הצגת המקור של הדף "משפט לוונהיים-סקולם"

{{סימון מתמטי}}
ב[[לוגיקה מתמטית]], '''משפט לוונהיים-סקולם''' הוא [[משפט (מתמטיקה)|משפט]] יסודי ב[[תורת המודלים]] שקובע שאם ל[[תורה (לוגיקה מתמטית)|תורה]] בשפה [[קבוצה בת מנייה|בת מנייה]] [[שפה מסדר ראשון|מסדר ראשון]] יש [[מודל (לוגיקה מתמטית)|מודל]] [[קבוצה אינסופית|אינסופי]], אז יש לה מודל מכל [[עוצמה (מתמטיקה)|עוצמה]] אינסופית. המשפט מראה שלתורה בת מנייה מסדר ראשון אין שליטה על העוצמה של המודלים האינסופיים שלה (בניגוד ל[[לוגיקה מסדר שני]]), ושכל תורה שכזו שיש לה מודל אינסופי אינה קטגורית (משמע יש לה יותר ממודל אחד [[עד כדי]] [[איזומורפיזם (לוגיקה מתמטית)|איזומורפיזם]]).

גרסה חזקה יותר של המשפט קובעת שלכל תורה בשפה מסדר ראשון ([[קבוצה שאינה בת מנייה|שאינה בת מנייה]] בהכרח) שיש לה מודל אינסופי, יש לה מודל מכל עוצמה אינסופית הגדולה מעוצמת קבוצת הקבועים שלה.

==היסטוריה==
כמוסבר בהמשך, משפט לוונהיים-סקולם הוא תוצר של שני משפטים, משפט הכיווץ ומשפט הניפוח. ב-[[1915]] הוכיח המתמטיקאי הגרמני [[לאופולד לוונהיים]] גרסה מוקדמת של משפט הכיווץ, שלכל תורה עם מודל אינסופי יש מודל בן מנייה. אולם בהוכחה של לוונהיים הייתה טעות. ב-[[1920]] הציג המתמטיקאי הנורווגי [[תורלף סקולם]] הוכחה חלופית ונכונה.

המשפט המלא הוכח ב-[[1936]] על ידי המתמטיקאי הרוסי [[אנטולי מלצב]], לאחר שהוכיח את הגרסה המלאה של [[משפט הקומפקטיות]] הדרושה בהוכחת משפט הניפוח. במאמרו הוא ציין שלטענת סקולם המשפט המלא הוכח עוד קודם לכן על ידי [[אלפרד טרסקי]] במהלך סמינר ב-[[1928]]. אולם טרסקי לא זכר את הוכחתו ולא ברור כיצד יכול היה להוכיח את המשפט ללא משפט הקומפקטיות.

==רקע==
[[מודל (לוגיקה מתמטית)|מודל]] של תורה <math>T</math> ב[[שפה מסדר ראשון]] <math>L</math> הוא '''[[מבנה (לוגיקה מתמטית)|מבנה]]''' (המורכב מ[[קבוצה (מתמטיקה)|קבוצה]] ומ[[פונקציה]] המפרשת את קבועי השפה כקבועים ו[[יחס (תורת הקבוצות)|יחס]]ים בקבוצה) שמקיים את כל ה[[פסוק (לוגיקה מתמטית)|פסוק]]ים בשפה. הקבוצה שעומדת בבסיס מבנה <math>\mathcal A</math> נקראת העולם של <math>\mathcal A</math>, ונסמנו <math>A</math>. העוצמה של <math>\mathcal A</math> היא ה[[עוצמה (מתמטיקה)|עוצמה]] של <math>A</math>. 

