משפט לוונהיים-סקולם
ויקיפדיה האנציקלופדיה encyclopedia
בלוגיקה מתמטית, משפט לוונהיים-סקולם הוא משפט יסודי בתורת המודלים שקובע שאם לתורה בשפה בת מנייה מסדר ראשון יש מודל אינסופי, אז יש לה מודל מכל עוצמה אינסופית. המשפט מראה שלתורה בת מנייה מסדר ראשון אין שליטה על העוצמה של המודלים האינסופיים שלה (בניגוד ללוגיקה מסדר שני), ושכל תורה שכזו שיש לה מודל אינסופי אינה קטגורית (משמע יש לה יותר ממודל אחד עד כדי איזומורפיזם).
בערך זה |
גרסה חזקה יותר של המשפט קובעת שלכל תורה בשפה מסדר ראשון (שאינה בת מנייה בהכרח) שיש לה מודל אינסופי, יש לה מודל מכל עוצמה אינסופית הגדולה מעוצמת קבוצת הקבועים שלה.
כמוסבר בהמשך, משפט לוונהיים-סקולם הוא תוצר של שני משפטים, משפט הכיווץ ומשפט הניפוח. ב-1915 הוכיח המתמטיקאי הגרמני לאופולד לוונהיים גרסה מוקדמת של משפט הכיווץ, שלכל תורה עם מודל אינסופי יש מודל בן מנייה. אולם בהוכחה של לוונהיים הייתה טעות. ב-1920 הציג המתמטיקאי הנורווגי תורלף סקולם הוכחה חלופית ונכונה.
המשפט המלא הוכח ב-1936 על ידי המתמטיקאי הרוסי אנטולי מלצב, לאחר שהוכיח את הגרסה המלאה של משפט הקומפקטיות הדרושה בהוכחת משפט הניפוח. במאמרו הוא ציין שלטענת סקולם המשפט המלא הוכח עוד קודם לכן על ידי אלפרד טרסקי במהלך סמינר ב-1928. אולם טרסקי לא זכר את הוכחתו ולא ברור כיצד יכול היה להוכיח את המשפט ללא משפט הקומפקטיות.
מודל של תורה בשפה מסדר ראשון הוא מבנה (המורכב מקבוצה ומפונקציה המפרשת את קבועי השפה כקבועים ויחסים בקבוצה) שמקיים את כל הפסוקים בשפה. הקבוצה שעומדת בבסיס מבנה נקראת העולם של , ונסמנו . העוצמה של היא העוצמה של .
מבנה הוא תת-מבנה של אם , ופונקציית המבנה של היא צמצום של פונקציית המבנה של ל-. קבוצה נקראת קבוצה סגורה ב- אם סגורה תחת כל הפעולות (פונקציות) בשפה (ובפרט מכילה את כל האיברים ב- המתפרשים כקבועים של , שהם הפעולות ה-0 מקומיות). אם הוא תת-קבוצה סגורה של , אז התת-מבנה שנקבע על ידי הוא התת-מבנה היחיד שעולמו הוא ושפונקציית המבנה שלו היא צמצום פונקציית המבנה של ל-.
תת-מבנה של מבנה נקרא תת-מבנה אלמנטרי אם לכל השמה אפשרית כל הנוסחאות בשפה שנכונות ב-, נכונות גם ב- (אינטואיטיבית, כל טענה שנכונה במבנה נכונה גם בכל תת-מבנה אלמנטרי שלו, ולהפך). מן ההגדרה נובע שאם מודל של , גם התת-מבנה האלמנטרי הוא מודל של .
מבחן טרסקי-ווט קובע שתנאי הכרחי ומספיק לכך שתת-מבנה של הוא תת-מבנה אלמנטרי, הוא:
- לכל נוסחה בשפה , אשר הם המשתנים החופשיים בה, ולכל , אם קיים כך ש- נכון ב-, אז קיים כך ש- נכון ב-.
קבוצת פסוקים היא עקבית אם קיים לה מודל (ראו משפט השלמות של גדל). משפט הקומפקטיות קובע ש- עקבית אם ורק אם כל תת-קבוצה סופית שלה עקבית.
לא ניתן להחליש את תנאי המשפט. אם לתורה יש מודל סופי הדבר אינו גורר קיום מודל אינסופי. זאת משום שבכל שפה מסדר ראשון יש יחס שוויון, ולכן התורה יכולה לכלול פסוק שאומר שבכל קבוצה של n+1 איברים יש שניים שווים (ומכאן שכל מודל יש לכל היותר n איברים). גם קיומו של מודל אינסופי לא גורר קיום מודל סופי. למשל כל קבוצה אינסופית היא מודל לתורה שלכל n כוללת את הפסוק הקובע שיש לפחות n איברים שונים. מצד שני, לתורה זו אין אף מודל סופי.
אם שפת התורה אינה בת-מנייה, אז מתקיימת גרסה מוכללת של משפט לוונהיים-סקולם הקובעת שקיים מודל מכל עוצמה שאינה קטנה מעוצמת השפה. ההוכחה של המשפט המוכלל אנלוגית למקרה הבן מנייה.