ספקות במתמטיקה: על משפטי אי-השלמות של גֵּדֵל

בשנת 1931, לוגיקן אוסטרי צעיר פרסם מאמר שהכניס את עולם המתמטיקה לתדהמה. לבחור שלנו קוראים קוּרְט גֵּדֵל (1906–1978), ועבור המתמטיקאים של אותה תקופה, מסקנותיו של גֵּדֵל ניפצו את הציפיות הגבוהות שהיו להם מהמתמטיקה שהם עצמם ניסו לפתח. המשפטים המתמטיים שגדל ניסח נקראים: משפטי אי-השלמות של גדל, וניתן לסכם אותם בקצרה באופן הבא. גדל הוכיח כי:

המתמטיקה אינה יכולה להיות בו-זמנית גם עִקְבִית וגם שְׁלֵמָה.

אם שמעתם בעבר על משפטי אי-השלמות של גדל ותמיד רציתם לדעת במה מדובר, מה המשמעות של המושגים: שלמות ועקביות, ומה ההשלכות שיש למשפטי גדל על עולם המתמטיקה, זה הפוסט בשבילכם.

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

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

עם ההוכחה, בא הביטחון

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

קיימים אינסוף מספרים ראשוניים.

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

ובכן, את ההוכחה לטענה מצא המתמטיקאי היווני אֵוּקְלִידֶס לפני כ-2300 שנים. במקרה זה, אין צורך להיכנס לז'רגון מתמטי מסובך (מי שרוצה יכול למצוא זאת בקישור כאן); אפשר לתרגם לעברית פשוטה את ההוכחה שלו, באופן הבא:

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

במילים פשוטות:

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

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

אוקיי, עכשיו אפשר להתקדם הלאה, ולהסביר את שני המושגים העיקריים שעליהם משפטי אי-השלמות של גדל מבוססים:

1. שלמות,
2. עקביות.

שלמות

המתמטיקה נקראת: שְׁלֵמָה, אם לכל טענה מתמטית אפשרית קיימת הוכחה שבאמצעותה ניתן לקבוע האם הטענה אמיתית או שקרית.

אוקיי, בואו נוריד את הדברים לקרקע. כדי להבין בקלות את המושג שלמות בהקשר מתמטי, נוכל לבחון בתור דוגמה את השערת גּוֹלְדְבָּךְ, שהיא טענה מתמטית על המספרים הטבעיים, כפי שניסח המתמטיקאי הפרוסי כריסטיאן גולדבאך (1690-1794):

כל מספר זוגי ניתן להציג כסכום של שני מספרים ראשוניים.

להלן מספר דוגמאות:

• 13 + 19 = 32,
• 251 + 317 = 568,
• 2909 + 42727 = 45636.

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

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

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

כאן מגיעה שאלת מיליון הדולר:

האם ניתן להוכיח כי המתמטיקה שלמה?

ללא הוכחה, תמיד יהיה לנו ספק שמא אי-שם מסתתרת לה טענה מתמטית שאי אפשר להוכיח אותה, אף על פי שהיא אמיתית!

עקביות

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

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

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

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

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

האם ניתן להוכיח כי המתמטיקה עקבית?

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

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

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

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

עד שהגיע קורט גדל וניפץ אמונה זו לרסיסים.

החלום ושברו

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

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

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

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

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

דויד הילברט, 8 ספטמבר, 1930.

אוֹי וֵיי זְמִיר … מה שהילברט לא ידע, הוא שיום אחד קודם לכן באותו כנס עצמו², לוגיקן צעיר בשם קורט גדל כבר סיפר לג'ון פון-נוימן (1903-1957) – תלמידו לשעבר של הילברט ומתמטיקאי דגול בזכות עצמו – כי המשימה של הילברט חסרת סיכוי, וחלומו הגרנדיוזי נידון לכישלון מוחלט. הסקופ של גדל לא הצליח לעורר יותר מדי תשומת לב באותו הכנס, אך שנה לאחר מכן – בגיל 25 בלבד – גדל פרסם מאמר בו הציג סופית את משנתו, לה אנו קוראים היום: משפטי אי-השלמות של גדל. את העיקרון הכללי מאחורי ההוכחה של גדל, אני מסביר בקישור כאן, אבל בשורה התחתונה ניתן לסכם את משפטי גדל כך:

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

לימים, כך תיאר ג'ון פון-נוימן את עבודתו של גדל:

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

ההשלכות של משפטי גדל

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

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

מי בכלל מבטיח לאותו מתמטיקאי כי קיימת הוכחה?

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

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

הילברט עצמו הבין זאת, ואפשר גם לצטט אותו בנושא זה, 30 שנים לפני שגדל פרסם את משפטי אי-השלמות שלו:

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

דויד הילברט, הכנס הבינלאומי למתמטיקה, פריס, 1900.

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

אוקיי, למה שלא נחליט כי השערת גולדבך אמיתית ופשוט נוסיף אותה לרשימת האקסיומות של המתמטיקה?

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

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

סיכום

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

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

1. אני משתמש כאן במילה מתמטיקה מבלי להיכנס להגדרות מדויקות של המונח, לכן יש להדגיש כבר על ההתחלה כי יש מגוון של תורות מתמטיות, ומשפטי גדל לא בהכרח חלים על כולן. באופן כללי ניתן לומר כי תורה מתמטית מורכבת מ: 1. אקסיומות, 2. כללים שמהם ניתן לגזור טענות מתוך האקסיומות, 3. שפה פורמלית שבאמצעותה ניתן לנסח את האקסיומות והטענות. משפטי גדל חלים רק על תורות מתמטיות שמקיימות תנאים מאוד ספציפיים. התנאי הראשון הוא שהתורה תהיה "אפקטיבית", כלומר קיימת שיטה שבאמצעותה ניתן להכריע בזמן סופי האם טענה של התורה היא אקסיומה או לא. התנאי השני הוא שהתורה תהיה "עשירה מספיק" כך שניתן לתאר באמצעותה את האריתמטיקה (המספרים הטבעיים עם פעולות החיבור והכפל). [↩]
2. נראה שהיו שני כנסים נפרדים שהתקיימו ביחד באותו מקום בקניגסברג. הכנס שבו נאם קורט גדל נקרא: "Second Conference on the Epistemology of the Exact Sciences" ונערך בתאריכים 5-7 לספטמבר. יום למחרת נערך באותו מקום כנס הנקרא: "Yearly Meeting of the Society of German Natural Scientists and Physicians", בו נאם הילברט את נאום הפרישה שלו. [↩]
3. במידה ותהיתם לעצמכם מה המשמעות של תמונת הנושא של הפוסט – זו שבה רואים מעין קוביה מלאת חורים – אז מדובר בקוביה שאם מאירים אותה מכיוונים שונים, אז הצל שמתקבל על הקיר מראה קוד QR שמפנה לערך בויקיפדיה של קורט גדל, מאוריץ אשר, וגם יוהאן סבסטיאן באך. מדובר בהתייחסות לספר: "גדל, אשר, באך" שכתב דאגלס הופשטטר ועוסק רבות במשפטי אי-השלמות של גדל. [↩]