Loading AI tools
התאמה המפרשת את הביטויים של שפה פורמלית כביטויים אודות מבנה מתמטי מסוים מוויקיפדיה, האנציקלופדיה החופשית
בלוגיקה מתמטית, מבנה הוא התאמה המפרשת את הביטויים של שפה פורמלית כביטויים אודות מבנה מתמטי מסוים. המבנה הוא הנותן משמעות לרצפי אותיות בשפה הפורמלית ומפרש אותם כטענות על יחסים המתקיימים בין אובייקטים מתמטיים.
בערך זה |
נסמן ב- שפת תחשיב יחסים כלשהי. נסמן ב- את קבוצת כל סימני השפה המייצגים קבועים (האיברים הקבועים, הפונקציות, והיחסים של השפה). תהי קבוצה כלשהי. מבנה של השפה שעולמו הוא הוא פונקציה המקיימת:
שלושת התנאים מצוינים לשם הנוחות, אף על פי שניתן להסתפק בתנאי האחרון בלבד, משום שפונקציות הן יחסים וקבועים הם יחסים 0-מקומיים.
הגדרה מקובלת אחרת למבנה היא כשלשה הסדורה , כאשר היא פונקציה המקיימת את התנאים הנ"ל, וקרויה פונקציית האינטרפרטציה. קרויה גם החתימה של ו- קרוי העולם או היקום של .
הערה: מעתה ועד סוף הערך, נסמן את סימני הקבועים בשפה בצורה , ואת הקבוע (קבוע אישי, יחס או פונקציה) שהותאם לו נסמן .
מבנה לשפה מפרש כל פסוק בשפה כטענה אודות העולם של . ערך האמת של הפסוק נקבע על פי נכונות הטענה לפי .
השמה במבנה היא פונקציה המתאימה לכל סימן של משתנה בשפה איבר ב-. כל השמה מתאימה לכל שם עצם בשפה איבר של באופן רקורסיבי כמתואר להלן:
אינטואיטיבית, ההשמה מציבה את הערכים שהיא נתנה למשתנים בפונקציות המופעלות עליהם. לדוגמה, במבנה של המספרים הממשיים, כל השמה שכוללת את ההצבה תקיים .
בהינתן מבנה והשמה, לכל נוסחה בשפה (שאינטואיטיבית, מייצגת טענה אודות המשתנים והקבועים של השפה) ניתן להתאים ערך אמת. פורמלית, ערך האמת במבנה תחת ההשמה הוא פונקציה , כאשר היא קבוצת הנוסחאות ב-, שמוגדרת באופן רקורסיבי:
מבין כל הנוסחאות מתייחדות אלו שהן פסוקים. ערך האמת של פסוקים לא מושפע כלל מההשמה הנתונה, אלא רק מן המבנה הנתון. (יש לציין שקיימות נוסחאות שאינן פסוקים שערך האמת שלהן אינו תלוי בהשמות. נוסחאות כאלו ניתן להפוך לפסוקים על ידי כימות כולל.) אינטואיטיבית, הפסוקים שערך האמת שלהם הוא אמת מייצגים את המשפטים שמתקיימים לגבי המבנה. מבין הפסוקים מתייחדת קבוצת הטאוטולוגיות והסתירות. אלו הם הפסוקים שערך האמת שלהם זהה בכל מבנה.
נבחן את השפה מסדר ראשון שכוללת שני קבועים ו-, שתי פונקציות דו-מקומיות ו- ושני יחסים דו-מקומיים ו-. כמו כן נרשה את השימוש בסימון המקוצר שמסמן את היחס . נתאר שלוש דוגמאות למבנים של השפה .
חוג המספרים השלמים הוא מבנה שעולמו הוא הקבוצה . הקבועים ו- מתפרשים כמספרים 0 ו-1, הפונקציות ו- מתפרשות כפעולת החיבור ופעולת הכפל הרגילות בין מספרים שלמים. הוא יחס השוויון הרגיל ואילו הוא היחס "מחלק את".
נדגים כמה פסוקים ב- ואת ערך האמת שלהם ב-:
שדה המספרים הממשיים הוא מבנה שעולמו הוא קבוצת המספרים על הישר הממשי . כמו קודם, הקבועים ו- מתפרשים כמספרים 0 ו-1, הפונקציות ו- מתפרשות כפעולת החיבור ופעולת הכפל הרגילות בין מספרים ממשיים. הוא יחס השוויון הרגיל ואילו הוא היחס "קטן או שווה ל-" .
נתאר את ערך האמת ב- של הפסוקים ב- שתוארו קודם:
נניח X היא קבוצה עם שני איברים לפחות. נגדיר מבנה באופן הבא: העולם של המבנה הוא , קבוצת החזקה של X, שאיבריה הם כל התת-קבוצות של X. הקבועים ו- מתפרשים כקבוצה הריקה וכקבוצה X בהתאמה. הפונקציות ו- מתפרשות כפעולת האיחוד ופעולת החיתוך בין קבוצות. הוא יחס השוויון הרגיל בין קבוצות ואילו הוא היחס "מוכל ב-".
נתאר את ערך האמת ב- של הפסוקים ב- שתוארו קודם:
אומרים שהמבנה הוא תת-מבנה של אם העולם של חלקי לעולם של וכולל את כל הקבועים האישיים של , הפונקציות והיחסים של הם הפונקציות והיחסים של כשמצמצמים אותם לעולם של , והפונקציות המצומצמות סגורות. למשל אם נחליף את המשמעות של במבנה 1 שהודגם קודם (חוג המספרים השלמים) כך שייתפרש כיחס "קטן או שווה ל-", נקבל תת-מבנה של מבנה 2 (שדה המספרים הממשיים).
יהי מבנה שעולמו . על תת-קבוצה נאמר שהיא תת-קבוצה סגורה ב- אם כל קבוע אישי של נמצא ב- ו- סגורה תחת כל הפונקציות של . לכל קבוצה סגורה יש תת-מבנה יחיד של שעולמו הוא . תת-מבנה זה נקרא התת-מבנה הנקבע על ידי . העולם של כל תת-מבנה הוא קבוצה סגורה.
האמיתות של נוסחאות כוללות עוברת בירושה ממבנים לתתי-מבנים. כלומר אם נוסחה שכל הכמתים בה הם נכונה במבנה מסוים, היא נכונה גם בכל תת-מבנה. ההפך אינו נכון, ייתכן שנוסחה כזו נכונה בתת-מבנה אך לא במבנה כולו (למשל הטענה שכל מספר הוא שלם נכונה בחוג השלמים אך לא בשדה הממשיים). האמיתות של נוסחאות ישיות עוברת מתת-מבנים למבנה. כלומר אם נוסחה שכל הכמתים בה הם נכונה בתת-מבנה, היא נכונה גם במבנה המכיל אותה. ההפך אינו נכון (למשל קיים מספר בשדה הממשיים שאינו שלם, אך אין מספר כזה בחוג השלמים).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.