משפט לוונהיים-סקולם
בערך זה |
בלוגיקה מתמטית, משפט לוונהיים-סקולם הוא משפט יסודי בתורת המודלים שקובע שאם לתורה בשפה בת מנייה מסדר ראשון יש מודל אינסופי, אז יש לה מודל מכל עוצמה אינסופית. המשפט מראה שלתורה בת-מנייה מסדר ראשון אין שליטה על העוצמה של המודלים האינסופיים שלה (בניגוד לשפה מסדר שני), ושכל תורה שכזו שיש לה מודל אינסופי אינה קטגורית (משמע יש לה יותר ממודל אחד עד כדי איזומורפיזם).
גרסה חזקה יותר של המשפט קובעת שלכל תורה בשפה מסדר ראשון (שאינה בת מנייה בהכרח ) שיש לה מודל אינסופי, יש לה מודל מכל עוצמה אינסופית הגדולה מעוצמת קבוצת הקבועים שלה.
היסטוריה
כמוסבר בהמשך, משפט לוונהיים-סקולם הוא תוצר של שני משפטים, משפט הכיווץ ומשפט הניפוח. ב-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}} $, נכונות גם ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal B (אינטואיטיבית, כל טענה שנכונה במבנה נכונה גם בכל תת-מבנה אלמנטרי שלו, ולהפך). מן ההגדרה נובע שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A מודל של $ T $, גם התת-מבנה האלמנטרי $ {\mathcal {B}} $ הוא מודל של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): T .
מבחן טרסקי-ווט קובע שתנאי הכרחי ומספיק לכך שתת-מבנה $ {\mathcal {B}} $ של $ {\mathcal {A}} $ הוא תת-מבנה אלמנטרי, הוא:
- לכל נוסחה $ \phi (x,x_{1},\ldots ,x_{n}) $ בשפה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): 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}} $, אז קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): b\in B כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \phi(b,b_1,\ldots,b_n) נכון ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A .
קבוצת פסוקים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma היא עקבית אם קיים לה מודל (ראו משפט השלמות של גדל). משפט הקומפקטיות קובע ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma עקבית אם ורק אם כל תת-קבוצה סופית שלה עקבית.
תנאי המשפט
לא ניתן להחליש את תנאי המשפט. אם לתורה יש מודל סופי הדבר אינו גורר קיום מודל אינסופי. זאת משום שבכל שפה מסדר ראשון יש יחס שוויון, ולכן התורה יכולה לכלול פסוק שאומר שבכל קבוצה של n+1 איברים יש שניים שווים (ומכאן שכל מודל יש לכל היותר n איברים). גם קיומו של מודל אינסופי לא גורר קיום מודל סופי. למשל כל קבוצה אינסופית היא מודל לתורה שלכל n כוללת את הפסוק הקובע שיש לפחות n איברים שונים. מצד שני, לתורה זו אין אף מודל סופי.
אם שפת התורה אינה בת-מנייה, אז מתקיימת גרסה מוכללת של משפט לוונהיים-סקולם הקובעת שקיים מודל מכל עוצמה שאינה קטנה מעוצמת השפה. ההוכחה של המשפט המוכלל אנלוגית למקרה הבן מנייה.
הוכחה
הוכחת המשפט נחלקת למעשה לשניים:
- משפט הכיווץ - לכל תורה בת-מנייה מסדר ראשון עם מודל אינסופי מעוצמה $ \kappa $, ולכל עוצמה אינסופית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mu\le \kappa , קיים לתורה זו מודל מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mu .
- משפט הניפוח - לכל תורה בת-מנייה מסדר ראשון עם מודל אינסופי מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \kappa , ולכל עוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \kappa\le\mu , קיים לתורה זו מודל מעוצמה $ \mu $ לפחות.
כמסקנה משני החלקים נובע משפט לוונהיים-סקולם במלואו:
- אם לתורה בת-מנייה מסדר ראשון יש מודל אינסופי מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \kappa , אז לכל עוצמה אינסופית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mu נבחר עוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \kappa,\mu \le \lambda . לפי משפט הניפוח קיים מודל מעוצמה $ \lambda $ לפחות, ולכן לפי משפט הכיווץ קיים מודל מעוצמה $ \mu $.
הוכחת משפט הכיווץ
יהי $ {\mathcal {A}} $ מבנה בשפה $ L $ (המקיימת את תנאי המשפט) מעוצמה אינסופית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \kappa . תהי $ \mu \leq \kappa $ עוצמה אינסופית. נראה שיש ל-$ {\mathcal {A}} $ תת-מבנה אלמנטרי מעוצמה $ \mu $.
לכל נוסחה $ \phi (x,x_{1},\ldots ,x_{n}) $ נתאים פונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): f_\phi : A^n \to A הנקראת פונקציית סקולם. פונקציית סקולם מוגדרת כך: לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): 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 $. נגדיר:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): 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 $ מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): 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 $.
נראה כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): B קבוצה סגורה ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A . לכל פעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): F n-מקומית בשפה $ L $ נגדיר נוסחה $ \phi _{F}(x,x_{1},\ldots ,x_{n}) $ שהיא הנוסחה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): x = F(x_1,\ldots,x_n) . מהסגירות של $ B $ ביחס לפונקציות סקולם נקבל ש-$ B $ סגורה ביחס ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): F - לכל $ b_{1},\ldots ,b_{n}\in B $ מתקיים: $ F(b_{1},\ldots ,b_{n})=f_{\phi _{F}}(b_{1},\ldots ,b_{n})\in B $.
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): B קבוצה סגורה ולכן קיים תת-מבנה $ {\mathcal {B}} $ של $ {\mathcal {A}} $ שנקבע על ידה. נוכיח כי זהו תת-מבנה אלמנטרי.
לכל נוסחה $ \phi (x,x_{1},\ldots ,x_{n}) $ ולכל $ b_{1},\ldots ,b_{n}\in B $, אם קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): a\in A כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \phi(a,b_1,\ldots,b_n) , אז לפי הגדרת פונקציית סקולם קיים $ b=f_{\phi }(b_{1},\ldots ,b_{n})\in B $ כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \phi(b,b_1,\ldots,b_n) . לכן לפי מבחן טרסקי-ווט $ {\mathcal {B}} $ תת-מבנה אלמנטרי של $ {\mathcal {A}} $.
מכאן שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A מודל של תורה $ T $ המקיימת את תנאי המשפט, אז $ {\mathcal {B}} $ היא מודל מעוצמה $ \mu $ של $ T $.
הוכחת משפט הניפוח
תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): T תורה בשפה $ L $ המקיימת את תנאי המשפט, ויהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A מודל שלה מעוצמה אינסופית $ \kappa $. תהי $ \kappa \leq \mu $ עוצמה כלשהי. נבנה מודל של $ T $ שעוצמתו $ \mu $ לפחות.
תהי $ I $ קבוצה שעוצמתה $ \mu $. נגדיר שפה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): L_I המתקבלת מ-$ L $ על ידי הוספה של קבוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): c_i כנגד כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): i \in I . נגדיר קבוצת פסוקים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Sigma בשפה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): L_I כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Sigma = \{c_i \ne c_j \mid i\ne j \ ,\ i,j \in I \} . נגדיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma כקבוצה המתקבלת מהאיחוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma = T \cup \Sigma .
נשתמש במשפט הקומפקטיות כדי להראות ש-$ \Gamma $ עקבית בשפה $ L_{I} $. תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma_0 תת-קבוצה סופית של $ \Gamma $. קיימת קבוצה מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma_1 = T \cup \Sigma_0 , כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Sigma_0 היא תת-קבוצה סופית של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Sigma , ומתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma_0 \subseteq \Gamma_1 . ב-$ \Sigma _{0} $ יש רק מספר סופי של פסוקים מהצורה $ c_{i}\neq c_{j} $. נסמן את קבוצת כל ה-$ c_{i} $ שמופיעים בפסוק שכזה ב-$ C $.
נגדיר מבנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A^* בשפה $ L_{I} $ שפונקציית המבנה שלו מתלכדת עם זו של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A לכל הקובעים ב-$ L $, ובנוסף מוגדרת באופן שרירותי לכל קבוע $ c_{i} $ ב-$ L_{I} $, מלבד לקבועים שב-$ C $, שאותם היא מפרשת כאיברים שונים זה מזה ב-$ A $ (ייתכן משום ש-$ C $ סופית, ואילו $ A $ אינסופית).
$ {\mathcal {A}}^{*} $ מודל של $ \Gamma _{1} $ (כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A הוא מודל של $ T $, וכל הפסוקים ב-$ \Sigma _{0} $ שקובעים שאיברי $ C $ שונים זה מזה, אכן מתקיימים), לכן היא גם מודל של $ \Gamma _{0} $, ועל כן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma_0 עקבית. נקבל ממשפט הקומפקטיות ש-$ \Gamma $ עקבית בשפה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): L_I . נסמן ב-$ {\mathcal {B}} $ מודל של $ \Gamma $ בשפה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): L_I . כל הפסוקים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \Gamma נכונים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal B , ובפרט כל פסוקי $ \Sigma $ שקובעים שיש $ |I| $ איברים השונים זה מזה נכונים. לכן $ \mu =|I|\leq |B| $.
$ {\mathcal {B}} $ מודל של $ T $ בשפה $ L_{I} $ (כתת קבוצה של $ \Gamma $), ולכן הוא גם מודל של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): T בשפה $ L $ (תוך צמצום פונקציית המבנה שלו ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): L ). קיבלנו של-$ T $ יש מודל מעוצמה $ \mu $ לפחות.
מסקנות
משפט לוונהיים-סקולם מאפשר להסיק מסקנות רבות על כוח הביטוי של שפה מסדר ראשון. מהמשפט נובע למשל שלא ניתן לתאר את קבוצת המספרים הטבעיים בשפה מסדר ראשון, בלי לתאר באותה מידה גרסאות מנופחות הכוללות "יותר מידי" מספרים. מכיוון שמערכת פאנו הכתובה בשפה מסדר שני מתארת את המספרים הטבעיים עד כדי איזומורפיזם, נובע מכך שלא ניתן לצמצם את אקסיומות מערכת פאנו לשפה מסדר ראשון. אריתמטיקת פאנו, שהיא המערכת המתקבלת מהחלפת אקסיומת האינדוקציה (הכתובה בסדר שני), בסכמה של אקסיומות הקובעות אינדוקציה לכל נוסחה מסדר ראשון, היא חלשה באופן מהותי ממערכת פאנו.
ממשפט לוונהיים-סקולם וממשפט הקומפקטיות ניתן להסיק שאם לתורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): 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} $ איזומורפיים. לכן אותם משפטים נכונים הן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal A והן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): \mathcal B , וכל המשפטים הללו בהכרח נובעים מ-$ T $.
בראשית המאה ה-20 ניסתה הקהילה המתמטית למצוא תורה מסדר ראשון שתתאר את המתמטיקה המודרנית כולה (ראו תוכנית הילברט). משפט לוונהיים-סקולם קבע שאף תורה שכזו לא תהיה קטגורית, ויהיו לה מודלים רבים. מאוחר יותר הוכח משפטי האי-שלמות של גדל שאף החריף את הבעיה יותר - לא תיתכן תורה שכזו שתהיה גם עקבית, גם אפקטיבית וגם שלמה (כלומר לא רק שיהיו לה מודלים רבים, אלא שלא בכולם יתקיימו אותם המשפטים).
משפט לינדסטרום קובע ששפה מסדר ראשון היא התחשיב הלוגי החזק ביותר שבמסגרתו מתקיימים הן משפט הקומפקטיות והן משפט הכיווץ של לוונהיים-סקולם.
פרדוקס סקולם
החלת משפט לוונהיים-סקולם על תורת הקבוצות האקסיומטית גוררת מסקנה הנדמית סתירתית. לפי המשפט קיים מודל בן מנייה של תורת הקבוצות. לכן כל הקבוצות במודל הן בנות מנייה (שכן כל איבר של קבוצה הוא בעצמו קבוצה במסגרת אקסיומות צרמלו-פרנקל). זאת בסתירה לכאורה למשפט קנטור שממנו עולה שקיימות קבוצות שאינן בנות מנייה.
תוצאה זו נתגלתה על ידי סקולם ב-1922 והיא קרויה על שמו "פרדוקס סקולם". סקולם גם הסביר מדוע הפרדוקס אינו סתירה באמת. הפתרון נעוץ בכך שהמונח "קבוצה" במודל של סקולם נבדל מהמשמעות החיצונית שלו. השוואת עוצמות של קבוצות מסתמכת על קיומן של פונקציות חד-חד-ערכיות ועל ביניהן. אולם פונקציות שכאלה הן בעצמן קבוצות, שאינן בהכרח כלולות כקבוצות במסגרת המודל הקטן ובן המנייה של סקולם לתורת הקבוצות. נכון שקיימת פונקציה חיצונית למודל שמתאימה בין קבוצת המספרים הטבעיים לקבוצת המספרים הממשיים במודל של סקולם, אבל הפונקציה הזו אינה קיימת בתוך המודל של סקולם, ולכן הוכחת האלכסון של קנטור עדין עובדת במודל זה.
קישורים חיצוניים
- משפט לוונהיים-סקולם, באתר MathWorld (באנגלית)
משפט לוונהיים-סקולם35140388Q1068283