בשנת 1948, כמה שנים אחרי שהיגר לארצות־הברית, הוזמן המתמטיקאי האוסטרי־הונגרי קורט גדל (Kurt Gödel) לראיון רשמי על־מנת לקבל אזרחות אמריקאית. בימים שלפני הראיון שקד גדל על לימוד החוקה האמריקאית לפרטיה, וערב הראיון בישר לידידו אוסקר מורגנשטרן, אחד מאבות תורת־המשחקים, שעלה בידו לאתר בה פירצה משפטית־לוגית: החוקה, כך גילה, מאפשרת לדיקטטור לתפוס את השלטון באמריקה! גדל התכוון לפרט את תגליתו בפני הקונסול, אך למזלו, שני ידידיו עמם נסע לפגישה – מורגנשטרן עצמו ואלברט איינשטיין – היו בקיאים בהלכות העולם יותר ממנו, והצליחו להניאו מלעשות כן ממש במהלך הראיון. גדל זכה באזרחות וחי באמריקה עד מותו ב-1978. אמריקה נשארה דמוקרטיה עד היום.
הסיפור מלמד מעט על אופיו של גדל, אבל כאן מעניין אותנו היבט אחר שלו: גדל התעניין במציאת דקויות לוגיות במקומות בלתי־צפויים. הפגם שגילה בחוקה האמריקאית הוא, ככל הנראה, אנקדוטלי ושולי; בהזדמנויות אחרות עלה בידו לגלות תגליות חשובות בהרבה. עם זאת, במאמר זה ננסה להבהיר שחלק מהפרשנויות הדרמטיות שניתנו לאורך השנים לאותן תגליות הן מבוססות אף פחות מהטענה שעל האמריקאים מרחף איום הנובע מהמבנה הלוגי של החוקה.
לפני שנתחיל, כדאי להדגיש נקודה חשובה. יש רק דרך אחת להבין בדיוק ולעומק מה אומרים המשפטים שהוכיח גדל, והיא ללמוד ברצינות את החומר הרלוונטי בלוגיקה מתמטית, את המשפטים עצמם ואת ההוכחות וההרחבות שלהם. מאמר זה אינו יכול לעשות זאת, ואף לא ינסה. ממש בימים אלו יוצא לאור ספר של טורקל פרנזן, מומחה לשיבושי־גדל, העושה את מה שמאמר זה מנסה לעשות, אך בצורה יסודית יותר; הספר מעניק את כל המידע הרלוונטי גם לחסרי רקע בנושא, ומומלץ למעוניינים להעמיק.
| “This drifting of figures and geometric figuring, this irruption of dimensions and transcendental mathematics, leads us to the promised surrealist peaks of scientific theory, peaks that culminate in Gödel’s theorem: the existential proof, a method that mathematically proves the existence of an object without producing the object…” – Paul Virilio |
איך אפשר להוכיח דבר־מה, לדעת בוודאות גמורה שמשהו נכון? ילדים מומחים בלנהל עם מבוגרים דיאלוגים מייאשים מהסוג הבא: "אם תעזוב את הבובה, היא תיפול למים." – "למה?" – "זה נקרא כוח המשיכה. דברים נופלים." – "למה?" – "המממ... כי לכדור הארץ יש מסה...?" – "למה?" – "כי ככה אמא אומרת! די!" לוגיקה היא דרך מסודרת להוכיח דבר מתוך דבר. כיוון שכך, צריך להתחיל ממשהו, ואותו משהו נקרא הנחות־יסוד, או אקסיומות. את אלה אין אנו מוכיחים; אנו מקבלים אותן כי הן נראות סבירות, או שימושיות למטרה מסויימת. אחרי שהחלטנו על האקסיומות עלינו להסכים גם על כללי־היסק לוגיים, ואז אפשר לגזור מסקנות בצורה פשוטה: כל מסקנה היא או בעצמה אקסיומה, או שהיא נובעת ישירות ממסקנות קודמות על־ידי אחד מכללי־ההיסק.
שיטת־החקירה הזו, "השיטה האקסיומטית", היא עתיקת־יומין. למרות שהיא לא מאפשרת לדעת דברים "בוודאות גמורה", היא לפחות מקלה עלינו לברר בדיוק על מה אנו מסתמכים כשאנו טוענים משהו – מהן האקסיומות העומדות בבסיס הטענה, ומהם כללי־ההיסק הלוגיים בהם השתמשנו כדי לעבור מטענה לטענה. השיחה בין הילד לאמו מדגימה שליותר מזה לא ניתן לצפות: תמיד אפשר לשאול עוד "למה?", וכך להטיל ספק במה שקיווינו שהוא מובן־מאליו. דיאלוג ידוע של לואיס קרול מדגים שגם המרכיב השני בשיטה, כללי־ההיסק, אינו חסין בפני הטלת ספק אין־סופית שכזו.
במתמטיקה, במיוחד, זכתה השיטה האקסיומטית להצלחה רבה, החל מפיתוח הגיאומטריה על־ידי אוקלידס לפני למעלה מאלפיים שנה. לשיטה האקסיומטית במתמטיקה יש כמה מאפיינים ייחודיים, וכדאי להזכיר שלושה מהם. ראשית, האקסיומות בתורות מתמטיות אינן אמפיריות; לעיתים הן הגדרות שרירותיות לגמרי ("חבורה היא קבוצה עם פעולה המקיימת..."), ולעיתים הן מבטאות אמיתות בסיסיות של ההכרה שלנו ("שני גדלים השווים לגודל שלישי, שווים ביניהם"). שנית, כללי הגזירה במתמטיקה מתבססים על לוגיקה בוליאנית פשוטה של "אמת" ו"שקר"; אין באמצע, בערך, אולי או לפעמים.
שלישית, התחום המתמטי העוסק בנושאים הללו משתמש במונחים המוכרים לנו משפת היום־יום – "שפה", "תורה", "הוכחה", "אמת" ו"עקביות". אבל, כדרכה של מתמטיקה, המשמעות של המונחים הללו היא כאן מדוייקת, פורמלית, וכתוצאה מכך שונה למדי ממשמעותם הרגילה. "תורה", למשל (המכונה לעתים גם "מערכת"), היא אוסף של אקסיומות וכללי־היסק; "הוכחה" בתורה היא סדרה של "נוסחאות", שכל אחת מהן היא שרשרת של סימנים ב"שפה", והנוסחה האחרונה בסדרה היא הטענה אותה רצינו להוכיח (והיא, אם כך, "יכיחה"). הכללים הקובעים האם הוכחה כזו היא תקפה הם לגמרי מכניים, או "תחביריים": הם מתייחסים אך ורק לשרשראות הסימנים, ולא למשמעויות השונות שאנחנו יכולים לייחס לסימנים הללו. מושג ה"אמת", לעומת זאת, הוא מושג סמנטי, וגם לו יש הגדרה פורמלית התלויה ב"מודל" של השפה.
בשל מחלוקות מתמטיות שונות (וכמה שגיאות) שהתגלעו בסוף המאה ה-19, התחזק הרצון להבהיר בדיוק אילו אקסיומות דרושות במתמטיקה, ובפרט, לברר האם אפשר להיפטר מכמה הנחות שנויות במחלוקת. נסיון מסוג זה הופיע בספרם המונומנטלי של ראסל ו־ווייטהד "פרינקיפיה מתמטיקה" (PM), ונמשך כתכנית מעט מעורפלת המכונה היום "תכנית הילברט". על רקע זה נולד משפט גדל.
| "The notion of constructibility implied by the axiom of choice associated to what we have just set forth for poetic language, explains the impossibility of establishing a contradiction in the space of poetic language. This observation is close to Gödel's observation concerning the impossibility of proving the inconsistency [sic] of a system by means formalized within the system." – Julia Kristeva |
כולנו מכירים מילדותנו את המספרים הטבעיים: אחת, שתיים, שלוש והבאים אחריהם. בבואנו לחקור את תכונותיהם המתמטיות, אנו מעוניינים – בהתאם לשיטה שהוצגה לעיל – לבחור מספר קטן של אקסיומות מהן נוכל לגזור משפטים וטענות על המספרים האלה, תוך שימוש בכללי־היסק פורמליים. כיצד נבחר את האקסיומות? מצד אחד, השאיפה היא לבחור מעט כאלה, כדי שיקל עלינו להבטיח שהן באמת טבעיות ונכונות, ואינן מובילות לסתירה. מצד שני, אם נבחר מעט מדי, ייתכן שהן לא תספקנה כדי להוכיח כל מה שנכון. התכונה הרצויה הראשונה של התורה נקראת "עקביות", והשניה "שלמות". שני אלה הם מושגים פורמליים, בעלי הגדרה חד־משמעית: עקביות פירושה שאין הוכחה של דבר וגם של היפוכו; שלמות פירושה שיש הוכחה של כל דבר או היפוכו.
אוסף האקסיומות של תורה לא חייב להיות סופי. מסיבות טכניות, אפילו תורות פשוטות יחסית עבור המספרים הטבעיים מחייבות מספר אקסיומות אין־סופי. לאור זאת, עלינו לדרוש שיהיה תהליך חד־משמעי המאפשר לקבוע האם נוסחה מסויימת היא אקסיומה; אחרת, כשנתבונן בהוכחה מוצעת, לא נוכל אפילו לברר האם השורה הראשונה שלה היא לגיטימית. במקביל, יש לדרוש משהו דומה מכללי־ההיסק: אם מראים לנו צעד בודד בהוכחה, צריכה להיות לנו דרך לקבוע האם הוא אכן יישום של אחד מכללי־ההיסק או לא. תורה העומדת בשתי דרישות אלה נקראת "אפקטיבית".
משפטי גדל אינם חלים רק על תורות אקסיומטיות של המספרים הטבעיים. אבל – וזו נקודה חשובה – כדי שמשפט גדל יחול על תורה, היא חייבת לכלול כמות מסויימת של אריתמטיקה – כלומר, דרוש שאפשר יהיה לנסח ולהוכיח בה מספר משפטים בסיסיים בתורת המספרים. אנו נכנה תורות כאלה "אריתמטיות", למרות שזהו אינו מונח מקובל במיוחד. כעת נוכל לנסח במידה סבירה של דיוק את המשפטים של גדל.
המשפט הראשון: אם T תורה אריתמטית, אפקטיבית ועקבית, אז יש נוסחה G כך ש-T אינה מוכיחה את G וגם אינה מוכיחה את שלילתה של G. מכאן ש-T איננה שלמה.
המשפט השני: אם T תורה אריתמטית ואפקטיבית, אז יש נוסחה C האומרת "T היא עקבית". אם, בנוסף, T עקבית, הנוסחה C אינה ניתנת להוכחה ב-T.
למען הדיוק, אלו אינם המשפטים שהוכיח גדל ב-1931. גדל לא התייחס במאמרו לתורות אריתמטיות כלליות, אלא לתורה ספציפית המכונה P הקרובה למערכת PM שהוזכרה לעיל, ורק ציין שההוכחה תעבוד באותו האופן גם בתורות דומות אחרות. הוא תכנן לפרסם מאמר־המשך בו יכליל את המשפטים, אך בסופו של דבר לא עשה זאת – בין היתר, כי אחרים עשו זאת במקומו. יתרה מזאת, בניסוח המשפט הראשון דרש גדל תכונה חזקה יותר מעקביות של T, ולכן הטענה שלו היתה חלשה יותר; המשפט שהצגנו הוא חיזוק למשפט של גדל, שהוכח על־ידי רוסר ב-1936. גם למשפט השני יש כיום חיזוקים שונים.
הטענה G המופיעה בניסוח המשפט הראשון מכונה לפעמים "נוסחת גדל עבור T", ולעיתים טועים וקוראים לה "משפט גדל". כדי למנוע אי־הבנות, נבחין בין משפט גדל (שהוא המשפט הראשון, או השני, בהתאם להקשר), לבין נוסחת גדל, שהיא הנוסחה G המופיעה במשפט הראשון.
| “Ever since Gödel showed that there does not exist a proof of the consistency of Peano’s arithmetic that is formalizable within this theory (1931), political scientists had the means for understanding why it was necessary to mummify Lenin and display him to the “accidental” comrades in a mausoleum, at the Center of the National Community.” – Régis Debray |
מאז פרסום המאמר של גדל, ובמיוחד לאחר פרסומם של ספרים פופולריים העוסקים בו, מופיעות פרשנויות שונות ומשונות למשפטים שלו בתחומים מגוונים להפתיע כגון פוליטיקה, אפיסטמולוגיה, אבולוציה וביקורת שירה. בחלק מהמקרים מדובר באסוציאציות חופשיות לגמרי – בין אם הפרשן מודה בכך ובין אם לאו – ואז אין הרבה מה לעשות: קוראים, צוחקים או בוכים, ועוברים הלאה. במקרים אחרים, מנסים הפרשנים לגזור מסקנות קונקרטיות מתוכן המשפטים או מהוכחתם. בחלק ניכר ממקרים אלה נופלות שגיאות ענייניות בהבנת הטענות המתמטיות או בשימוש בהן, וקצת מטעויות אלה אנסה להאיר כעת.
ניסוחים פופולריים שגויים של משפטי גדל הם "אף תורה מתמטית אינה שלמה" ו"אף תורה מתמטית לא מסוגלת להוכיח שהיא עקבית". לעיתים הניסוחים השגויים נובעים מרשלנות גרידא, אך לעיתים קרובות יותר, הם מעידים על חוסר־הבנה רציני של המשפטים, שעל יסודו נבנים מגדלים פורחים. מה, בדיוק, שגוי כאן? כמה דברים.
"אף תורה מתמטית" – טעות. משפטי גדל מציבים דרישות מסויימות מהתורות עליהן הם חלים. כשהדרישות אינן מתקיימות, המסקנות פשוט אינן נכונות. מאז ההוכחה המקורית של גדל הדרישות עודנו וחודדו, אבל לא נעלמו: הן נותרו קריטיות להוכחת המשפטים. יש תורות מתמטיות חשובות, מעניינות ומאוד לא־טריוויאליות שהן שלמות, ומשפט גדל לא חל עליהן; נזכיר כדוגמאות את הגיאומטריה האוקלידית, את התורה RCF (שדות סגורים־ממשית), ואפילו מספר תורות הדנות במספרים הטבעיים כגון PrA (אריתמטיקת פרסבורגר). כדאי לציין שבעולם המתמטי, הדרישות של משפט גדל נחשבות "חלשות" – כלומר, "רוב" התורות המעניינות כן תקיימנה אותן, ולכן תהיינה חשופות למשפט. אך יש לזכור שני דברים: אחד, "רוב" זה כאמור לא הכל; ושניים, כשמנסים להחיל את משפט גדל על תחום שאיננו מתמטי גרידא, הדרישות הללו הופכות קשות מאוד למילוי, ואין בדרך־כלל שום סיבה להניח שתורה בתחום אחר (נניח, כלכלה) תהיה פגיעה למסקנות של משפטי גדל.
"לא מסוגלת להוכיח" – כאן יש טעות יותר עדינה, אבל לא פחות חשובה. כאמור, "הוכחה" בלוגיקה מתמטית היא מושג פורמלי, הקשור, אך לא זהה, למושג "הוכחה" המוכר לנו משפת היום־יום. ביום־יום אנחנו מציינים בביטוי "הוכחה" דבר־מה המדגים מעל לכל ספק שטענה מסויימת היא נכונה. בלוגיקה, הוכחה היא סדרה של נוסחאות ותו־לא. לעתים יש קשר הדוק בין המושגים, אבל הם אינם זהים.
דוגמא פשוטה: תורה מתמטית מוכיחה פורמלית כל אקסיומה שלה, אך בשפת היום־יום לא היינו אומרים שמי שהניח שהירח עשוי צמר גם הוכיח שהירח עשוי צמר. לכן, הוכחה פורמלית לא בהכרח מהווה הוכחה־במובן־הרגיל של נכונות, ובאותו אופן, היעדר הוכחה פורמלית לא בהכרח מעיד על היעדר הוכחה־במובן־הרגיל. כל זה, יש להדגיש, היה גלוי וידוע עוד לפני גדל.
כדי להדגים את הקושי בצורה חריפה אף יותר, נשתמש בפעלול קטן. ניקח תורה מתמטית פשוטה עליה חל משפט גדל, למשל התורה המכונה PA (אריתמטיקת פֵּאָנוֹ), הבנויה מאקסיומות פשוטות וסבירות מאוד. עכשיו נבנה תורה מלאכותית Z שהאקסיומות שלה הן בדיוק אלו של PA, יחד עם אקסיומה אחת נוספת האומרת "PA איננה עקבית". הטענה הזו (כמו C המופיעה במשפט גדל) ניתנת לניסוח פורמלי בשפה של PA, ועל־כן אפשר להוסיף אותה כאקסיומה.
כעת נקבל כמסקנה מוזרה ממשפט גדל שאם PA עקבית (וזוהי הנחת עבודה סבירה), אז גם Z עקבית (הוכחה: תרגיל לקורא). עכשיו לפנינו תורה עקבית Z שבה ניתן להוכיח את הטענה השקרית "PA איננה עקבית"! אין פה אסון, אלא אבחנה פשוטה שתורה עקבית אינה בהכרח נאותה, כלומר אינה מוכיחה רק משפטים אמיתיים. הנקודה החשובה היא שאם יש לנו סיבה להטיל ספק בעקביות (או בנאותות) של תורה מסויימת, הוכחה של עקביות זו בתוך אותה תורה לא תועיל בכלום – ממילא אנו מטילים ספק בתורה, אז מדוע שנאמין לה כשהיא מוכיחה שהיא עקבית? מצד שני, אם יש לנו סיבות טובות להאמין שתורה היא כן עקבית, חסרונה של הוכחת־עקביות־פנימית כזו לא צריך להפריע לנו כלל.
קורט גדל עם אלברט אינשטיין (מקור: ארכיון ההיסטוריה של המתמטיקה, אוניברסיטת סנט אנדרוז)
נעבור לטענה שגויה נוספת: "יש אמיתות שלוגיקה ומתמטיקה אינן מסוגלות להוכיח". נכון שבכל תורה העומדת בתנאים מסויימים יש משפטים נכונים שהיא לא מוכיחה; אך מכאן לא נובע שיש טענה נכונה שאיננה יכיחה באף תורה. מתמטיקאים קוראים לשגיאה זו "החלפת סדר הכמתים", והיא שגיאה גסה ונפוצה. מכך ש"לכל אדם, אפשר למצוא מכונית שלא הוא בנה" לא נובע ש"יש מכונית שאף אחד לא בנה אותה".
השגיאה הזו מופיעה, למשל (כנראה סתם מחוסר תשומת־לב), ברשימה שכתב שמעון שוקן, פרופסור למדעי־המחשב. במקרים אחרים, היא משמשת קרש־קפיצה לטענות מרחיקות־לכת על גבולות הרציונליזם ומותר האדם מן המכונה.
שתי שגיאות נפוצות נוספות הן הטענות "יש משפטים שבני־אדם רואים שהם אמיתיים, אבל תורות פורמליות לא יכולות להוכיח" ו"יש משפטים שבני־אדם רואים שהם אמיתיים, ומחשבים לא יוכלו לראות זאת לעולם". הצהרות מסוג זה נאמרו על־ידי הפילוסוף ג'ון סרל (Searle), הפיזיקאי רוג'ר פנרוז (Penrose) ואחרים. האם יש באמת משפטים שאנחנו רואים שהם אמיתיים, אבל אי־אפשר להוכיח אותם פורמלית? כותב שורות אלה, אישית, משוכנע שאין; בכל אופן, משפט גדל בהחלט לא מספק לנו כאלה, וכמוהו גם לא משפטים קרובים לו (כגון משפט טיורינג על בעיית העצירה).
אחד המועמדים הפופולריים למשפט כזה הוא נוסחת־גדל G הנזכרת במשפט הראשון. בהוכחתו המקורית בנה גדל את הנוסחה G כך שתהווה ניסוח פורמלי לטענה "G אינה יכיחה בתורה T". כיוון ש-G אכן מתגלה כלא־יכיחה, מסתבר שהיא נכונה, וש-T אינה יכולה להראות זאת – והרי לנו טענה שאנחנו, יצורים נבונים הקוראים את ההוכחה של גדל, רואים שהיא נכונה, ו-T אינה רואה זאת. האמנם מש"ל?
לא. הטעות היא שההוכחה לא מראה ש-G נכונה; היא רק מראה שאם T עקבית, אז G נכונה, ובדיוק את הרישא של המשפט הזה אנחנו לא יודעים (ו-T לא יכולה להוכיח). גדל היה מודע היטב לדקות הזו, והקדיש את סעיף 4 במאמרו המקורי לניתוח ההשלכות שלה. תוצאות הניתוח הן בדיוק המשפט השני שלו: את הטענה "אם T עקבית, אז G נכונה" בהחלט אפשר להוכיח ב-T, וקל להראות ש-G שקולה ב-T לנוסחת העקביות, אותה כינינו C.
אכן מבלבל, אבל זו עדיין לא סיבה לומר שגדל הוכיח שבני־אדם אינם מחשבים. נדגיש שוב את הנקודה העיקרית: את מה שאנחנו, בני־האדם, יכולים לראות, יכולה גם התורה הפורמלית (למשל, שאם T עקבית אז G אינה ניתנת להוכחה); את מה שהתורה הפורמלית לא יכולה להוכיח (את G עצמה), גם אנחנו לא יכולים. ככל הידוע למשפט גדל, בני־אדם אינם יודעים יותר מתורות פורמליות.
תפיסה שגויה אחרת בהקשר זה גורסת כי הוכחת משפט גדל כרוכה ב"קפיצה מחוץ למערכת", או שהיא מעין מטא־הוכחה הדורשת הסתכלות "מבחוץ". האמת היא הפוכה לחלוטין: משפט גדל הוא נכון בדיוק משום שאת השקילות "G נכונה אם ורק אם G איננה יכיחה ב-T" כן אפשר להוכיח בתוך T עצמה, בלי כל הסתכלות מבחוץ. זהו לב־לבו של ההישג של גדל: הוא הראה שתורות אריתמטיות פשוטות מסוגלות להביע פורמלית משפטים "על עצמן". תורות של המספרים הטבעיים אינן מוגבלות רק למשפטים אריתמטיים כגון "יש אין־סוף מספרים ראשוניים", אלא הן מסוגלות לנסח ולהוכיח משפטים מסוג "תורה זו לא מוכיחה ש...".
מה גדל בכלל לא
יש עוד שלל דוגמאות לטיעונים מופרכים הנשענים על אי־הבנה של משפט גדל, ולא נוכל למנות אפילו את רובם. כשבוחנים טיעונים מסוג זה, כדאי לשמור על פרופורציה, ולזכור את ההקשר: משפט גדל הוא משפט מתמטי הדן, בסופו־של־דבר, במניפולציות פורמליות של סימנים על נייר. כדי להקיש ממנו על היבט כלשהו של ההווייה האנושית, ולא סתם כמטפורה, דרושה קפיצה, שבמקרים רבים מאוד אינה זוכה לכל הצדקה.
טורקל פרנזן מצא את משפט גדל בקבוצת דיון על מוסיקת היפ־הופ. עד כמה קשה למצוא פרשני־גדל בפורומים אינטרנטיים ישראליים פופולריים? חיפוש בן פחות מעשר שניות בגוגל העלה מסמך, מינואר 2005, הכולל מספר לא מבוטל של היגדים מופרכים מהסוג שהזכרנו. החל מ"אדם לעולם לא יבין את עצמו", דרך "משפט זה, יותר מכל דבר אחר בעולם המדעי, ממחיש את הפער בין 'אני' ו'אחר' ", ועד למשפט הסיום התמוה "מה הדבר אומר על מתמטיקאים, אם לקח להם כל כך הרבה זמן להגיע לאותה מסקנה שכל איש רוח יודע, שאין אמת אחת? ולראיה, עדיין לא לגמרי יודעים איך להתמודד עם תובנה זו..."
צילו של קורט גדל עדיין מרחף על הארץ, מעורפל ומטושטש. די, הניחו לו.
רוב תודות לאורי גוראל־גורביץ' ולאילן עמית על עזרתם בחיבור מאמר זה.
|
קישורים
|
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש