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

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

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

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

היסטוריה

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

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

רקע

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

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

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

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

לכל נוסחה ${\displaystyle \phi (x,x_{1},\ldots ,x_{n})}$ בשפה ${\displaystyle L}$, אשר ${\displaystyle x,x_{1},\ldots ,x_{n}}$ הם המשתנים החופשיים בה, ולכל ${\displaystyle b_{1},\ldots ,b_{n}\in B}$, אם קיים ${\displaystyle a\in A}$ כך ש-${\displaystyle \phi (a,b_{1},\ldots ,b_{n})}$ נכון ב-${\displaystyle {\mathcal {A}}}$, אז קיים ${\displaystyle b\in B}$ כך ש-${\displaystyle \phi (b,b_{1},\ldots ,b_{n})}$ נכון ב-${\displaystyle {\mathcal {A}}}$.

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

תנאי המשפט

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

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

הוכחה

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

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

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

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

הוכחת משפט הכיווץ

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

לכל נוסחה ${\displaystyle \phi (x,x_{1},\ldots ,x_{n})}$ נתאים פונקציה ${\displaystyle f_{\phi }:A^{n}\to A}$ הנקראת פונקציית סקולם. פונקציית סקולם מוגדרת כך: לכל ${\displaystyle a_{1},\ldots ,a_{n}\in A}$ מגדירים ${\displaystyle f_{\phi }(a_{1},\ldots ,a_{n})=a}$, כאשר ${\displaystyle a\in A}$ הוא איבר כך שמתקיים ${\displaystyle \phi (a,a_{1},\ldots ,a_{n})}$, אם ישנו איבר כזה, או סתם איבר שרירותי אם אין איבר כזה (בחירת האיברים מצריכה את אקסיומת הבחירה). נסמן ב-${\displaystyle S}$ את קבוצת פונקציות סקולם של כל הנוסחאות בשפה ${\displaystyle L}$. יש ${\displaystyle \aleph _{0}}$ נוסחאות בשפה ${\displaystyle L}$ (כי קבוצת המילים מעל שפה בת מנייה היא בת מנייה) ולכן ${\displaystyle |S|=\aleph _{0}}$.

נגדיר כעת ברקורסיה סדרת קבוצות. ${\displaystyle B_{0}}$ תהיה תת-קבוצה כלשהי של ${\displaystyle A}$ שעוצמתה ${\displaystyle \mu }$. נגדיר:

${\displaystyle 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\}}$

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

נוכיח באינדוקציה כי לכל ${\displaystyle n}$ טבעי, ${\displaystyle |B_{n}|=\mu }$.

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

נגדיר ${\displaystyle B=\bigcup _{n=0}^{\infty }B_{n}}$. מהגדרת ${\displaystyle B}$ מתקיים ${\displaystyle B\subseteq A}$ וכן ${\displaystyle |B|=\aleph _{0}\cdot \mu =\mu }$.

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

נראה כי ${\displaystyle B}$ קבוצה סגורה ב-${\displaystyle {\mathcal {A}}}$. לכל פעולה ${\displaystyle F}$ n-מקומית בשפה ${\displaystyle L}$ נגדיר נוסחה ${\displaystyle \phi _{F}(x,x_{1},\ldots ,x_{n})}$ שהיא הנוסחה ${\displaystyle x=F(x_{1},\ldots ,x_{n})}$. מהסגירות של ${\displaystyle B}$ ביחס לפונקציות סקולם נקבל ש-${\displaystyle B}$ סגורה ביחס ל-${\displaystyle F}$ - לכל ${\displaystyle b_{1},\ldots ,b_{n}\in B}$ מתקיים: ${\displaystyle F(b_{1},\ldots ,b_{n})=f_{\phi _{F}}(b_{1},\ldots ,b_{n})\in B}$.

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

לכל נוסחה ${\displaystyle \phi (x,x_{1},\ldots ,x_{n})}$ ולכל ${\displaystyle b_{1},\ldots ,b_{n}\in B}$, אם קיים ${\displaystyle a\in A}$ כך שמתקיים ${\displaystyle \phi (a,b_{1},\ldots ,b_{n})}$, אז לפי הגדרת פונקציית סקולם קיים ${\displaystyle b=f_{\phi }(b_{1},\ldots ,b_{n})\in B}$ כך שמתקיים ${\displaystyle \phi (b,b_{1},\ldots ,b_{n})}$. לכן לפי מבחן טרסקי-ווט ${\displaystyle {\mathcal {B}}}$ תת-מבנה אלמנטרי של ${\displaystyle {\mathcal {A}}}$.

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

