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

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

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

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

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

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

הוכחה: נניח בשלילה ש-$T$ לא שלמה. אז קיים פסוק $\alpha$ כך ש-$T⊬\alpha$ וגם $T⊬\mathrm{\neg }\alpha$. מכך ש-$T⊬\alpha$ נובע ש-$T,\alpha$ עקבית (חסרת סתירה), ולכן ממשפט השלמות קיים מודל $M^{\prime }\models T,\alpha$. מההנחה מודל זה אינסופי, ולכן ממשפט לוונהיים-סקולם יש מודל $M\models T,\alpha$ מעוצמה $\kappa$. באופן דומה, מ-$T⊬\mathrm{\neg }\alpha$ נקבל שיש מודל $N\models T,\mathrm{\neg }\alpha$ מעוצמה $\kappa$. אז בפרט $M,N$ מודלים ל-$T$, אבל הם לא איזומורפיים כי הם לא שקולים אלמנטרית: $M\models \alpha$ אך $N\models \mathrm{\neg }\alpha$ ולכן $N⊭\alpha$. קיבלנו סתירה להנחה ש-$T$ היא $\kappa$-קטגורית.

דוגמאות

• ניקח שפה עם סימן השוויון $=$ ושלושה סימני קבועים $c_1,c_2,c_3$. ניקח תורה עם האקסיומות הבאות: תבנית:ש $\mathrm{\exists }{x}_1\mathrm{\exists }{x}_2\mathrm{\exists }{x}_3\mathrm{\neg }(x_1=x_2)\wedge \mathrm{\neg }(x_1=x_3)\wedge \mathrm{\neg }(x_2=x_3)\wedge \mathrm{\forall }y(y=x_1\vee y=x_2\vee y=x_3)$ תבנית:ש $\mathrm{\neg }(c_1=c_2)\wedge \mathrm{\neg }(c_1=c_2)\wedge \mathrm{\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=\{\mathrm{\neg }(c_i=c_j)\mid i\ne j\}$. אז כל מודל $M$ של $T$ אינסופי, כי יש בו אינסוף איברים שונים שהם פירושי הקבועים $c_i^M$. נבחין כי $T$ לא ${\mathrm{\aleph }}_0$-קטגורית: הרי נוכל לקחת מודל $M$ שלה המכיל את פירושי הקבועים בלבד, ומודל $M^{\prime }$ המכיל איבר נוסף, ואז אין איזומורפיזם ביניהם (כי איזומורפיזם שומר על קבועים). אמנם, נבחין ש-$T$ היא $\kappa$-קטגורית לכל $\kappa >{\mathrm{\aleph }}_0$: בהינתן שני מודלים מעוצמה $\kappa$, נוכל להתאים את פירושי הקבועים זה לזה (כלומר להתאים $c_i^M\mapsto c_i^{M^{\prime }}$), ואת יתר $\kappa$ האיברים להתאים על ידי איזומורפיזם של קבוצות, שמתאים גם כאיזומורפיזם של מודלים כי אין יחסים עליהם יש לשמור ביחס אליהם. מהמשפט לעיל נקבל כי $T$ שלמה.
• נעיין בתורת המספרים עם פונקציית העוקב בלבד. נטען שהיא שלמה, ונראה זאת בעזרת המשפט שלעיל. אכן, כל מודל שלה אינסופי, שכן הוא מכיל עותק של $\mathbb{N}$, וכן מספר עותקים כלשהו של $\mathbb{Z}$. ברור שהיא לא ${\mathrm{\aleph }}_0$-קטגורית, כי יש לה מודל המכיל עותק של $\mathbb{N}$ בלבד, ומודל אחר שמכיל בנוסף עותק של $\mathbb{Z}$, ומודלים אלו לא איזומורפיים. אבל היא כן $\kappa$-קטגורית לכל $\kappa >{\mathrm{\aleph }}_0$, כי בהינתן שני מודלים מעוצמה $\kappa$, נוכל להתאים בין העותקים של $\mathbb{N}$ שבהם, וכן בין $\kappa$ העותקים של $\mathbb{Z}$ שיש בכל אחד מהם. מכאן שזו תורה שלמה.
• תורת הסדר המלא הצפוף בלי קצוות היא שלמה, שכן כל מודל שלה אינסופי, וניתן להראות שהיא ${\mathrm{\aleph }}_0$-קטגורית, על ידי בניית התאמה בין שני סדרים צפופים בני-מנייה.
• תורת המרחבים הווקטוריים מעל שדה $𝔽$ כלשהו בן מנייה היא שלמה. היא לא ${\mathrm{\aleph }}_0$-קטגורית כי למשל $𝔽,{𝔽}^2$ לא איזומורפיים, כי הם לא מאותו מימד מעל $𝔽$: הראשון ממימד $1$ ואילו השני ממימד $2$. אמנם, לכל $\kappa >{\mathrm{\aleph }}_0$ התורה כן $\kappa$-קטגורית. מכיוון שאיבר כללי במרחב הוא צירוף ליניארי סופי של איברי בסיס, נובע שכל מרחב וקטורי מעוצמה $\kappa$ הוא ממימד $\kappa$ מעל $𝔽$, ולכן יש איזומורפיזם בין כל שני מרחבים וקטוריים מעוצמה $\kappa$.
• תורת השדות הסגורים אלגברית ממציין כלשהו היא שלמה. זאת כי כל שדה סגור אלגברית הוא אינסופי (הרי בהינתן שדה $𝔽=\{a_1,\dots ,a_n\}$ סופי, הפולינום $p(x)=1+\prod _{i=1}^n(x-a_i)$ מקיים $p(a_i)=1$ לכל $1\le i\le n$ ואזי אין לו שורש בשדה, ומכאן ש-$𝔽$ לא סגור אלגברית). בנוסף, לפי משפט, בהינתן עוצמה $\kappa >{\mathrm{\aleph }}_0$ ומאפיין כלשהו, יש רק שדה סגור אלגברי אחד מעוצמה וממאפיין אלו עד כדי איזומורפיזם. לכן התורה היא $\kappa$-קטגורית לכל $\kappa >{\mathrm{\aleph }}_0$, ונובע כי היא שלמה.