משפט לוונהיים-סקולם

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Nuvola apps edu mathematics blue-p.svg

בערך זה
נעשה שימוש
בסימנים מוסכמים
מתחום המתמטיקה.
להבהרת הסימנים
ראו סימון מתמטי.

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

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

רקע[עריכת קוד מקור | עריכה]

מודל של תורה T בשפה מסדר ראשון L הוא מבנה (המורכב מקבוצה ומפונקציה המפרשת את קבועי השפה כקבועים ויחסים בקבוצה) שמקיים את כל הפסוקים בשפה. הקבוצה שעומדת בבסיס מבנה \mathcal A נקראת העולם של \mathcal A, ונסמנו A. העוצמה של \mathcal A היא העוצמה של A.

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

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

מבחן טרסקי-ווט קובע שתנאי הכרחי ומספיק לכך שתת-מבנה \mathcal B של \mathcal A הוא תת-מבנה אלמנטרי, הוא:

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

קבוצת פסוקים \Gamma היא עקבית אם קיים לה מודל (ראו משפט השלמות של גדל). משפט הקומפקטיות קובע ש-\Gamma עקבית אם ורק אם כל תת-קבוצה סופית שלה עקבית.

תנאי המשפט[עריכת קוד מקור | עריכה]

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

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

הוכחה[עריכת קוד מקור | עריכה]

הוכחת המשפט נחלקת למעשה לשניים:

  • משפט הכיווץ - לכל תורה בת-מנייה מסדר ראשון עם מודל אינסופי מעוצמה \kappa, ולכל עוצמה אינסופית \mu\le \kappa, קיים לתורה זו מודל מעוצמה \mu.
  • משפט הניפוח - לכל תורה בת-מנייה מסדר ראשון עם מודל אינסופי מעוצמה \kappa, ולכל עוצמה \kappa\le\mu, קיים לתורה זו מודל מעוצמה \mu לפחות.

כמסקנה משני החלקים נובע משפט לוונהיים-סקולם במלואו:

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

הוכחת משפט הכיווץ[עריכת קוד מקור | עריכה]

יהי \mathcal A מבנה בשפה L (המקיימת את תנאי המשפט) מעוצמה אינסופית \kappa. תהי \mu\le\kappa עוצמה אינסופית. נראה שיש ל-\mathcal A תת-מבנה אלמנטרי מעוצמה \mu.

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

נגדיר כעת ברקורסיה סדרת קבוצות. B_0 תהיה תת-קבוצה כלשהי של A שעוצמתה \mu. נגדיר:

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 \}

כלומר B_{n+1} היא הקבוצה המתקבלת מ-B_n על ידי הוספת כל התמונות של איברי B_n תחת כל פונקציות סקולם.

נוכיח באינודקציה כי לכל n טבעי, |B_n| = \mu.

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

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

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

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

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

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

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

הוכחת משפט הניפוח[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

מסקנות[עריכת קוד מקור | עריכה]

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

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

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

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

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

פרדוקס סקולם[עריכת קוד מקור | עריכה]

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

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