משפט אי השלמות של גדל: הטוב, הרע והיפה. חלק שני

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

היפה

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

קידוד טענות

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

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

הצד הרע: מה המשפט של גדל לא אומר?

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

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

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

יש אלוהים?

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

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

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

תם ולא נשלם

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

גדי אלכסנדרוביץ' הוא בעל תואר שלישי במדעי המחשב ומחבר הבלוג "לא מדויק".