מבנה (לוגיקה מתמטית)

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

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

הגדרה פורמלית

נסמן ב-$L$ שפת תחשיב יחסים כלשהי. נסמן ב-$\sigma$ את קבוצת כל סימני השפה המייצגים קבועים (האיברים קבועים, הפונקציות, והיחסים של השפה). תהי $A$ קבוצה כלשהי. מבנה ${\mathcal {A}}$ של השפה $L$ שעולמו הוא $A$ הוא פונקציה המקיימת:

• לכל סימן קבוע ${\bar {a}}\in L^{*}$ קיים $a\in A$ כך ש-${\mathcal {A}}({\bar {a}})=a$.
• לכל סימן פונקציה (פעולה) n-מקומית ${\bar {F}}$ קיימת פונקציה n-מקומית $F:A^{n}\to A$ כך ש-${\mathcal {A}}({\bar {F}})=F$.
• לכל סימן יחס n-מקומי ${\bar {R}}$ קיים יחס n-מקומי $R\subseteq A^{n}$ כך ש-${\mathcal {A}}({\bar {R}})=R$.

שלושת התנאים מצוינים לשם הנוחות, אף על פי שניתן להסתפק בתנאי האחרון בלבד, משום שפונקציות הן יחסים וקבועים הם יחסים 0-מקומיים.

הגדרה מקובלת אחרת למבנה היא כשלשה הסדורה ${\mathcal {A}}=(A,\sigma ,I)$, כאשר $I$ היא פונקציה המקיימת את התנאים הנ"ל, וקרויה פונקציית האינטרפטציה. $\sigma$ קרויה גם החתימה של ${\mathcal {A}}$ ו-$A$ קרוי העולם או היקום של ${\mathcal {A}}$.

הערה: מעתה ועד סוף הערך, נסמן את סימני הקבועים בשפה בצורה ${\bar {X}}$, ואת הקבוע (קבוע אישי, יחס או פונקציה) שהותאם לו ${\mathcal {A}}({\bar {X}})$ נסמן $X$.

ערך אמת במבנה נתון

מבנה ${\mathcal {A}}$ לשפה $L$ מפרש כל פסוק בשפה כטענה אודות העולם של ${\mathcal {A}}$. ערך האמת של הפסוק נקבע על פי נכונות הטענה לפי ${\mathcal {A}}$.

השמה במבנה ${\mathcal {A}}$ היא פונקציה המתאימה לכל סימן של משתנה בשפה $L$ איבר ב-$A$. כל השמה $\pi$ מתאימה לכל שם עצם בשפה איבר של $A$ באופן רקורסיבי כמתואר להלן:

• לכל קבוע בשפה מותאם האיבר ב-$A$ שהותאם לו על ידי המבנה: $\pi ({\bar {a}})={\mathcal {A}}({\bar {a}})=a$.
• לכל שם עצם הנוצר מפונקציה n-מקומית ${\bar {F}}(x_{1},\ldots ,x_{n})$ המופעלת על שמות העצם $x_{1},\ldots ,x_{n}$ מותאם האיבר: $\pi ({\bar {F}}(x_{1},\ldots ,x_{n}))=F(\pi (x_{1}),\ldots ,\pi (x_{n}))$

אינטואיטיבית, ההשמה $\pi$ מציבה את הערכים שהיא נתנה למשתנים בפונקציות המופעלות עליהם. לדוגמה, במבנה של המספרים הממשיים, כל השמה שכוללת את ההצבה $\pi ({\bar {x_{1}}})=1$ תקיים $\pi ({\bar {x_{1}}}+1)=2$.

בהינתן מבנה והשמה, לכל נוסחה בשפה (שאינטואיטיבית, מייצגת טענה אודות המשתנים והקבועים של השפה) ניתן להתאים ערך אמת. פורמלית, ערך האמת במבנה ${\mathcal {A}}$ תחת ההשמה $\pi$ הוא פונקציה $V_{\mathcal {A}}^{\pi }:L_{\phi }\to \{T,F\}$, כאשר $L_{\phi }$ היא קבוצת הנוסחאות ב-$L$, שמוגדרת באופן רקורסיבי:

• לכל נוסחה אטומית (כזו המתקבלת מהפעלת יחס על שמות עצם) $\phi ={\bar {R}}(x_{1},\ldots ,x_{n})$ מתקיים: $V_{\mathcal {A}}^{\pi }(\phi )=T$ אם ורק אם מתקיים היחס $R(\pi (x_{1}),\ldots ,\pi (x_{n}))$ בעולם $A$.
• לכל נוסחה או זוג נוסחאות, ערך האמת של הנוסחאות המתקבלות מהפעלת הקשרים הלוגיים של השפה על הנוסחאות נקבע על פי טבלת האמת של הקשרים.
• לכל נוסחה $\phi (x)$, ערך האמת של הנוסחה $\forall x\phi (x)$ הוא $T$ אם ורק אם לכל $a\in A$ מתקיים $V_{\mathcal {A}}^{\pi }(\phi (a))=T$.
• לכל נוסחה $\phi (x)$, ערך האמת של הנוסחה $\exists x\phi (x)$ הוא $T$ אם ורק אם קיים $a\in A$ כך שמתקיים $V_{\mathcal {A}}^{\pi }(\phi (a))=T$.

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

דוגמה

נבחן את השפה מסדר ראשון $L$ שכוללת שני קבועים ${\bar {0}}$ ו-${\bar {1}}$, שתי פונקציות דו-מקומיות $\oplus$ ו-$\otimes$ ושני יחסים דו-מקומיים $\equiv$ ו-$\prec$. כמו כן נרשה את השימוש בסימון המקוצר $\not \equiv$ שמסמן את היחס $\neg (x\equiv y)$. נתאר שלוש דוגמאות למבנים של השפה $L$.

מבנה 1: חוג המספרים השלמים

חוג המספרים השלמים הוא מבנה ${\mathcal {Z}}$ שעולמו הוא הקבוצה $\mathbb {Z} =\{\ldots ,-2,-1,0,1,2,\ldots \}$. הקבועים ${\bar {0}}$ ו-${\bar {1}}$ מתפרשים כמספרים 0 ו-1, הפונקציות $\oplus$ ו-$\otimes$ מתפרשות כפעולת החיבור ופעולת הכפל הרגילות בין מספרים שלמים. $\equiv$ הוא יחס השוויון הרגיל ואילו $\prec$ הוא היחס "מחלק את".

נדגים כמה פסוקים ב-$L$ ואת ערך האמת שלהם ב-${\mathcal {Z}}$:

• ${\bar {1}}\prec {\bar {0}}$ - פסוק אמיתי הקובע ש-1 מחלק את 0.
• $\forall x(x\oplus x\equiv x)$ - פסוק שקרי הקובע שכל מספר שווה לסכום שלו עם עצמו.
• $\forall x((x\not \equiv {\bar {0}})\to \exists y(x\otimes y\equiv {\bar {1}}))$ - הפסוק קובע שלכל מספר שונה מאפס קיים מספר הופכי. המשפט שקרי ב-${\mathcal {Z}}$ כי למשל ל-2 אין הופכי (חצי אינו מספר שלם, ולכן אינו כלול בעולם $\mathbb {Z}$).

מבנה 2: שדה המספרים הממשיים

שדה המספרים הממשיים הוא מבנה ${\mathcal {R}}$ שעולמו הוא קבוצת המספרים על הישר הממשי $\mathbb {R}$. כמו קודם, הקבועים ${\bar {0}}$ ו-${\bar {1}}$ מתפרשים כמספרים 0 ו-1, הפונקציות $\oplus$ ו-$\otimes$ מתפרשות כפעולת החיבור ופעולת הכפל הרגילות בין מספרים ממשיים. $\equiv$ הוא יחס השוויון הרגיל ואילו $\prec$ הוא היחס "קטן או שווה ל-" $\leq$.

נתאר את ערך האמת ב-${\mathcal {R}}$ של הפסוקים ב-$L$ שתוארו קודם:

• ${\bar {1}}\prec {\bar {0}}$ - פסוק שקרי הקובע ש-1 קטן מ-0.
• $\forall x(x\oplus x\equiv x)$ - פסוק שקרי הקובע שכל מספר שווה לסכום שלו עם עצמו.
• $\forall x((x\not \equiv {\bar {0}})\to \exists y(x\otimes y\equiv {\bar {1}}))$ - הפסוק קובע שלכל מספר שונה מאפס קיים מספר הופכי. המשפט אמיתי ב-${\mathcal {R}}$.

מבנה 3: קבוצת חזקה

נניח X היא קבוצה עם שני איברים לפחות. נגדיר מבנה ${\mathcal {P}}$ באופן הבא: העולם של המבנה הוא $\wp (X)$, קבוצת החזקה של X, שאיבריה הם כל התת-קבוצות של X. הקבועים ${\bar {0}}$ ו-${\bar {1}}$ מתפרשים כקבוצה הריקה וכקבוצה X בהתאמה. הפונקציות $\oplus$ ו-$\otimes$ מתפרשות כפעולת האיחוד ופעולת החיתוך בין קבוצות. $\equiv$ הוא יחס השוויון הרגיל בין קבוצות ואילו $\prec$ הוא היחס "מוכל ב-".

נתאר את ערך האמת ב-${\mathcal {P}}$ של הפסוקים ב-$L$ שתוארו קודם:

• ${\bar {1}}\prec {\bar {0}}$ - פסוק שקרי הקובע ש-X מוכל בקבוצה הריקה (הנחנו שב-X יש איברים).
• $\forall x(x\oplus x\equiv x)$ - פסוק אמיתי הקובע שלכל תת-קבוצה שווה לאיחוד שלה עם עצמה.
• $\forall x((x\not \equiv {\bar {0}})\to \exists y(x\otimes y\equiv {\bar {1}}))$ - הפסוק קובע שלכל תת-קבוצה שאינה ריקה יש איבר הופכי ביחס לפעולת החיתוך. המשפט שקרי ב-${\mathcal {P}}$. נקח $x\in X$, אז ליחידון $\{x\}$ אין הופכי ביחס לחיתוך (נזכור כי הנחנו שב-X יש לפחות שני איברים).

תת-מבנה

אומרים שהמבנה ${\mathcal {B}}$ הוא תת-מבנה של ${\mathcal {A}}$ אם העולם של ${\mathcal {B}}$ חלקי לעולם של ${\mathcal {A}}$ וכולל את כל הקבועים האישיים של ${\mathcal {A}}$, הפונקציות והיחסים של ${\mathcal {B}}$ הם הפונקציות והיחסים של ${\mathcal {A}}$ כשמצמצמים אותם לעולם של ${\mathcal {B}}$, והפונקציות המצומצמות סגורות. למשל אם נחליף את המשמעות של $\prec$ במבנה 1 שהודגם קודם (חוג המספרים השלמים) כך שייתפרש כיחס "קטן או שווה ל-", נקבל תת-מבנה של מבנה 2 (שדה המספרים הממשיים).

יהי ${\mathcal {A}}$ מבנה שעולמו $A$. על תת-קבוצה $B\subseteq A$ נאמר שהיא תת-קבוצה סגורה ב-${\mathcal {A}}$ אם כל קבוע אישי של ${\mathcal {A}}$ נמצא ב-$B$ ו-$B$ סגורה תחת כל הפונקציות של ${\mathcal {A}}$. לכל קבוצה סגורה $B$ יש תת-מבנה יחיד של ${\mathcal {A}}$ שעולמו הוא $B$. תת-מבנה זה נקרא התת-מבנה הנקבע על ידי $B$. העולם של כל תת-מבנה הוא קבוצה סגורה.

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