תורת המודלים

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

תורת המודלים היא תחום במתמטיקה העוסק בחקר מודלים של תורות מתמטיות, תוך שימוש בכלים מלוגיקה מתמטית. מושאי המחקר העיקריים בתחום זה הם מבנים בשפות פורמליות, לרוב בלוגיקה מסדר ראשון. כיום מקובלת חלוקה של תורת המודלים לתורת המודלים הקלאסית (ובפרט 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 שונה מכל איברי המבנה).

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

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

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

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

דוגמאות למודלים רוויים:[עריכת קוד מקור | עריכה]

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) דוגמה נגדית להשערת ווט‏[1]. יש לציין שהשערת ווט הוכחה עבור מחלקות מרכזיות של תורות, בהן תורות \omega-יציבות, תורות o-מינימליות, תורות של גרפים ומחלקות נוספות. לכן, עד העשור הקודם, הדעה הרווחת הייתה שהשערת ווט נכונה.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Knight, R. W. (2002), The Vaught Conjecture: A Counterexample, manuscript, http://www.maths.ox.ac.uk/~knight/stuff/example.ps.

לקריאה נוספת[עריכת קוד מקור | עריכה]