שתף קטע נבחר

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

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

     

    היפה

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

     

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

     

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

     

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

     

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

     

    קידוד טענות

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

     

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

     

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

     

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

     

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

     

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

     

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

     

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

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

     

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

     

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

     

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

     

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

     

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

     

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

     

    יש אלוהים?

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

     

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

     

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

     

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

     

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

     

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

     

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

     

    במילים אחרות, משפט גדל הוא שמכריע בשאלה אם האדם הוא "רק" מחשב מאוד מתוחכם או שיש בו משהו שחורג מעבר. זו עמדה שמביעים לא מעט פילוסופים ומתמטיקאים והנציג הבולט ביותר שלה הוא כנראה המתמטיקאי רוג'ר פנרוז שהקדיש לה שני ספרים - “The Emperor's New Mind” ו-”Shadows of the Mind”.

     

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

     

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

     

    תם ולא נשלם

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

     

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

     

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

     

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

     

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