בלוגיקה מתמטית, משפט לוונהיים-סקולם הוא משפט יסודי בתורת המודלים שקובע שאם לתורה בשפה בת מנייה מסדר ראשון יש מודל אינסופי, אז יש לה מודל מכל עוצמה אינסופית. המשפט מראה שלתורה בת-מנייה מסדר ראשון אין שליטה על העוצמה של המודלים האינסופיים שלה (בניגוד לשפה מסדר שני), ושכל תורה שכזו שיש לה מודל אינסופי אינה קטגורית (משמע יש לה יותר ממודל אחד עד כדי איזומורפיזם).
גרסה חזקה יותר של המשפט קובעת שלכל תורה בשפה מסדר ראשון (שאינה בהכרח בת מנייה) שיש לה מודל אינסופי, יש לה מודל מכל עוצמה אינסופית הגדולה מעוצמת קבוצת הקבועים שלה.
היסטוריה.
כמוסבר בהמשך, משפט לוונהיים-סקולם הוא תוצר של שני משפטים, משפט הכיווץ ומשפט הניפוח. ב-1915 הוכיח המתמטיקאי הגרמני לאופולד לוונהיים גרסה מוקדמת של משפט הכיווץ, שלכל תורה עם מודל אינסופי יש מודל בן מנייה. אולם בהוכחה של לוונהיים הייתה טעות. ב-1920 הציג המתמטיקאי הנורווגי תורלף סקולם הוכחה חלופית ונכונה.
המשפט המלא הוכח ב-1936 על ידי המתמטיקאי הרוסי אנטולי מלצב, לאחר שהוכיח את הגרסה המלאה של משפט הקומפקטיות הדרושה בהוכחת משפט הניפוח. במאמרו הוא ציין שלטענת סקולם המשפט המלא הוכח עוד קודם לכן על ידי אלפרד טרסקי במהלך סמינר ב-1928. אולם טרסקי לא זכר את הוכחתו ולא ברור כיצד יכול היה להוכיח את המשפט ללא משפט הקומפקטיות.
רקע.
מודל של תורה formula_1 בשפה מסדר ראשון formula_2 הוא מבנה (המורכב מקבוצה ומפונקציה המפרשת את קבועי השפה כקבועים ויחסים בקבוצה) שמקיים את כל הפסוקים בשפה. הקבוצה שעומדת בבסיס מבנה formula_3 נקראת העולם של formula_3, ונסמנו formula_5. העוצמה של formula_3 היא העוצמה של formula_5.
מבנה formula_8 הוא תת-מבנה של formula_3 אם formula_10, ופונקציית המבנה של formula_8 היא צמצום של פונקציית המבנה של formula_3 ל-formula_13. קבוצה formula_10 נקראת קבוצה סגורה ב-formula_3 אם formula_13 סגורה תחת כל הפעולות (פונקציות) בשפה formula_2 (ובפרט מכילה את כל האיברים ב-formula_5 המתפרשים כקבועים של formula_2, שהם הפעולות ה-0 מקומיות). אם formula_13 הוא תת-קבוצה סגורה של formula_5, אז התת-מבנה שנקבע על ידי formula_13 הוא התת-מבנה היחיד formula_8 שעולמו הוא formula_13 ושפונקציית המבנה שלו היא צמצום פונקציית המבנה של formula_3 ל-formula_13.
תת-מבנה formula_8 של מבנה formula_3 נקרא תת-מבנה אלמנטרי אם לכל השמה אפשרית כל הנוסחאות בשפה formula_2 שנכונות ב-formula_3, נכונות גם ב-formula_8 (אינטואיטיבית, כל טענה שנכונה במבנה נכונה גם בכל תת-מבנה אלמנטרי שלו, ולהפך). מן ההגדרה נובע שאם formula_3 מודל של formula_1, גם התת-מבנה האלמנטרי formula_8 הוא מודל של formula_1.
מבחן טרסקי-ווט קובע שתנאי הכרחי ומספיק לכך שתת-מבנה formula_8 של formula_3 הוא תת-מבנה אלמנטרי, הוא:
קבוצת פסוקים formula_48 היא עקבית אם קיים לה מודל (ראו משפט השלמות של גדל). משפט הקומפקטיות קובע ש-formula_48 עקבית אם ורק אם כל תת-קבוצה סופית שלה עקבית.
תנאי המשפט.
לא ניתן להחליש את תנאי המשפט. אם לתורה יש מודל סופי הדבר אינו גורר קיום מודל אינסופי. זאת משום שבכל שפה מסדר ראשון יש יחס שוויון, ולכן התורה יכולה לכלול פסוק שאומר שבכל קבוצה של n+1 איברים יש שניים שווים (ומכאן שכל מודל יש לכל היותר n איברים). גם קיומו של מודל אינסופי לא גורר קיום מודל סופי. למשל כל קבוצה אינסופית היא מודל לתורה שלכל n כוללת את הפסוק הקובע שיש לפחות n איברים שונים. מצד שני, לתורה זו אין אף מודל סופי.
אם שפת התורה אינה בת-מנייה, אז מתקיימת גרסה מוכללת של משפט לוונהיים-סקולם הקובעת שקיים מודל מכל עוצמה שאינה קטנה מעוצמת השפה. ההוכחה של המשפט המוכלל אנלוגית למקרה הבן מנייה.
הוכחה.
הוכחת המשפט נחלקת למעשה לשניים:
כמסקנה משני החלקים נובע משפט לוונהיים-סקולם במלואו:
הוכחת משפט הכיווץ.
יהי formula_3 מבנה בשפה formula_2 (המקיימת את תנאי המשפט) מעוצמה אינסופית formula_50. תהי formula_64 עוצמה אינסופית. נראה שיש ל-formula_3 תת-מבנה אלמנטרי מעוצמה formula_52.
לכל נוסחה formula_67 נתאים פונקציה formula_68 הנקראת פונקציית סקולם. פונקציית סקולם מוגדרת כך: לכל formula_69 מגדירים formula_70, כאשר formula_42 הוא איבר כך שמתקיים formula_72, אם ישנו איבר כזה, או סתם איבר שרירותי אם אין איבר כזה (בחירת האיברים מצריכה את אקסיומת הבחירה). נסמן ב-formula_73 את קבוצת פונקציות סקולם של כל הנוסחאות בשפה formula_2. יש formula_75 נוסחאות בשפה formula_2 (כי קבוצת המילים מעל שפה בת מנייה היא בת מנייה) ולכן formula_77.
נגדיר כעת ברקורסיה סדרת קבוצות. formula_78 תהיה תת-קבוצה כלשהי של formula_5 שעוצמתה formula_52. נגדיר:
כלומר formula_82 היא הקבוצה המתקבלת מ-formula_83 על ידי הוספת כל התמונות של איברי formula_83 תחת כל פונקציות סקולם.
נוכיח באינדוקציה כי לכל formula_85 טבעי, formula_86.
נגדיר formula_96. מהגדרת formula_13 מתקיים formula_98 וכן formula_99.
נבחין כי formula_13 סגורה תחת פונקציות סקולם. לכל formula_101 ולכל formula_102 קיים formula_83 כך ש-formula_104, ולכן formula_105.
נראה כי formula_13 קבוצה סגורה ב-formula_3. לכל פעולה formula_108 n-מקומית בשפה formula_2 נגדיר נוסחה formula_110 שהיא הנוסחה formula_111. מהסגירות של formula_13 ביחס לפונקציות סקולם נקבל ש-formula_13 סגורה ביחס ל-formula_108 - לכל formula_115 מתקיים: formula_116.
formula_13 קבוצה סגורה ולכן קיים תת-מבנה formula_8 של formula_3 שנקבע על ידה. נוכיח כי זהו תת-מבנה אלמנטרי.
לכל נוסחה formula_38 ולכל formula_41, אם קיים formula_42 כך שמתקיים formula_43, אז לפי הגדרת פונקציית סקולם קיים formula_124 כך שמתקיים formula_46. לכן לפי מבחן טרסקי-ווט formula_8 תת-מבנה אלמנטרי של formula_3.
מכאן שאם formula_3 מודל של תורה formula_1 המקיימת את תנאי המשפט, אז formula_8 היא מודל מעוצמה formula_52 של formula_1.
הוכחת משפט הניפוח.
תהי formula_1 תורה בשפה formula_2 המקיימת את תנאי המשפט, ויהי formula_3 מודל שלה מעוצמה אינסופית formula_50. תהי formula_54 עוצמה כלשהי. נבנה מודל של formula_1 שעוצמתו formula_52 לפחות.
תהי formula_140 קבוצה שעוצמתה formula_52. נגדיר שפה formula_142 המתקבלת מ-formula_2 על ידי הוספה של קבוע formula_144 כנגד כל formula_145. נגדיר קבוצת פסוקים formula_146 בשפה formula_142 כך: formula_148. נגדיר את formula_48 כקבוצה המתקבלת מהאיחוד formula_150.
נשתמש במשפט הקומפקטיות כדי להראות ש-formula_48 עקבית בשפה formula_142. תהי formula_153 תת-קבוצה סופית של formula_48. קיימת קבוצה מהצורה formula_155, כך ש-formula_156 היא תת-קבוצה סופית של formula_146, ומתקיים formula_158. ב-formula_156 יש רק מספר סופי של פסוקים מהצורה formula_160. נסמן את קבוצת כל ה-formula_144 שמופיעים בפסוק שכזה ב-formula_162.
נגדיר מבנה formula_163 בשפה formula_142 שפונקציית המבנה שלו מתלכדת עם זו של formula_3 לכל הקובעים ב-formula_2, ובנוסף מוגדרת באופן שרירותי לכל קבוע formula_144 ב-formula_142, מלבד לקבועים שב-formula_162, שאותם היא מפרשת כאיברים שונים זה מזה ב-formula_5 (ייתכן משום ש-formula_162 סופית, ואילו formula_5 אינסופית).
formula_163 מודל של formula_174 (כי formula_3 הוא מודל של formula_1, וכל הפסוקים ב-formula_156 שקובעים שאיברי formula_162 שונים זה מזה, אכן מתקיימים), לכן היא גם מודל של formula_153, ועל כן formula_153 עקבית. נקבל ממשפט הקומפקטיות ש-formula_48 עקבית בשפה formula_142. נסמן ב-formula_8 מודל של formula_48 בשפה formula_142. כל הפסוקים ב-formula_48 נכונים ב-formula_8, ובפרט כל פסוקי formula_146 שקובעים שיש formula_189 איברים השונים זה מזה נכונים. לכן formula_190.
formula_8 מודל של formula_1 בשפה formula_142 (כתת קבוצה של formula_48), ולכן הוא גם מודל של formula_1 בשפה formula_2 (תוך צמצום פונקציית המבנה שלו ל-formula_2). קיבלנו של-formula_1 יש מודל מעוצמה formula_52 לפחות.
מסקנות.
משפט לוונהיים-סקולם מאפשר להסיק מסקנות רבות על כוח הביטוי של שפה מסדר ראשון. מהמשפט נובע למשל שלא ניתן לתאר את קבוצת המספרים הטבעיים בשפה מסדר ראשון, בלי לתאר באותה מידה גרסאות מנופחות הכוללות "יותר מידי" מספרים. מכיוון שמערכת פאנו הכתובה בשפה מסדר שני מתארת את המספרים הטבעיים עד כדי איזומורפיזם, נובע מכך שלא ניתן לצמצם את אקסיומות מערכת פאנו לשפה מסדר ראשון. אריתמטיקת פאנו, שהיא המערכת המתקבלת מהחלפת אקסיומת האינדוקציה (הכתובה בסדר שני), בסכמה של אקסיומות הקובעות אינדוקציה לכל נוסחה מסדר ראשון, היא חלשה באופן מהותי ממערכת פאנו.
ממשפט לוונהיים-סקולם וממשפט הקומפקטיות ניתן להסיק שאם לתורה formula_1 יש מודלים סופיים בלתי חסומים (לכל M טבעי יש מודל שעוצמתו M לפחות), אז יש לה מודל מכל עוצמה אינסופית. ממשפט הקומפקטיות נובע שהתורה המתקבלת מ-formula_1 על ידי הוספת אינסוף פסוקים שקובעים שיש לפחות n איברים שונים לכל n טבעי היא עקבית. לכן יש לה ל-formula_1 מודל אינסופי, ולכן מודל מכל עוצמה אינסופית.