תורת המודלים

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

מבוא

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

מרגע שהוכחו שני המשפטים האלו, התחום הלך וצבר תאוצה:

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

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

ניתוח מודלים על סמך עושרם המתמטי

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

כל טיפוס מגלם בתוכו "תכונה" מסוימת, שיכולה להתקיים או לא להתקיים במודל. מודלים שמקיימים את התכונה הם מודלים שמממשים את הטיפוס; השאר משמיטים אותו.

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

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

מודלים רוויים

מודל M הוא רווי אם לכל קבוצת פרמטרים A שעוצמתו קטנה מעוצמת M, מתקיים אחד מהתנאים (השקולים) הבאים:

1. לכל n טבעי, כל n-טיפוס חלקי מעל A ממומש ב-M.
2. לכל n טבעי, כל n-טיפוס שלם מעל A ממומש ב-M.
3. כל 1-טיפוס מעל A ממומש ב-M.

במובן זה, המודל מקיים "כל תכונה הגיונית". לפיכך, מודלים רויים נחשבים לעשירים.

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

קיום מודלים רוויים

לא לכל התורות קיימים מודלים רוויים, ולעיתים הקיום מותנה בהנחות תורת-קבוצתיות; למשל, מהשערת הרצף המוכללת נובע כי בהינתן מונה אינסופי $\kappa$, לכל תורה שעוצמתה קטנה ממנו, קיים מודל רווי מעוצמה $\kappa ^{+}$.

עבור תורות "טובות" מספיק לא קיים צורך בהנחות תורת קבוצתיות על מנת להוכיח קיומו של מודל רווי אינסופי. למשל, לכל תורה w-יציבה קיים מודל רווי מעוצמה k לכל מונה אינסופי k.

תכונות

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

כל מודל רווי הוא אוניברסלי - מודל המשכן בתוכו אלמנטרית כל מודל מעוצמה הקטנה מעוצמתו. השימוש המקובל ביותר במודלים רוויים הוא ביצירת מה שמכונה "מודל מפלצת" - Monster Model - מודל רווי לתורה T מעוצמה $\kappa$, שהיא מונה אינסופי גדול ככל שנרצה. בכל פעם שדנים במודלים של תורה שלמה T, ניתן להניח שהם מעוצמה הקטנה מ-$\kappa$ ולכן הם מהווים תתי מבנים אלמנטריים שלו - קיימת תועלת רבה בהתבוננות בכל המודלים כתתי מבנים של מודל עצום ומורכב אחד.

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

דוגמאות למודלים רוויים

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

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

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

מודלים ראשוניים ואטומיים

מודל של תורה T הוא ראשוני אם קיים שיכון אלמנטרי שלו בכל מודל אחר של T.

זהו המודל הפשוט ביותר של התורה - "המינימום האפשרי" שנדרש על מנת לקיים אותה - ולכן לרוב מודלים ראשוניים נחשבים למודלים דלים. מלוונהיים-סקולם נובע כי אם לתורה T קיים מודל ראשוני, אז עוצמתו היא $max\{\aleph _{0},|T|\}$.

בכל מודל ראשוני בן מניה, כל טיפוס ממומש הוא מבודד. מודל שמקיים שכל טיפוס ממומש הוא מבודד נקרא מודל אטומי, וזהו זן נוסף של מודלים דלים.

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

משפטים חשובים

משפט Ryll-Nardzewski: משפט זה מאפשר לאפיין את התורות שיש להן בדיוק מודל בן מניה אחד עד כדי איזומורפיזם; אלה התורות ה-$\!\,\aleph _{0}$-קטגוריות.

נמצאו (באופן בלתי תלוי, על ידי מספר חוקרים) התנאים השקולים הבאים לתורות בשפות בנות מניה, שיש להן מודלים אינסופיים:

1. התורה $\!\,\aleph _{0}$-קטגורית;
2. כל טיפוס מסדר n הוא מבודד (לכל n טבעי);
3. לכל n טבעי, אוסף הטיפוסים מסדר n הוא סופי;
4. לכל מספר טבעי n, יש מספר סופי של נוסחאות עם n משתנים חופשיים, עד כדי שקילות ביחס לתורה;
5. כל מודל בן מניה של התורה הוא אטומי.