מבנה <math>\mathcal B</math> הוא '''תת-מבנה''' של <math>\mathcal A</math> אם <math>B \subseteq A</math>, ופונקציית המבנה של <math>\mathcal B</math> היא צמצום של פונקציית המבנה של <math>\mathcal A</math> ל-<math>B</math>. קבוצה <math>B \subseteq A</math> נקראת '''קבוצה סגורה''' ב-<math>\mathcal A</math> אם <math>B</math> [[סגירות (אלגברה)|סגורה]] תחת כל הפעולות (פונקציות) בשפה <math>L</math> (ובפרט מכילה את כל האיברים ב-<math>A</math> המתפרשים כקבועים של <math>L</math>, שהם הפעולות ה-0 מקומיות). אם <math>B</math> הוא תת-קבוצה סגורה של <math>A</math>, אז ה'''תת-מבנה שנקבע על ידי <math>B</math>''' הוא התת-מבנה היחיד <math>\mathcal B</math> שעולמו הוא <math>B</math> ושפונקציית המבנה שלו היא צמצום פונקציית המבנה של <math>\mathcal A</math> ל-<math>B</math>.

תת-מבנה <math>\mathcal B</math> של מבנה <math>\mathcal A</math> נקרא '''[[תת-מבנה אלמנטרי]]''' אם לכל השמה אפשרית כל ה[[נוסחה (לוגיקה)|נוסחאות]] בשפה <math>L</math> שנכונות ב-<math>\mathcal A</math>, נכונות גם ב-<math>\mathcal B</math> (אינטואיטיבית, כל טענה שנכונה במבנה נכונה גם בכל תת-מבנה אלמנטרי שלו, ולהפך). מן ההגדרה  נובע שאם <math>\mathcal A</math> מודל של <math>T</math>, גם התת-מבנה האלמנטרי <math>\mathcal B</math> הוא מודל של <math>T</math>.

'''[[מבחן טרסקי-ווט]]''' קובע ש[[תנאי הכרחי ומספיק]] לכך שתת-מבנה <math>\mathcal B</math> של <math>\mathcal A</math> הוא תת-מבנה אלמנטרי, הוא:
:לכל נוסחה <math>\phi(x,x_1,\ldots, x_n)</math> בשפה <math>L</math>, אשר <math>x,x_1,\ldots,x_n</math> הם המשתנים החופשיים בה, ולכל <math>b_1,\ldots,b_n\in B</math>, אם קיים <math>a\in A</math> כך ש-<math>\phi(a,b_1,\ldots,b_n)</math> נכון ב-<math>\mathcal A</math>, אז קיים <math>b\in B</math> כך ש-<math>\phi(b,b_1,\ldots,b_n)</math> נכון ב-<math>\mathcal A</math>.

קבוצת פסוקים <math>\Gamma</math> היא '''[[עקביות (לוגיקה)|עקבית]]''' אם קיים לה מודל (ראו [[משפט השלמות של גדל]]). '''[[משפט הקומפקטיות]]''' קובע ש-<math>\Gamma</math> עקבית אם ורק אם כל תת-קבוצה סופית שלה עקבית.

==תנאי המשפט==
לא ניתן להחליש את תנאי המשפט. אם לתורה יש מודל סופי הדבר אינו גורר קיום מודל אינסופי. זאת משום שבכל שפה מסדר ראשון יש יחס שוויון, ולכן התורה יכולה לכלול פסוק שאומר שבכל קבוצה של n+1 איברים יש שניים שווים (ומכאן שכל מודל יש לכל היותר n איברים). גם קיומו של מודל אינסופי לא גורר קיום מודל סופי. למשל כל קבוצה אינסופית היא מודל לתורה שלכל n כוללת את הפסוק הקובע שיש לפחות n איברים שונים. מצד שני, לתורה זו אין אף מודל סופי.

אם שפת התורה אינה בת-מנייה, אז מתקיימת גרסה מוכללת של משפט לוונהיים-סקולם הקובעת שקיים מודל מכל עוצמה שאינה קטנה מעוצמת השפה. ההוכחה של המשפט המוכלל אנלוגית למקרה הבן מנייה.

