לוגיקה מסדר ראשון

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

זו הבעיה באופן כללי במתמטיקה: אנחנו בדרך כלל רואים רק את התוצר הסופי. אם ננסה להבין את כל שלבי הביניים זה ידרוש מאיתנו מאמץ גדול פי כמה וכמה, ולעתים קרובות נצטרך להסתגל לטרמינולוגיות שונות מהותית מאלו שהתרגלו אליהן (אפילו הפוכות!) ולרעיונות פילוסופיים מנחים שבימינו עשויים להיראות מוזרים. זה הופך את ההיסטוריה של המתמטיקה לתחום מאתגר מאין כמותו, שאני לרוב נמנע ממנו. כך גם עם פרגה - שיטות הסימון שלו היו שונות משלנו כיום, והיו עוד כמה הבדלים רעיוניים בין מה שהוא עשה ומה שאני הולך להציג כרגע. חשבו על מה שאני מציג בתור זיקוק הרעיונות של פרגה ומתמטיקאים רבים אחרים; וזכרו שזו בפירוש לא הדרך היחידה לבנות לוגיקה פורמלית אלא פשוט זו שהשתרשה בסופו של דבר במרבית ספרי הלימוד ובעיסוק המתמטי הכללי, בגלל שהיא הייתה הנוחה ביותר. למה שאני אציג קוראים “לוגיקה מסדר ראשון” (First Order Logic).

לוגיקה מסדר ראשון מנסה לתאר את רוב המתמטיקה. כדי להסביר מה בכלל המשמעות של “תיאור” שכזה ולמה לא את כל המתמטיקה אני חושב שכדאי קודם כל להכיר את הפרטים הקטנים של מה זה בכלל אומר, לוגיקה מסדר ראשון. גם פשר השם (“סדר ראשון”? מה זו “לוגיקה מסדר שני”, אם כן?) תלוי בפרטים. לכן הפוסט הזה הולך להיות טכני והגדרתי יחסית. זה לא יהיה נעים לקוראים שמקווים למבוא מלטף, אבל אומר לכם בכנות - בכל הנוגע ללוגיקה, אני לא חושב שיש כזה, או אפילו שנכון לעשות את זה. לוגיקה היא האמנות של תיאור פורמלי ומדויק של דברים שאחרת הם בגדר נפנופי ידיים; לב-לבו של העניין הוא בכך שהבנה של הפורמליזם הזה מאפשרת לנו להבין את נפנופי הידיים ברמה גבוהה יותר מאשר היינו מבינים אותם אם היינו נשארים ברמת נפנופי הידיים. אם לסטות לאנגלית לרגע, Details Matter. אני לא חושב שזה מקרה שספר המדע הפופולרי היחיד שקראתי ולדעתי עושה צדק ללוגיקה - “גדל, אשר, באך” - מלכלך את הידיים שלו בפרטים טכניים כבר מההתחלה.

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

אם כן, בואו ונעבור לפרטים. מי מכם שקרא את הפוסטים על תחשיב הפסוקים כבר יודע למה בערך צריך לצפות - תיאור של לוגיקה מסויימת מורכב מתיאור של תחביר - האופן שבו בונים פסוקים שמטרתם “לתאר משהו”, וסמנטיקה, האופן שבו נותנים משמעות לרכיבים של הפסוקים, ובמקרה שלנו - המשמעות הזו נותנת בסופו של דבר לפסוקים ערכי אמת - “אמת/שקר”, או \( \mbox{T,F} \).

בתחשיב הפסוקים בנינו את הפסוקים מתוך “אטומים” שהיו משתנים שיכלו לקבל ערכי \( \mbox{T,F} \) בלבד, וחיברנו אותם זה לזה עם “וגם/או/לא/גורר”, וזהו זה. כוח ההבעה שלנו היה מוגבל למדי. הבה ונמחיש זאת עם שתי דוגמאות. הראשונה היא קלאסית, ונוגעת לשרשרת המשפטים הבאה שמשוייכת לאריסטו:

1. כל בני האדם הם בני תמותה.
2. סוקרטס הוא בן אדם.
3. מכאן שסוקרטס הוא בן תמותה.

