קטגוריות של תורות

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

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

ניתן הגדרה עדינה יותר: אומרים שתורה $T$ היא $\kappa$-קטגורית אם כל המודלים שלה מעוצמה $\kappa$ איזומורפיים.

שימוש ב-$\kappa$-קטגוריות ככלי להוכחת שלמות של תורות

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

הוכחה: נניח בשלילה ש-$T$ לא שלמה. אז קיים פסוק $\alpha$ כך ש-$T\nvdash \alpha$ וגם $T\nvdash \neg \alpha$. מכך ש-$T\nvdash \alpha$ נובע ש-$T,\alpha$ עקבית (חסרת סתירה), ולכן ממשפט השלמות קיים מודל $M'\vDash T,\alpha$. מההנחה מודל זה אינסופי, ולכן ממשפט לוונהיים-סקולם יש מודל $M\vDash T,\alpha$ מעוצמה $\kappa$. באופן דומה, מ-$T\nvdash \neg \alpha$ נקבל שיש מודל $N\vDash T,\neg \alpha$ מעוצמה $\kappa$. אז בפרט $M,N$ מודלים ל-$T$, אבל הם לא איזומורפיים כי הם לא שקולים אלמנטרית: $M\vDash \alpha$ אך $N\vDash \neg \alpha$ ולכן $N\nvDash \alpha$. קיבלנו סתירה להנחה ש-$T$ היא $\kappa$-קטגורית.

דוגמאות

• ניקח שפה עם סימן השוויון $=$ ושלושה סימני קבועים $c_{1},c_{2},c_{3}$. ניקח תורה עם האקסיומות הבאות:
  $\exists x_{1}\,\exists x_{2}\,\exists x_{3}\,\neg (x_{1}=x_{2})\wedge \neg (x_{1}=x_{3})\wedge \neg (x_{2}=x_{3})\wedge \forall y\,(y=x_{1}\vee y=x_{2}\vee y=x_{3})$
  $\neg (c_{1}=c_{2})\wedge \neg (c_{1}=c_{2})\wedge \neg (c_{2}=c_{3})$
  זו תורה קטגורית, כי בכל מודל $M$ שלה יש שלושה איברים בדיוק (מהאקסיומה הראשונה), והם פירושי הקבועים $c_{1}^{M},c_{2}^{M},c_{3}^{M}$, ששונים זה מזה (מהאקסיומה השנייה).
• אם בדוגמה הקודמת היינו מוותרים על האקסיומה השנייה, אז התורה לא הייתה קטגורית, כי קיים מודל בו כל סימני הקבועים מתאימים לאותו איבר, למשל (כלומר $c_{1}^{M}=c_{2}^{M}=c_{3}^{M}$).
• ניקח הפעם שפה עם סימן השוויון $=$, ועם סימני קבועים $c_{1},c_{2},c_{3},\dots$. ניקח את התורה הבאה:
  $T=\{\neg (c_{i}=c_{j})\mid i\neq j\}$. אז כל מודל $M$ של $T$ אינסופי, כי יש בו אינסוף איברים שונים שהם פירושי הקבועים $c_{i}^{M}$. נבחין כי $T$ לא $\aleph _{0}$-קטגורית: הרי נוכל לקחת מודל $M$ שלה המכיל את פירושי הקבועים בלבד, ומודל $M'$ המכיל איבר נוסף, ואז אין איזומורפיזם ביניהם (כי איזומורפיזם שומר על קבועים). אמנם, נבחין ש-$T$ היא $\kappa$-קטגורית לכל $\kappa >\aleph _{0}$: בהינתן שני מודלים מעוצמה $\kappa$, נוכל להתאים את פירושי הקבועים זה לזה (כלומר להתאים $c_{i}^{M}\mapsto c_{i}^{M'}$), ואת יתר $\kappa$ האיברים להתאים על ידי איזומורפיזם של קבוצות, שמתאים גם כאיזומורפיזם של מודלים כי אין יחסים עליהם יש לשמור ביחס אליהם. מהמשפט לעיל נקבל כי $T$ שלמה.
• נעיין בתורת המספרים עם פונקציית העוקב בלבד. נטען שהיא שלמה, ונראה זאת בעזרת המשפט שלעיל. אכן, כל מודל שלה אינסופי, שכן הוא מכיל עותק של $\mathbb {N}$, וכן מספר עותקים כלשהו של $\mathbb {Z}$. ברור שהיא לא $\aleph _{0}$-קטגורית, כי יש לה מודל המכיל עותק של $\mathbb {N}$ בלבד, ומודל אחר שמכיל בנוסף עותק של $\mathbb {Z}$, ומודלים אלו לא איזומורפיים. אבל היא כן $\kappa$-קטגורית לכל $\kappa >\aleph _{0}$, כי בהינתן שני מודלים מעוצמה $\kappa$, נוכל להתאים בין העותקים של $\mathbb {N}$ שבהם, וכן בין $\kappa$ העותקים של $\mathbb {Z}$ שיש בכל אחד מהם. מכאן שזו תורה שלמה.
• תורת הסדר המלא הצפוף בלי קצוות היא שלמה, שכן כל מודל שלה אינסופי, וניתן להראות שהיא $\aleph _{0}$-קטגורית, על ידי בניית התאמה בין שני סדרים צפופים בני-מנייה.
• תורת המרחבים הווקטוריים מעל שדה $\mathbb {F}$ כלשהו בן מנייה היא שלמה. היא לא $\aleph _{0}$-קטגורית כי למשל $\mathbb {F} ,\mathbb {F} ^{2}$ לא איזומורפיים, כי הם לא מאותו מימד מעל $\mathbb {F}$: הראשון ממימד $1$ ואילו השני ממימד $2$. אמנם, לכל $\kappa >\aleph _{0}$ התורה כן $\kappa$-קטגורית. מכיוון שאיבר כללי במרחב הוא צירוף ליניארי סופי של איברי בסיס, נובע שכל מרחב וקטורי מעוצמה $\kappa$ הוא ממימד $\kappa$ מעל $\mathbb {F}$, ולכן יש איזומורפיזם בין כל שני מרחבים וקטוריים מעוצמה $\kappa$.
• תורת השדות הסגורים אלגברית ממציין כלשהו היא שלמה. זאת כי כל שדה סגור אלגברית הוא אינסופי (הרי בהינתן שדה $\mathbb {F} =\{a_{1},\dots ,a_{n}\}$ סופי, הפולינום $p(x)=1+\prod _{i=1}^{n}(x-a_{i})$ מקיים $p(a_{i})=1$ לכל $1\leq i\leq n$ ואזי אין לו שורש בשדה, ומכאן ש-$\mathbb {F}$ לא סגור אלגברית). בנוסף, לפי משפט, בהינתן עוצמה $\kappa >\aleph _{0}$ ומאפיין כלשהו, יש רק שדה סגור אלגברי אחד מעוצמה וממאפיין אלו עד כדי איזומורפיזם. לכן התורה היא $\kappa$-קטגורית לכל $\kappa >\aleph _{0}$, ונובע כי היא שלמה.

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31399754קטגוריות של תורות