תורת המודלים

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

מבוא

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

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

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

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

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

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

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

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

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

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

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

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

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

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

לא לכל התורות קיימים מודלים רוויים, ולעיתים הקיום מותנה בהנחות תורת-קבוצתיות; למשל, מהשערת הרצף המוכללת נובע כי בהינתן מונה אינסופי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} , לכל תורה שעוצמתה קטנה ממנו, קיים מודל רווי מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa^+} .

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

תכונות

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

כל מודל רווי הוא אוניברסלי - מודל המשכן בתוכו אלמנטרית כל מודל מעוצמה הקטנה מעוצמתו. השימוש המקובל ביותר במודלים רוויים הוא ביצירת מה שמכונה "מודל מפלצת" - Monster Model - מודל רווי לתורה T מעוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} , שהיא מונה אינסופי גדול ככל שנרצה. בכל פעם שדנים במודלים של תורה שלמה T, ניתן להניח שהם מעוצמה הקטנה מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} ולכן הם מהווים תתי מבנים אלמנטריים שלו - קיימת תועלת רבה בהתבוננות בכל המודלים כתתי מבנים של מודל עצום ומורכב אחד.

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

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

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

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

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

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

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

זהו המודל הפשוט ביותר של התורה - "המינימום האפשרי" שנדרש על מנת לקיים אותה - ולכן לרוב מודלים ראשוניים נחשבים למודלים דלים. מלוונהיים-סקולם נובע כי אם לתורה T קיים מודל ראשוני, אז עוצמתו היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle max\{\aleph_0,|T|\}} .

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

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

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

משפט Ryll-Nardzewski: משפט זה מאפשר לאפיין את התורות שיש להן בדיוק מודל בן מניה אחד עד כדי איזומורפיזם; אלה התורות ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \aleph_0} -קטגוריות.

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

  1. התורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \aleph_0} -קטגורית;
  2. כל טיפוס מסדר n הוא מבודד (לכל n טבעי);
  3. לכל n טבעי, אוסף הטיפוסים מסדר n הוא סופי;
  4. לכל מספר טבעי n, יש מספר סופי של נוסחאות עם n משתנים חופשיים, עד כדי שקילות ביחס לתורה;
  5. כל מודל בן מניה של התורה הוא אטומי.

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

משפט האיזומורפיזם של סקוט: נובע ממחקר מתקדם יותר בתורת המודלים, כשהמודלים אינם בלוגיקה מסדר ראשון. הרקע למשפט הוא פיתוחן של לוגיקות אינסופיות (בהן ניתן לכמת על מספר אינסופי של איברים, ולבצע קוניונקציות ודיסיונקציות אינסופיות). אחת מהן היא הלוגיקה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(\omega_1,\omega)} , שהיא חזקה מהלוגיקה מסדר ראשון - היא עולה עליה בכך שניתן לבצע בה קוניונקציות ודיסיונקציות בנות מניה. משפט האיזומורפיזם של סקוט אומר שלכל מבנה בן מניה יש פסוק בלוגיקה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(\omega_1,\omega)} המאפיין אותו עד כדי איזומורפיזם.

השערת ווט

שאלות רבות עולות בקשר למספר המודלים מעוצמה k, עד כדי איזומורפיזם, שיש לתורה T (לצורך הפשטות דנים בתורה שהיא בת מניה מסדר ראשון, ובעלת מודלים אינסופיים). נסמן מספר זה ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(T,k)} .

בפרט נחקרה שאלה זו לגבי הערכים שיכול לקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(T,\aleph_0)} : קל לראות שיש למונה זה חסם עליון, והוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0}} . ממשפט "אף פעם לא 2" של ווט, מונה זה שונה מ-2. מצד שני, לכל מספר טבעי אחר n יש דוגמה לתורה T כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(T,\aleph_0)} =n. כך גם ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \aleph_0} . השערת ווט (vaught's conjecture) היא ההשערה שאלו האפשרויות היחידות: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(T,\aleph_0)} אינו בן מניה, אז עוצמתו היא כעוצמת הרצף. קל לראות שהיא נובעת בקלות מהשערת הרצף; אך ללא הנחת השערת הרצף מתקבלת בעיה קשה מאד לפתרון.

משפט מורלי: מורלי (Morley) הגיע לפתרון חלקי לבעיה זו. הוא הוכיח שללא השערת הרצף, אם מניחים כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(T,\aleph_0)} גדול מ- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \aleph_1} , אז עוצמתו היא בהכרח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0}} . הוכחת המשפט עושה שימוש כביר בלוגיקה אינסופית (אף על פי שניסוחו תקף ללוגיקה מסדר ראשון, ולכאורה לא מצריך מעבר כזה) ובתורת הקבוצות התיאורית.

אם כן, מחוזקים ממשפט מורלי, פתרון השערת ווט מצטמצם לשאלה האם קיימת תורה T עבורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I(T,\aleph_0)} שווה ל - הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_1} . להוכיח שלא תיתכן תורה כזו, או לחלופין לתת דוגמה לתורה כזו (בהנחת שלילת השערת הרצף), פירושו לפתור את השערת ווט.

בעשור הקודם מצא החוקר רובין נייט (Robin Knight) דוגמה נגדית להשערת ווט[1]. השערת ווט הוכחה עבור מחלקות מרכזיות של תורות, בהן תורות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

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

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

הערות שוליים

  1. ^ Knight, R. W. (2002), The Vaught Conjecture: A Counterexample, manuscript, http://www.maths.ox.ac.uk/~knight/stuff/example.ps.
אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=תורת_המודלים&oldid=756365"