קטגוריות של תורות
![]() |
ערך ללא מקורות
| |
ערך ללא מקורות | |
בלוגיקה מתמטית, אומרים שתורה $ 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} $, ונובע כי היא שלמה.

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] קטגוריות של תורות31399754