==הוכחה==
הוכחת המשפט נחלקת למעשה לשניים:
*משפט הכיווץ - לכל תורה בת-מנייה מסדר ראשון עם מודל אינסופי מעוצמה <math>\kappa</math>, ולכל עוצמה אינסופית <math>\mu\le \kappa</math>,  קיים לתורה זו מודל מעוצמה <math>\mu</math>. 
*משפט הניפוח - לכל תורה בת-מנייה מסדר ראשון עם מודל אינסופי מעוצמה <math>\kappa</math>, ולכל עוצמה <math>\kappa\le\mu</math>, קיים לתורה זו מודל מעוצמה <math>\mu</math> לפחות.
כמסקנה משני החלקים נובע משפט לוונהיים-סקולם במלואו:
*אם לתורה בת-מנייה מסדר ראשון יש מודל אינסופי מעוצמה <math>\kappa</math>, אז לכל עוצמה אינסופית <math>\mu</math> נבחר עוצמה <math>\kappa,\mu \le \lambda</math>. לפי משפט הניפוח קיים מודל מעוצמה <math>\lambda</math> לפחות, ולכן לפי משפט הכיווץ קיים מודל מעוצמה <math>\mu</math>.

===הוכחת משפט הכיווץ===
יהי <math>\mathcal A</math> מבנה בשפה <math>L</math> (המקיימת את תנאי המשפט) מעוצמה אינסופית <math>\kappa</math>. תהי <math>\mu\le\kappa</math> עוצמה אינסופית. נראה שיש ל-<math>\mathcal A</math> תת-מבנה אלמנטרי מעוצמה <math>\mu</math>.

לכל נוסחה <math>\phi(x,x_1,\ldots,x_n)</math> נתאים פונקציה <math>f_\phi : A^n \to A</math> הנקראת '''פונקציית סקולם'''. פונקציית סקולם מוגדרת כך: לכל <math>a_1,\ldots,a_n\in A</math> מגדירים <math>f_\phi (a_1,\ldots,a_n) = a</math>, כאשר <math>a\in A</math> הוא איבר כך שמתקיים <math>\phi(a,a_1,\ldots,a_n)</math>, אם ישנו איבר כזה, או סתם איבר שרירותי אם אין איבר כזה (בחירת האיברים מצריכה את [[אקסיומת הבחירה]]). נסמן ב-<math>S</math> את קבוצת פונקציות סקולם של כל הנוסחאות בשפה <math>L</math>. יש <math>\aleph_0</math> נוסחאות בשפה <math>L</math> (כי קבוצת המילים מעל שפה [[קבוצה בת מנייה|בת מנייה]] היא בת מנייה) ולכן <math>|S|=\aleph_0</math>.

נגדיר כעת ב[[הגדרה רקורסיבית|רקורסיה]] סדרת קבוצות. <math>B_0</math> תהיה תת-קבוצה כלשהי של <math>A</math> שעוצמתה <math>\mu</math>. נגדיר:
:<math>B_{n+1} = B_n \cup \{f_\phi (b_1,\ldots,b_k) \mid b_1,\ldots,b_k\in B_n \ ,\ f_\phi \in S \}</math>
כלומר <math>B_{n+1}</math> היא הקבוצה המתקבלת מ-<math>B_n</math> על ידי הוספת כל התמונות של איברי <math>B_n</math> תחת כל פונקציות סקולם.

נוכיח ב[[אינדוקציה מתמטית|אינדוקציה]] כי לכל <math>n</math> טבעי, <math>|B_n| = \mu</math>.
*על פי הגדרתו, <math>B_0</math> מקיים <math>|B_0| = \mu</math>.
*נניח שמתקיים <math>|B_n| = \mu</math>. אז יש <math>\mu</math> [[N-יה סדורה|k-יות סדורות]] של איברי <math>B_n</math> ([[משפט טרסקי]]), ויש <math>\aleph_0</math> פונקציות סקולם, ולכן יש <math>\aleph_0\cdot\mu = \mu</math> תמונות של איברי <math>B_n</math> תחת פונקציות סקולם. מכאן ש-<math>|B_{n+1}| = |B_n| + \mu = \mu</math>.

נגדיר <math>B = \bigcup_{n=0}^\infty B_n</math>. מהגדרת <math>B</math> מתקיים <math>B\subseteq A</math> וכן <math>|B| = \aleph_0\cdot\mu = \mu</math>. 

