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

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

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

נסמן ב-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), ערך האמת של הנוסחה \exist 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 \exist 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 הוא היחס "קטן או שווה ל-" \le.

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