הוכחת משפט הניפוח

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

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

נשתמש במשפט הקומפקטיות כדי להראות ש-${\displaystyle \Gamma }$ עקבית בשפה ${\displaystyle L_{I}}$. תהי ${\displaystyle \Gamma _{0}}$ תת-קבוצה סופית של ${\displaystyle \Gamma }$. קיימת קבוצה מהצורה ${\displaystyle \Gamma _{1}=T\cup \Sigma _{0}}$, כך ש-${\displaystyle \Sigma _{0}}$ היא תת-קבוצה סופית של ${\displaystyle \Sigma }$, ומתקיים ${\displaystyle \Gamma _{0}\subseteq \Gamma _{1}}$. ב-${\displaystyle \Sigma _{0}}$ יש רק מספר סופי של פסוקים מהצורה ${\displaystyle c_{i}\neq c_{j}}$. נסמן את קבוצת כל ה-${\displaystyle c_{i}}$ שמופיעים בפסוק שכזה ב-${\displaystyle C}$.

נגדיר מבנה ${\displaystyle {\mathcal {A}}^{*}}$ בשפה ${\displaystyle L_{I}}$ שפונקציית המבנה שלו מתלכדת עם זו של ${\displaystyle {\mathcal {A}}}$ לכל הקובעים ב-${\displaystyle L}$, ובנוסף מוגדרת באופן שרירותי לכל קבוע ${\displaystyle c_{i}}$ ב-${\displaystyle L_{I}}$, מלבד לקבועים שב-${\displaystyle C}$, שאותם היא מפרשת כאיברים שונים זה מזה ב-${\displaystyle A}$ (ייתכן משום ש-${\displaystyle C}$ סופית, ואילו ${\displaystyle A}$ אינסופית).

${\displaystyle {\mathcal {A}}^{*}}$ מודל של ${\displaystyle \Gamma _{1}}$ (כי ${\displaystyle {\mathcal {A}}}$ הוא מודל של ${\displaystyle T}$, וכל הפסוקים ב-${\displaystyle \Sigma _{0}}$ שקובעים שאיברי ${\displaystyle C}$ שונים זה מזה, אכן מתקיימים), לכן היא גם מודל של ${\displaystyle \Gamma _{0}}$, ועל כן ${\displaystyle \Gamma _{0}}$ עקבית. נקבל ממשפט הקומפקטיות ש-${\displaystyle \Gamma }$ עקבית בשפה ${\displaystyle L_{I}}$. נסמן ב-${\displaystyle {\mathcal {B}}}$ מודל של ${\displaystyle \Gamma }$ בשפה ${\displaystyle L_{I}}$. כל הפסוקים ב-${\displaystyle \Gamma }$ נכונים ב-${\displaystyle {\mathcal {B}}}$, ובפרט כל פסוקי ${\displaystyle \Sigma }$ שקובעים שיש ${\displaystyle |I|}$ איברים השונים זה מזה נכונים. לכן ${\displaystyle \mu =|I|\leq |B|}$.

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

מסקנות

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

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

מסקנה נוספת ממשפט לוונהיים-סקולם היא שאם ${\displaystyle T}$ תורה ${\displaystyle \aleph _{0}}$-קטגורית (יש לה מודל יחיד עד כדי איזומורפיזם מעוצמה ${\displaystyle \aleph _{0}}$), ואין לה מודלים סופיים, אז ${\displaystyle T}$ תורה שלמה. זאת משום שאם ${\displaystyle {\mathcal {A}},{\mathcal {B}}}$ הם מודלים כלשהם של ${\displaystyle T}$, אז לפי הנתון הם אינם סופיים, ולכן לפי משפט הכיווץ יש להם תת-מבנים אלמנטריים ${\displaystyle {\mathcal {A}}_{0},{\mathcal {B}}_{0}}$ מעוצמה ${\displaystyle \aleph _{0}}$. מכיוון ש-${\displaystyle T}$ תורה ${\displaystyle \aleph _{0}}$-קטגורית נובע מכך ש-${\displaystyle {\mathcal {A}}_{0},{\mathcal {B}}_{0}}$ איזומורפיים. לכן אותם משפטים נכונים הן ב-${\displaystyle {\mathcal {A}}}$ והן ב-${\displaystyle {\mathcal {B}}}$, וכל המשפטים הללו בהכרח נובעים מ-${\displaystyle T}$.

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

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

פרדוקס סקולם

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

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

קישורים חיצוניים

• משפט לוונהיים-סקולם, באתר MathWorld (באנגלית)