נבחין כי <math>B</math> סגורה תחת פונקציות סקולם. לכל <math>f_\phi \in S</math> ולכל <math>b_1,\ldots, b_k \in B</math> קיים <math>B_n</math> כך ש-<math>b_1,\ldots, b_k \in B_n</math>, ולכן <math>f_\phi (b_1,\ldots, b_k) \in B_{n+1} \subseteq B</math>.

נראה כי <math>B</math> [[קבוצה סגורה]] ב-<math>\mathcal A</math>. לכל פעולה <math>F</math> n-מקומית בשפה <math>L</math> נגדיר נוסחה <math>\phi_F(x,x_1,\ldots,x_n)</math> שהיא הנוסחה <math>x = F(x_1,\ldots,x_n)</math>. מהסגירות של <math>B</math> ביחס לפונקציות סקולם נקבל ש-<math>B</math> סגורה ביחס ל-<math>F</math> - לכל <math>b_1,\ldots,b_n \in B</math> מתקיים: <math>F(b_1,\ldots,b_n) = f_{\phi_{F}}(b_1,\ldots,b_n) \in B</math>.

<math>B</math> קבוצה סגורה ולכן קיים תת-מבנה <math>\mathcal B</math> של <math>\mathcal A</math> שנקבע על ידה. נוכיח כי זהו תת-מבנה אלמנטרי.

לכל נוסחה <math>\phi(x,x_1,\ldots, x_n)</math> ולכל <math>b_1,\ldots,b_n\in B</math>, אם קיים <math>a\in A</math> כך שמתקיים <math>\phi(a,b_1,\ldots,b_n)</math>, אז לפי הגדרת פונקציית סקולם קיים <math>b = f_\phi (b_1,\ldots,b_n) \in B</math> כך שמתקיים <math>\phi(b,b_1,\ldots,b_n)</math>. לכן לפי מבחן טרסקי-ווט <math>\mathcal B</math> תת-מבנה אלמנטרי של <math>\mathcal A</math>.

מכאן שאם <math>\mathcal A</math> מודל של תורה <math>T</math> המקיימת את תנאי המשפט, אז <math>\mathcal B</math> היא מודל מעוצמה <math>\mu</math> של <math>T</math>.

===הוכחת משפט הניפוח===
תהי <math>T</math> תורה בשפה <math>L</math> המקיימת את תנאי המשפט, ויהי <math>\mathcal A</math> מודל שלה מעוצמה אינסופית <math>\kappa</math>. תהי <math>\kappa\le\mu</math> עוצמה כלשהי. נבנה מודל של <math>T</math> שעוצמתו <math>\mu</math> לפחות.

תהי <math>I</math> קבוצה שעוצמתה <math>\mu</math>. נגדיר שפה <math>L_I</math> המתקבלת מ-<math>L</math> על ידי הוספה של קבוע <math>c_i</math> כנגד כל <math>i \in I</math>. נגדיר קבוצת [[פסוק (לוגיקה מתמטית)|פסוק]]ים <math>\Sigma</math> בשפה <math>L_I</math> כך: <math>\Sigma = \{c_i \ne c_j \mid i\ne j \ ,\ i,j \in I \}</math>. נגדיר את <math>\Gamma</math> כקבוצה המתקבלת מהאיחוד <math>\Gamma = T \cup \Sigma</math>.

נשתמש ב[[משפט הקומפקטיות]] כדי להראות ש-<math>\Gamma</math> [[עקביות (לוגיקה)|עקבית]] בשפה <math>L_I</math>. תהי <math>\Gamma_0</math> תת-קבוצה סופית של <math>\Gamma</math>. קיימת קבוצה מהצורה <math>\Gamma_1 = T \cup \Sigma_0</math>, כך ש-<math>\Sigma_0</math> היא תת-קבוצה סופית של <math>\Sigma</math>, ומתקיים <math>\Gamma_0 \subseteq \Gamma_1</math>. ב-<math>\Sigma_0</math> יש רק מספר סופי של פסוקים מהצורה <math>c_i \ne c_j</math>. נסמן את קבוצת כל ה-<math>c_i</math> שמופיעים בפסוק שכזה ב-<math>C</math>. 