אינטואיטיבית ברור לנו שההיסק פה “נכון”. איך מפרמלים אותו בתחשיב הפסוקים? הרי בתחשיב הפסוקים אין לנו דרך לדבר על “כל” ועל תכונות כמו “מישהו הוא בן אדם/בן תמותה”. אפשר היה אולי לחשוב שטענה 1 היא מהצורה \( A\to B \) כאשר \( A \) הוא “בן אדם” ו-\( B \) הוא “בן תמותה”, אבל איך זה מתחבר אל סוקרטס? האם טענה 2 היא \( A \)? לא, שהרי \( A \) היא הטענה “בן אדם”. היא לא הטענה “סוקרטס הוא בן אדם”. אולי צריך להוסיף עוד משתנה עבור “סוקרטס”? ואז טענה 2 היא \( C\to A \)? ואז נסיק איכשהו מצמד הפסוקים \( A\to B \) ו-\( C\to A \) ש-\( C\to B \). זה נשמע לא רע במיוחד, אבל זה אומר שצריך להתאים משתנה מיוחד לכל בן אדם אפשרי. ומה עם זאפוד ביבלברוקס? הוא לא בן אדם. בואו נתאים לו משתנה \( Z \). האם אנחנו צריכים פסוק \( \neg\left(Z\to A\right) \) עבור זאפוד? ומה יקרה אם זאפוד וסוקרטס יופיעו באותו משפט? מה המשמעות של \( \left(C\to A\right)\wedge\neg\left(Z\to A\right) \)? היינו רוצים לומר שהמשפט הזה אומר “סוקרטס הוא בן אדם וזאפוד לא” אבל לשם כך המשתנה \( A \) צריך לקבל גם \( \mbox{T} \) וגם \( \mbox{F} \) בו זמנית (\( \mbox{T} \) לחלק השמאלי של המשפט ו-\( \mbox{F} \) לימני). או לחילופין, צריך יהיה להציב \( \mbox{F} \) או בסוקרטס או בזאפוד, אבל…

טוב, זה די מיש-מש. למרות שאולי אפשר לחלץ מזה משהו, זה כאב ראש לחשוב איך לנסח אפילו משפטים פשוטים בצורה הזו. בואו נעבור עכשיו למשפט קצת יותר מורכב - הגדרת הגבול בחדו”א. אומרים ש-\( \lim_{x\to x_{0}}f\left(x\right)=L \) אם לכל \( \varepsilon>0 \) קיים \( \delta>0 \) כך שלכל \( x \), אם \( \left|x-x_{0}\right|<\delta \) אז \( \left|f\left(x\right)-L\right|<\varepsilon \). איך אפשר לנסח את שרשרת ה”לכל-קיים-לכל” בעזרת תחשיב הפסוקים? אין לי מושג. ואיך אפשר לנסח את ההפעלה של ערך מוחלט בתוך ההגדרה? לא יודע. ואיך אפשר לנסח את “קטן מ-“? האם צריך שני משתנים שונים, אחד עבור \( \left|x-x_{0}\right|<\delta \) ואחד עבור \( \left|f\left(x\right)-L\right|<\varepsilon \)? הרי התחושה שלנו היא שהמופע של הערך המוחלט, והמופע של ה-\( < \) בשני המקרים הוא מופע של אותו דבר. אנחנו רוצים לחלץ את הרכיבים הדומים, לא להסתיר אותם מאחורי משתנים שונים.

בקיצור, אנחנו עוברים לדבר על לוגיקה מסדר ראשון כדי לשפר את יכולת ההבעה שלנו. לצורך כך אנחנו מרחיבים את התחביר באופן משמעותי. יש לנו, כמקודם, משתנים: \( x_{1},x_{2},x_{3},\dots \). יש לנו את הסימנים הלוגיים של תחשיב הפסוקים, כלומר \( \to,\neg,\wedge,\vee \), ואפשר גם להוסיף \( \leftrightarrow \) כדי לשפר את הקריאות. צריך גם סוגריים ופסיק, כלומר הסימנים \( ) \) ו-\( ( \) ו-\( , \) (למה פסיק? עוד מעט נגיע לזה). אבל שני השחקנים החדשים שמקבלים מקום של כבוד הם הסימנים עבור “לכל” ו”קיים”: \( \forall \) ו-\( \exists \), שהם מעין A הפוכה (עבור All, “לכל”) ו-E הפוכה (עבור Exists, “קיים”).

אילו עוד דברים אנחנו צריכים? ובכן, אם ננסה לדבר על תורת הקבוצות נצטרך כנראה סימן עבור יחס השייכות \( \in \) ועבור הקבוצה הריקה \( \emptyset \); אם נדבר על תורת החבורות נצטרך סימן עבור הפעולה הבינארית של החבורה \( \cdot \) ועבור האיבר האדיש לכפל \( e \). אם נדבר על המספרים הטבעיים נצטרך סימן ל-\( 0 \) וסימן ל”עוקב של מספר”, נאמר \( S \) (כך ש-\( S\left(0\right) \) הוא בעצם 1 וכדומה), וכמובן שאת יחס הסדר \( < \) ואת פעולות החיבור \( + \) והכפל \( \times \). ואם נרצה לדבר על גרפים נצטרך עוד סימן יחס שמתאר שיש קשת בין שני צמתים - למשל, \( E\left(v,u\right) \) מתאר זאת. וכו’ וכו’ וכו’. אנחנו רואים שאנחנו צריכים המון סימנים, אבל שהסימנים הללו הם תלויי שימוש; אנחנו לא חייבים את \( \in \) תמיד אלא רק כשאנחנו רוצים לתאר קבוצות; ואין צורך בסימן \( + \) בתורת החבורות, וכו’ וכו’. לכן מטעמי חסכנות אנחנו מרשים להשתמש רק בתת-קבוצה של הסימנים האפשריים. פורמלית, אנחנו מגדירים מילון שהוא אוסף של סימנים שבאים לתאר קבועים, יחסים ופונקציות, כך שכל מילון מגדיר שפה אחרת מסדר ראשון. יש את השפה של תורת החבורות, שהמילון שלה הוא \( \left\langle e,\cdot\right\rangle \); השפה של המספרים הטבעיים עם המילון \( \left\langle 0,S,+,\times\right\rangle \); השפה של תורת הקבוצות עם \( \left\langle \emptyset,\in\right\rangle \) וכן הלאה. כאן \( 0,\emptyset \) הם דוגמאות לקבועים, בעוד ש-\( \in \) הוא דוגמא ליחס ו-\( S,+,\times \) הם דוגמאות לפונקציות.

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

יש סימן יחס מיוחד שטרם דיברתי עליו - שוויון, \( = \). יש ספרים שלא מכניסים אותו אוטומטית לשפות, ויש ספרים שכן. אני מעדיף את הגישה שמכניסה אותו אוטומטית למרות שהיא טיפה מגבילה אותנו. אם כן, \( = \) יהיה שייך לקבוצת הסימנים שתמיד יכולים לשמש כחלק מהרכבת פסוקים בשפה - הקבוצה \( \left\{ \to,\neg,\wedge,\vee,\leftrightarrow,),(,,,\exists,\forall,=\right\} \). לסימנים הללו קוראים סימנים לוגיים.

באופן כללי מסמנים פונקציות כמשהו כזה: \( f\left(x_{1},x_{2}\right) \) הוא דוגמה לסימן פונקציה ש”מופעלת” על שני משתנים, \( x_{1},x_{2} \). גם יחסים מתוארים כך -\( R\left(x_{1},x_{2}\right) \) הוא דוגמה. שימו לב מה יש לנו כאן: קודם כל את סימן הפונקציה/יחס; אחר כך סוגר שמאלי (הסוגר הזה הוא חלק מהסימנים הלוגיים!), אחר כך שם של משתנה, אחר כך הסימן “פסיק”, אז עוד משתנה, ואז סוגר ימני.

כשבונים פסוקים בתחשיב הפסוקים, יש שני סוגים של “אבני בניין” שעובדים איתם. ראשית, יש ביטויים שהמשמעות שנייחס להם - אחרי שנתחיל לייחס משמעות לדברים - היא של איברים מה”עולם” (מה זה? בהמשך). שנית, יש ביטויים שהמשמעות שנייחס להם היא משמעות לוגית - \( \mbox{T} \) או \( \mbox{F} \). לביטויים מהסוג הראשון נקרא שמות עצם, ולביטויים מהסוג השני - נוסחאות. שימו לב ששם עצם לבדו הוא לא נוסחה חוקית!

שם עצם מוגדר בתור סימן של משתנה (למשל, \( x \)) או סימן של קבוע (למשל, \( c \)) או “הפעלה” של סימן פונקציה על שמות עצם, למשל \( f\left(x,c\right) \) או \( g\left(f\left(x,x,x\right),g\left(c_{1},c_{2}\right)\right) \).

נוסחאות מוגדרות בצורה טיפה יותר מורכבת - ראשית יש נוסחאות אטומיות, שהן תמיד “הפעלה” של סימן יחס כלשהו על שמות עצם כלשהם, למשל \( R\left(f\left(x_{1},x_{2}\right),c\right) \) או \( x_{1}=g\left(x_{2}\right) \) וכדומה. שנית, אם \( \varphi,\psi \) הן נוסחאות, כך גם \( \neg\varphi \) ו-\( \left(\varphi\to\psi\right) \) ו-\( \left(\varphi\leftrightarrow\psi\right) \) ו-\( \left(\varphi\wedge\psi\right) \) ו-\( \left(\varphi\vee\psi\right) \) (זה דומה לתחשיב הפסוקים, עם נוסחאות אטומיות במקום משתנים). לבסוף, לכל משתנה \( x \) ונוסחה \( \varphi \), גם \( \forall x\left(\varphi\right) \) ו-\( \exists v\left(\varphi\right) \) היא נוסחה. זה משלים את הגדרת התחביר (אבל ברצינות, אם אתם רוצים ללמוד את העניין עד הסוף, תצטרכו ספר אמיתי בשביל זה).

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

1. \( \forall x\forall y\forall z\left(\left(x\cdot y\right)\cdot z=x\cdot\left(y\cdot z\right)\right) \) ("אסוציאטיביות").
2. \( \forall x\left(x\cdot e=e\cdot x=x\right) \) ("אדיש כפלי").
3. \( \forall x\exists y\left(x\cdot y=y\cdot x=e\right) \) ("הופכי כפלי").

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

עכשיו בואו נעבור לסמנטיקה.

הסמנטיקה של תחשיב הפסוקים היא פשוטה ביותר - יש משתנים, בכל אחד מציבים \( \mbox{T} \) או \( \mbox{F} \), “מחשבים” את הערך של פסוק שנובע מתוך ההצבה הזו, וסיימנו. בתחשיב היחסים הסיפור מסובך באופן משמעותי. אנחנו מתחילים משפה מסדר ראשון נתונה, עם איזה שהוא מילון נתון (מילון, כזכור, הוא אוסף סימני הקבועים, היחסים והפונקציות שיכולים להופיע בנוסחאות השפה). הדבר הראשון שעושים, עוד לפני שמתחילים עם השמות של ערכים למשתנים, הוא לקבוע את “זירת המשחק” שלנו, שכוללת את העולם שממנו ילקחו הערכים שמשתנים יכולים לקבל, ואת הפרשנות שניתנת בעולם הזה לסימני הקבועים, היחסים והפונקציות. המפלצת שכוללת את כל המידע הזה בתוכה נקראת מבנה ומסומנת אצלי ב-\( \mathcal{M} \).

מבנה \( \mathcal{M} \), אם כן, כולל:

1. קבוצה לא ריקה \( D^{\mathcal{M}} \) - זה "העולם" שממנו ילקחו הערכים שהמשתנים יכולים לקבל.
2. לכל סימן קבוע \( c \) במילון, איבר \( c^{\mathcal{M}}\in D^{\mathcal{M}} \) - הפרשנות ש-\( c \) מקבל במודל \( \mathcal{M} \).
3. לכל סימן יחס \( R \) במילון על \( n \) מקומות, יחס \( R^{\mathcal{M}}\subseteq\left(D^{\mathcal{M}}\right)^{n} \).
4. לכל סימן פונקציה \( f \) במילון על \( n \) מקומות, פונקציה \( f^{\mathcal{M}}:\left(D^{\mathcal{M}}\right)^{n}\to D^{\mathcal{M}} \).

ושוב, אדגיש את ההבדל שיש פה בין הסמנטיקה והתחביר. \( c,R,f \) הם סימנים - אותיות ותו לא, חסרי פשר לכשעצמם ונתונים לפרשנויות רבות; לעומת זאת, \( c^{\mathcal{M}} \) הוא איבר של קבוצה, ו-\( R^{\mathcal{M}} \) הוא יחס על קבוצה ו-\( f^{\mathcal{M}} \) היא פונקציה על קבוצה. יש להם משמעות עמוקה יותר מאשר אוסף פיקסלים.

בואו נחזור אל תורת החבורות שלנו וניתן דוגמאות לשני מבנים אפשריים עבורה. מבנה אחד הוא זה: \( \mathcal{M}=\left(\mathbb{Z},0,+\right) \). כלומר, \( D^{\mathcal{M}}=\mathbb{Z} \) - המספרים השלמים; \( e^{\mathcal{M}}=0 \) - כלומר, הפרשנות שלנו לסימן הקבוע \( e \) הוא המספר \( 0\in\mathbb{Z} \), ו-\( \cdot^{\mathcal{M}}=+ \), כלומר הפרשנות שלנו לסימן הפונקציה \( \cdot \) הוא פעולת החיבור.

מבנה אחר לגמרי הוא זה שבו \( D^{\mathcal{M}}=\mbox{GL}_{n}\left(\mathbb{C}\right) \) - אוסף המטריצות מסדר \( n\times n \) מעל המרוכבים שהדטרמיננטה שלהן שונה מאפס. במבנה הזה \( \cdot \) הוא הפעולה של כפל מטריצות, ו-\( e \) היא מטריצת היחידה (המטריצה שכולה אפסים פרט לאלכסון הראשי שכולו 1). אם אתם לא מכירים את הדוגמה הזו, לא נורא; זה לא קריטי להמשך.

עכשיו, אחרי שהגדרנו מבנה, אפשר להגדיר גם השמה - זו פשוט פונקציה \( s:\left\{ x_{1},x_{2},x_{3},\dots\right\} \to D^{\mathcal{M}} \) שמתאימה לכל משתנה \( x \) איבר כלשהו מתוך \( D^{\mathcal{M}} \). ברגע שבו הגדרנו השמה \( s \), ערך האמת של כל נוסחה נקבע, באופן הבא:

1. ראשית, אפשר לחשב לכל שם עצם את האיבר שהוא מתאים לו.
2. שנית, לכל נוסחה אטומית אפשר לחשב אם ערכה הוא \( \mbox{T} \) או \( \mbox{F} \).
3. כעת קל לחשב מתוך ערכי ה-\( \mbox{T} \) וה-\( \mbox{F} \) הללו ערך אמת לכל הנוסחה כמו בתחשיב הפסוקים.
4. ...למעט במקרה שבו יש לנו כמתים, ואז יש לנו רמה נוספת של סיבוך.

בואו נעבור על זה שלב שלב. ראשית, מרגע שהגדרנו את \( s \) על המשתנים, אפשר להגדיר פונקציה \( \overline{s} \) שהיא הרחבה של \( s \) על כל שמות העצם, באופן הבא: \( \overline{s}\left(x\right)=s\left(x\right) \) לכל משתנה; \( \overline{s}\left(c\right)=c^{\mathcal{M}} \) לכל סימן קבוע \( c \); ו-\( \overline{s}\left(f\left(t_{1},\dots,t_{n}\right)\right)=f^{\mathcal{M}}\left(\overline{s}\left(t_{1}\right),\dots,\overline{s}\left(t_{n}\right)\right) \) לכל סימן פונקציה \( f \).

כאן כדאי לעצור ולוודא שמבינים את הגדרה למעלה. למשל, באגף שמאל של השוויון האחרון יש לנו את הפונקציה \( \overline{s} \) שמופעלת על שם עצם יחיד - \( f\left(t_{1},\dots,t_{n}\right) \). האופן שבו היא פועלת הוא קודם כל לחשב, באופן רקורסיבי, מה ההשמה המורחבת נותנת לכל אחד משמות העצם \( t_{1},\dots,t_{n} \) שהם הרכיבים של שם העצם הזה; לאחר מכן היא לוקחת את הפונקציה \( f^{\mathcal{M}} \) - הפרשנות של סימן הפונקציה \( f \) במבנה \( \mathcal{M} \) - ומפעילה אותה על הערכים שהיא כבר חישבה. התוצאה היא איבר ב-\( D^{\mathcal{M}} \), וזה הערך ש-\( \overline{s} \) נותנת לשם העצם.

למשל, נתבונן בשם העצם \( \left(x\cdot y\right)\cdot e \) שמנוסחת בשפה של תורת החבורות. נניח שהמודל שלנו הוא \( \mathcal{M}=\left(\mathbb{Z},0,+\right) \) שכבר הזכרתי; מה יהיה \( \overline{s}\left(\left(x\cdot y\right)\cdot e\right) \)? מההגדרה שלי ניתן לראות שהוא יהיה \( s\left(x\right)+s\left(y\right)+0 \), ולכן אם למשל \( s\left(x\right)=2 \) ו-\( s\left(y\right)=3 \) נקבל \( \overline{s}\left(\left(x\cdot y\right)\cdot e\right)=5 \).

השלב הבא הוא לטפל בנוסחאות האטומיות. נוסחה אטומית כללית נראית כך: \( R\left(t_{1},\dots,t_{n}\right) \) כאשר \( R \) הוא סימן יחס כלשהו. לנוסחה הזו ניתן ערך \( \mbox{T} \) אם מתקיים \( R^{\mathcal{M}}\left(\overline{s}\left(t_{1}\right),\dots,\overline{s}\left(t_{n}\right)\right) \), כלומר אם ביחס \( R^{\mathcal{M}} \), שהוא הפרשנות של סימן היחס \( R \) במבנה \( \mathcal{M} \), האיברים \( \overline{s}\left(t_{1}\right),\dots,\overline{s}\left(t_{n}\right) \) של \( D^{\mathcal{M}} \) אכן נמצאים זה עם זה. שימו לב שזה תלוי הן בערך ש-\( \overline{s} \) מעניקה לשמות העצם, והן בפרשנות של \( R \) ב-\( \mathcal{M} \). היוצא מן הכלל היחיד הוא יחס השוויון, שבו אין “פרשנות” - הוא תמיד מייצג שוויון, כלומר \( t_{1}=t_{2} \) מקבל ערך \( \mbox{T} \) אם ורק אם \( \overline{s}\left(t_{1}\right)=\overline{s}\left(t_{2}\right) \). כאמור, הדרישה הזו מגבילה אותנו במובן מסויים אבל זה לא קריטי כרגע.

כיצד מחשבים ערך אמת כעת עבור פסוקים שבנוים מקשרים אני מקווה שאתם כבר יודעים. למשל, \( \varphi\wedge\psi \) מקבל \( \mbox{T} \) רק אם שני רכיביו קיבלו \( \mbox{T} \) וכדומה.

הסימון הפורמלי לכל זה הוא הסימון הבא: \( \mathcal{M}\models_{s}\varphi \) פירושו “בפרשנות של השפה שנותן המבנה \( \mathcal{M} \), ובהשמה \( s \), הפסוק \( \varphi \) מקבל ערך \( \mbox{T} \)”. הסימון הזה הכרחי כדי שיהיה נוח להסביר איך נותנים ערכי אמת עבור פסוקים שמכילים כמתים; לפני כן אצטרך להציג עוד סימון. נניח ש-\( x \) הוא משתנה כלשהו ו-\( a\in D^{\mathcal{M}} \) איבר כלשהו במבנה, וש-\( s \) היא השמה למשתנים. אז אפשר להגדיר השמה אחרת, שאסמן \( s\left[x\leftarrow a\right] \), שהיא זהה ל-\( s \) על כל משתנה אפשרי פרט ל-\( x \), ועל המשתנה הזה היא מחזירה \( a \).

כעת: \( \mathcal{M}\models_{s}\forall x\left(\varphi\right) \) אם לכל \( a\in D^{\mathcal{M}} \) מתקיים \( \mathcal{M}\models_{s\left[x\leftarrow a\right]}\varphi \); ו-\( \mathcal{M}\models_{s}\exists x\left(\varphi\right) \) אם קיים \( a\in D^{\mathcal{M}} \) כך ש-\( \mathcal{M}\models_{s\left[x\leftarrow a\right]}\varphi \). זו ההגדרה הכי קשה כאן; עצרו ונסו לוודא שאתם מבינים מה הולך פה. שימו לב לכך שחישוב ערך האמת של \( \forall x\left(\varphi\right) \) ו-\( \exists x\left(\varphi\right) \) תחת ההשמה \( s \) בעצם מתעלם מהערך ש-\( s \) נותנת ל-\( x \); תחת זאת הוא משחק עם כל ערך אפשרי ורואה מה קורה. זה לא אומר ש-\( s \) לא חשובה; רק שהערך הספציפי שהיא נותנת ל-\( x \) לא רלוונטי.

עם ההגדרה הזו, סיימנו; אנחנו מבינים איך בהינתן מודל והשמה נותנים ערך אמת לכל הנוסחאות. עם זאת, לרוב הנוסחאות שיעניינו אותנו הן נוסחאות שאפשר לדעת מה יהיה ערך האמת שלהן ישר מתוך \( \mathcal{M} \), בלי שהוא יהיה תלוי בהשמה זו או אחרת. לצורך כך אני נזקק להגדרה אחת אחרונה: משתנה בנוסחה כלשהי הוא קשור אם הוא מופיע בטווח של כמת שמתאים לו. למשל, \( \forall x\left(x=y\right) \) היא דוגמה לנוסחה שבה המשתנה \( x \) הוא קשור (כי הוא נופל בתוך הטווח של הכמת \( \forall x \) - בתוך הסוגריים שמייד אחריו). לעומת זאת \( y \) אינו קשור; למשתנה שכזה קוראים חופשי.

נוסחה שאין בה משתנים חופשיים בכלל נקראת פסוק. אם אין משתנים חופשיים בכלל, זה אומר שכל משתנה נמצא תמיד בטווח של כמת כלשהו, ולכן, אם תחשבו על זה רגע, ערך האמת של הפסוק לא יכול להיות תלוי באף השמה ספציפית כלשהי! זה בגלל שחישוב ערך האמת של הפסוק מתוך השמה תמיד יכלול את השלב שבו “זורקים לפח” את הערך שההשמה נתנה למשתנה, ובמקום זה מנסים את כל הערכים האפשריים. כן, זה מבלבל למדי; כשמוכיחים את זה פורמלית הראש כואב טיפה פחות.

זה מוביל אותנו להגדרה המרכזית בכל העניין הזה: אם \( \varphi \) הוא פסוק ו-\( \mathcal{M} \) הוא מבנה שמתאים לשפה, אז מסמנים \( \mathcal{M}\models\varphi \) אם \( \mathcal{M}\models_{s}\varphi \) עבור השמה \( s \) כלשהי (אם זה קורה להשמה כלשהי, זה קורה לכל ההשמות). במקרה הזה אומרים ש-\( \mathcal{M} \) היא מודל של \( \varphi \). מכאן קצרה הדרך לאוסף של נוסחאות: \( \mathcal{M}\models\Phi \) אם היא מודל של כל נוסחה ב-\( \Phi \). זה גם בדיוק מה שהלך בתחשיב הפסוקים, רק ששם “מודל” היה פשוט השמה, וכאן מודל הוא עולם ומלואו, תרתי משמע.

כעת, שימו לב לכך שהמבנה \( \mathcal{M}=\left(\mathbb{Z},0,+\right) \) הוא מודל של תורת החבורות, כלומר של קבוצת שלושת הפסוקים שקראתי לה “תורת החבורות”. לעומת זאת, \( \mathcal{M}=\left(\mathbb{Z},1,+\right) \) הוא אמנם מבנה חוקי למהדרין, אבל הוא איננו מודל של תורת החבורות שכן הוא לא מספק את הפסוק \( \forall x\left(x\cdot e=e\cdot x=x\right) \) (בדקו זאת!). זה מתאים לידע שלנו, לפיו \( \left(\mathbb{Z},1,+\right) \) אינה חבורה. למעשה, די ברור שהמודלים של “תורת החבורות” שלנו הם בדיוק המבנים שאנחנו קוראים להם “חבורות”!

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