משפט "לעולם לא 2" של ווט: ההצבעה על מודלים רוויים ואטומיים מאפשרת להוכיח שלא ייתכן שלתורה מסדר ראשון בשפה בת מניה יהיו שני מודלים בני מניה עד כדי איזומורפיזם (זהו משפט ווט - vaught's 'never 2' theorem). הסיבה לכך היא שניתן להוכיח שקיומם של שני מודלים בדיוק מחייבת שאחד מהם הוא ראשוני, והשני הוא רווי. מתוכם ניתן ליצור מודל שלישי, שהוא אינו ראשוני ואינו רווי, ולכן לא איזומורפי לאף אחד משני המודלים האלה.

משפט האיזומורפיזם של סקוט: נובע ממחקר מתקדם יותר בתורת המודלים, כשהמודלים אינם בלוגיקה מסדר ראשון. הרקע למשפט הוא פיתוחן של לוגיקות אינסופיות (בהן ניתן לכמת על מספר אינסופי של איברים, ולבצע קוניונקציות ודיסיונקציות אינסופיות). אחת מהן היא הלוגיקה $L(\omega _{1},\omega )$, שהיא חזקה מהלוגיקה מסדר ראשון - היא עולה עליה בכך שניתן לבצע בה קוניונקציות ודיסיונקציות בנות מניה. משפט האיזומורפיזם של סקוט אומר שלכל מבנה בן מניה יש פסוק בלוגיקה $L(\omega _{1},\omega )$ המאפיין אותו עד כדי איזומורפיזם.

השערת ווט

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

בפרט נחקרה שאלה זו לגבי הערכים שיכול לקבל $I(T,\aleph _{0})$: קל לראות שיש למונה זה חסם עליון, והוא $2^{\aleph _{0}}$. ממשפט "אף פעם לא 2" של ווט, מונה זה שונה מ-2. מצד שני, לכל מספר טבעי אחר n יש דוגמה לתורה T כך ש- $I(T,\aleph _{0})$=n. כך גם ל-$\!\,\aleph _{0}$. השערת ווט (vaught's conjecture) היא ההשערה שאלו האפשרויות היחידות: אם $I(T,\aleph _{0})$ אינו בן מניה, אז עוצמתו היא כעוצמת הרצף. קל לראות שהיא נובעת בקלות מהשערת הרצף; אך ללא הנחת השערת הרצף מתקבלת בעיה קשה מאוד לפתרון.

משפט מורלי: מורלי (Morley) הגיע לפתרון חלקי לבעיה זו. הוא הוכיח שללא השערת הרצף, אם מניחים כי $I(T,\aleph _{0})$ גדול מ- $\!\,\aleph _{1}$, אז עוצמתו היא בהכרח $2^{\aleph _{0}}$. הוכחת המשפט עושה שימוש כביר בלוגיקה אינסופית (אף על פי שניסוחו תקף ללוגיקה מסדר ראשון, ולכאורה לא מצריך מעבר כזה) ובתורת הקבוצות התיאורית.

אם כן, מחוזקים ממשפט מורלי, פתרון השערת ווט מצטמצם לשאלה האם קיימת תורה T עבורה $I(T,\aleph _{0})$ שווה ל - $\aleph _{1}$. להוכיח שלא תיתכן תורה כזו, או לחלופין לתת דוגמה לתורה כזו (בהנחת שלילת השערת הרצף), פירושו לפתור את השערת ווט.

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

לקריאה נוספת

• Chang, Chen Chung; Keisler, H. Jerome (1990) [1973]. Model Theory. Studies in Logic and the Foundations of Mathematics (3rd ed.). Elsevier. ISBN 978-0-444-88054-3.
• Hodges, Wilfrid (1997). A shorter model theory. Cambridge: Cambridge University Press. ISBN 978-0-521-58713-6.
• Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217. Springer. ISBN 0-387-98760-6.

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

מדיה וקבצים בנושא תורת המודלים בוויקישיתוף

• תורת המודלים, דף שער בספרייה הלאומית
• תורת המודלים, באתר MathWorld (באנגלית)