נגדיר מבנה <math>\mathcal A^*</math> בשפה <math>L_I</math> שפונקציית המבנה שלו מתלכדת עם זו של <math>\mathcal A</math> לכל הקובעים ב-<math>L</math>, ובנוסף מוגדרת באופן שרירותי לכל קבוע <math>c_i</math> ב-<math>L_I</math>, מלבד לקבועים שב-<math>C</math>, שאותם היא מפרשת כאיברים שונים זה מזה ב-<math>A</math> (ייתכן משום ש-<math>C</math> סופית, ואילו <math>A</math> אינסופית).

<math>\mathcal A^*</math> מודל של <math>\Gamma_1</math> (כי <math>\mathcal A</math> הוא מודל של <math>T</math>, וכל הפסוקים ב-<math>\Sigma_0</math> שקובעים שאיברי <math>C</math> שונים זה מזה, אכן מתקיימים), לכן היא גם מודל של <math>\Gamma_0</math>, ועל כן <math>\Gamma_0</math> עקבית. נקבל ממשפט הקומפקטיות ש-<math>\Gamma</math> עקבית בשפה <math>L_I</math>. נסמן ב-<math>\mathcal B</math> מודל של <math>\Gamma</math> בשפה <math>L_I</math>. כל הפסוקים ב-<math>\Gamma</math> נכונים ב-<math>\mathcal B</math>, ובפרט כל פסוקי <math>\Sigma</math> שקובעים שיש <math>|I|</math> איברים השונים זה מזה נכונים. לכן <math>\mu = |I| \le |B|</math>.

<math>\mathcal B</math> מודל של <math>T</math> בשפה <math>L_I</math> (כתת קבוצה של <math>\Gamma</math>), ולכן הוא גם מודל של <math>T</math> בשפה <math>L</math> (תוך צמצום פונקציית המבנה שלו ל-<math>L</math>). קיבלנו של-<math>T</math> יש מודל מעוצמה <math>\mu</math> לפחות.

==מסקנות==
משפט לוונהיים-סקולם מאפשר להסיק מסקנות רבות על כוח הביטוי של שפה מסדר ראשון. מהמשפט נובע למשל שלא ניתן לתאר את [[קבוצת המספרים הטבעיים]] בשפה מסדר ראשון, בלי לתאר באותה מידה גרסאות מנופחות הכוללות "יותר מידי" מספרים. מכיוון ש[[מערכת פאנו]] הכתובה ב[[לוגיקה מסדר שני]] מתארת את המספרים הטבעיים [[עד כדי (מתמטיקה)|עד כדי]] [[איזומורפיזם]], נובע מכך שלא ניתן לצמצם את [[אקסיומה|אקסיומות]] מערכת פאנו לשפה מסדר ראשון. [[אריתמטיקת פאנו]], שהיא המערכת המתקבלת מהחלפת [[אקסיומת האינדוקציה]] (הכתובה בסדר שני), בסכמה של אקסיומות הקובעות אינדוקציה לכל נוסחה מסדר ראשון, היא חלשה באופן מהותי ממערכת פאנו.

ממשפט לוונהיים-סקולם וממשפט הקומפקטיות ניתן להסיק שאם לתורה <math>T</math> יש מודלים סופיים בלתי חסומים (לכל M טבעי יש מודל שעוצמתו M לפחות), אז יש לה מודל מכל עוצמה אינסופית. ממשפט הקומפקטיות נובע שהתורה המתקבלת מ-<math>T</math> על ידי הוספת אינסוף פסוקים שקובעים שיש לפחות n איברים שונים לכל n טבעי היא עקבית. לכן יש לה ל-<math>T</math> מודל אינסופי, ולכן מודל מכל עוצמה אינסופית.

