אז מה זו לוגיקה מתמטית?

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

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

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

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

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

כדי להסביר מה קורה עכשיו כדאי לתת דוגמה. גם אם לא שמעתם עדיין על המושג המתמטי של חבורה, לא נורא; מה שחשוב הוא שזה מושג שמתאר הרבה אובייקטים במתמטיקה - מספרים שלמים, שברים, מטריצות, פרמוטציות, איזומטריות וכו’ וכו’ וכו’. כל היצורים הללו הם רבים ושונים, אבל בעלי כמה תכונות בסיסיות משותפות שהופכות את כולם לדוגמאות לחבורות. מאותן תכונות בסיסיות אפשר להסיק מסקנות שתקפות לכל חבורה - למשל, “בכל חבורה סופית הסדר של כל איבר בחבורה מחלק את סדר החבורה” שאפשר לכתוב בנוסחה מתמטית מדויקת בתור \( \forall G:\left|G\right|<\infty\Rightarrow\left(a\in G\Rightarrow o\left(a\right)|\left|G\right|\right) \) (זו לא נוסחה שמתאימה לכללי הבניה שאציג בהמשך; כאן ניסיתי לתת משהו שיהיה קריא ככל האפשר לעין אנושית במחיר ויתור על הדיוק וביצעתי כמה הזנחות מזעזעות). הנוסחה הזו היא חד משמעית - ברור שיש קשר של \( \in \) בין \( a \) ל-\( G \), וברור ש-\( o\left(a\right) \) נמצא ביחס שמסומן על ידי \( | \) עם \( \left|G\right| \), ואם מכירים את הסימונים \( \forall \) (“לכל”) ו-\( \Rightarrow \) (“גורר”) גם ברור בערך מה העקרון הלוגי שמביעה הנוסחה - “לכל \( G \), אם מתקיים א’ אז מתקיים ש(אם מתקיים ב’ אז מתקיים ג’)”. מה לא ברור, בטח לא למישהו שלא בקיא כל כך במתמטיקה? מה המשמעות של סימונים כמו \( G,<,\infty,o\left(a\right),| \) וכדומה. וכאן התשובה היא לא מיידית בכלל; להבדיל מהסימן \( \forall \) שמשמעותו היא תמיד “לכל”, לסימונים האחרים ניתן לתת הרבה משמעויות שונות. \( G \) יכול לייצג אוסף של מטריצות, או את המספרים השלמים, או קבוצה של פרמוטציות, וכו’ וכו’. לפעמים זה נהיה עוד יותר מוזר וגם סמלים כמו \( < \) לא בהכרח מייצגים “קטן מ-“.

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

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

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

כעת, נניח שיש לנו אוסף של משפטים, \( \Phi \), ונניח שיש לנו עוד משפט אחד \( A \). אומרים ש-\( A \) נובע לוגית מ-\( \Phi \) אם בכל פרשנות שבה כל משפטי \( \Phi \) הם נכונים, גם \( A \) הוא נכון. מסמנים את זה \( \Phi\models A \). זו הגדרה סמנטית, כי היא מתייחסת למשמעות שאנחנו נותנים לסימבולים שמופיעים ב-\( \Phi \)וב-\( A \). כמו כן, אומרים ש-\( A \) יכיח מ-\( \Phi \) אם במערכת ההוכחה שלנו ניתן לקבל את \( A \) על ידי הוכחה שבה ניתן להשתמש באברי \( \Phi \) בתור הנחות היסוד. מסמנים את זה \( \Phi\vdash A \). זו הגדרה תחבירית כי היא מדברת על היכולת לבצע מניפולציות לסדרות של סימבולים מתוך \( \Phi \) כדי להפיק מהן את סדרת הסימבולים שמרכיבה את \( A \). אם תעצרו ותחשבו לרגע, אין שום סיבה שבעולם ששני דברים כל כך שונים באופיים יהיו קשורים זה לזה - מצד אחד, משמעויות מתמטיות שיכולות להילקח מכל רחבי העולם המתמטי; מצד שני, מניפולציות מכניות של סדרות של סימבולים. הקסם (שהוא לא פחות ממדהים, לטעמי) הוא שיש קשר. כלומר, ניתן לתת מערכות הוכחה (עבור סוגים מסויימים של לוגיקות) שבהן מתקיים ש-\( \Phi\models A\iff\Phi\vdash A \); שבהן משפט הוא יכיח מקבוצת פסוקים אם ורק אם הוא נובע ממנה לוגית. לתוצאה כזו קוראים משפט שלמות ונאותות (“נאותות” פירושה שכל מה שיכיח אכן נובע לוגית, וזה בדרך כלל קל; “שלמות” פירושה שכל מה שנובע לוגית אכן יכיח, וזה החלק הקשה יותר להוכחה והמפתיע בהרבה). משפט שלמות ונאותות עבור הסוג הנפוץ ביותר של לוגיקה - לוגיקה מסדר ראשון - הוא לרוב אחת מהפסגות של קורס מבוא ללוגיקה.

אלו מכם ששמעו על משפטי אי-השלמות של גדל אולי קצת מבולבלים בשלב הזה. אני אומר שיש משפטי שלמות ונאותות, ומצד שני יש גם את משפטי אי השלמות של גדל. איך זה מסתדר? דיברתי על זה בעבר, אבל אסביר שוב בקצרה: המילה “שלמות” מופיעה כאן בשתי משמעויות שונות. המשמעות שעליה דיברתי כעת, לפיה אם \( \Phi\models A \) אז \( \Phi\vdash A \) היא שלמות של מערכת ההוכחה; לעומת זאת, המשמעות השניה תמיד מתייחסת לשלמות של תורות. מבחינתנו, תורה היא אוסף של משפטים \( \Phi \) בלוגיקה מסויימת; ותורה היא שלמה אם לכל \( A \) שניתן לנסח בשפה של התורה, או שמתקיים \( \Phi\vdash A \) או שמתקיים \( \Phi\vdash\neg A \), כאשר \( \neg A \) הוא השלילה של \( A \) (באותה מידה - בגלל שיש לנו את משפט השלמות והנאותות - היה אפשר להגדיר זאת גם כ”או שמתקיים \( \Phi\models A \) או שמתקיים \( \Phi\models\neg A \)”). זה אומר שמרגע שהנחנו את \( \Phi \), לא נותרות שאלות פתוחות; לכל שאלה יש תשובה חד משמעית. כן או לא. ובזכות משפטי השלמות והנאותות גם אפשר למצוא את אותה תשובה חד משמעית באופן מכני.

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

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

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