מסקנה נוספת ממשפט לוונהיים-סקולם היא שאם <math>T</math> תורה <math>\aleph_0</math>-[[תורה קטגורית|קטגורית]] (יש לה מודל יחיד עד כדי איזומורפיזם מעוצמה <math>\aleph_0</math>), ואין לה מודלים סופיים, אז <math>T</math> [[שלמות|תורה שלמה]]. זאת משום שאם <math>\mathcal A, \mathcal B</math> הם מודלים כלשהם של <math>T</math>, אז לפי הנתון הם אינם סופיים, ולכן לפי משפט הכיווץ יש להם תת-מבנים אלמנטריים <math>\mathcal A_0, \mathcal B_0</math> מעוצמה <math>\aleph_0</math>. מכיוון ש-<math>T</math> תורה <math>\aleph_0</math>-קטגורית נובע מכך ש-<math>\mathcal A_0, \mathcal B_0</math> איזומורפיים. לכן אותם משפטים נכונים הן ב-<math>\mathcal A</math> והן ב-<math>\mathcal B</math>, וכל המשפטים הללו בהכרח נובעים מ-<math>T</math>.

בראשית [[המאה ה-20]] ניסתה הקהילה המתמטית למצוא תורה מסדר ראשון שתתאר את המתמטיקה המודרנית כולה (ראו [[תוכנית הילברט]]). משפט לוונהיים-סקולם קבע שאף תורה שכזו לא תהיה קטגורית, ויהיו לה מודלים רבים. מאוחר יותר הוכח [[משפטי האי-שלמות של גדל]] שאף החריף את הבעיה יותר - לא תיתכן תורה שכזו שתהיה גם עקבית, גם [[תורה אפקטיבית|אפקטיבית]] וגם [[שלמות|שלמה]] (כלומר לא רק שיהיו לה מודלים רבים, אלא שלא בכולם יתקיימו אותם המשפטים).

[[משפט לינדסטרום]] קובע ששפה מסדר ראשון היא התחשיב הלוגי החזק ביותר שבמסגרתו מתקיימים הן משפט הקומפקטיות והן משפט הכיווץ של לוונהיים-סקולם.

==פרדוקס סקולם==
החלת משפט לוונהיים-סקולם על [[תורת הקבוצות האקסיומטית]] גוררת מסקנה הנדמית סתירתית. לפי המשפט קיים מודל בן מנייה של תורת הקבוצות. לכן כל הקבוצות במודל הן בנות מנייה (שכן כל איבר של קבוצה הוא בעצמו קבוצה במסגרת [[אקסיומות צרמלו-פרנקל]]). זאת בסתירה לכאורה ל[[משפט קנטור]] שממנו עולה שקיימות [[קבוצה שאינה בת מנייה|קבוצות שאינן בנות מנייה]].

תוצאה זו התגלתה על ידי סקולם ב-[[1922]] ונקראת על שמו "[[פרדוקס]] סקולם". סקולם גם הסביר מדוע הפרדוקס אינו סתירה באמת. הפתרון נעוץ בכך שהמונח "קבוצה" במודל של סקולם נבדל מהמשמעות החיצונית שלו. השוואת עוצמות של קבוצות מסתמכת על קיומן של [[פונקציה חד-חד-ערכית ועל|פונקציות חד-חד-ערכיות ועל]] ביניהן. אולם פונקציות שכאלה הן בעצמן קבוצות, שאינן בהכרח כלולות כקבוצות במסגרת המודל הקטן ובן המנייה של סקולם לתורת הקבוצות. נכון שקיימת פונקציה חיצונית למודל שמתאימה בין קבוצת המספרים הטבעיים לקבוצת המספרים הממשיים במודל של סקולם, אבל הפונקציה הזו אינה קיימת בתוך המודל של סקולם, ולכן הוכחת [[האלכסון של קנטור]] עדין עובדת במודל זה.

==קישורים חיצוניים==
*{{MathWorld}}

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:משפטים בלוגיקה|לוונהיים-סקולם]]
[[קטגוריה:הוכחות]]