משפט אי השלמות של גדל - מה הוא ממש, ממש לא

באדיבות הבלוג Good math, bad math נחשפתי לאחד מההסברים הגרועים ביותר - אם לא הגרוע ביותר - שנתקלתי בהם אי פעם למשפט אי השלמות של גדל. כל המאפיינים הקלאסיים של בלבלת גדל מצויים שם - ניסוח שגוי לחלוטין של המשפט, שמעיד על חוסר הבנה מוחלט שלו; ייחוס השלכות “הרסניות” למשפט על המתמטיקה; טענה שהמשפט תקף לאלף ואחד תחומי חיים אחרים ולא רק למתמטיקה; וכמובן, הסקת מסקנות מרחיקת לכת באשר לחיים, ליקום ובכלל. באופן מפתיע, או שלא, המאמר נמצא באתר בשם Cosmic Fingerprints שככל הנראה טורח לשכנע את קוראיו בקיום בורא תבוני ליקום.

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

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

In 1931, the young mathematician Kurt Gödel made a landmark discovery, as powerful as anything Albert Einstein developed.

In one salvo, he completely demolished an entire class of scientific theories.

Gödel’s discovery not only applies to mathematics but literally all branches of science, logic and human knowledge. It has earth-shattering implications.

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

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

כעת אנו עוברים לסקירה היסטורית מביכה ביותר:

Mathematicians love proofs. They were hot and bothered for centuries, because they were unable to PROVE some of the things they knew were true.

So for example if you studied high school Geometry, you’ve done the exercises where you prove all kinds of things about triangles based on a set of theorems. That high school geometry book is built on Euclid’s five postulates. Everyone knows the postulates are true, but in 2500 years nobody’s figured out a way to prove them. Yes, it does seem perfectly “obvious” that a line can be extended infinitely in both directions, but no one has been able to PROVE that. We can only demonstrate that Euclid’s postulates are a reasonable, and in fact necessary, set of 5 assumptions. Towering mathematical geniuses were frustrated for 2000+ years because they couldn’t prove all their theorems. There were so many things that were “obviously true,” but nobody could find a way to prove them.

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

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

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

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

כעת הסקירה ההיסטורית עוברת לתוכנית של הילברט:

In the early 1900’s, however, a tremendous wave of optimism swept through mathematical circles. The most brilliant mathematicians in the world (like Bertrand Russell, David Hilbert and Ludwig Wittgenstein) became convinced that they were rapidly closing in on a final synthesis.

A unifying “Theory of Everything” that would finally nail down all the loose ends. Mathematics would be complete, bulletproof, airtight, triumphant.

In 1931 this young Austrian mathematician, Kurt Gödel, published a paper that once and for all PROVED that a single Theory Of Everything is actually impossible. He proved they would never prove everything. (Yeah I know, it sounds a little odd, doesn’t it?)

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

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

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

“Anything you can draw a circle around cannot explain itself without referring to something outside the circle - something you have to assume but cannot prove.”

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

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

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

טוב, תגידו - מה שהוא כתב זו אנלוגיה, אולי לא הבנתי אותו נכון? ובכן, לא - בציטוט הבא הוא נותן תיאור יותר קונקרטי:

Gödel proved that there are ALWAYS more things that are true than you can prove. Any system of logic or numbers that mathematicians ever came up with will always rest on at least a few unprovable assumptions.

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

הכותב ממשיך עם שוונג ה”משפט גדל חל על הכל”:

Gödel’s Incompleteness Theorem applies not just to math, but to everything that is subject to the laws of logic. Everything that you can count or calculate. Incompleteness is true in math; it’s equally true in science or language and philosophy.

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

כעת אנו עוברים לתיאור נפנוף-ידיימי מאוד של הוכחת המשפט:

Gödel, in one of the most ingenious moves in the history of math, converted this Liar’s Paradox into a mathematical formula. He proved that no statement can prove its own truth.

You always need an outside reference point.

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

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

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

The Incompleteness Theorem was a devastating blow to the “positivists” of the time. They insisted that literally anything you could not measure or prove was nonsense. He showed that their positivism was nonsense.

Gödel proved his theorem in black and white and nobody could argue with his logic. Yet some of his fellow mathematicians went to their graves in denial, believing that somehow or another Gödel must surely be wrong.

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

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

A “theory of everything” - whether in math, or physics, or philosophy - will never be found. Because it is mathematically impossible.

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

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

If you visit the world’s largest atheist website, Infidels, on the home page you will find the following statement:

“Naturalism is the hypothesis that the natural world is a closed system, which means that nothing that is not part of the natural world affects it.”

If you know Gödel’s theorem, you know all systems rely on something outside the system. So according to Gödel’s Incompleteness theorem, the folks at Infidels cannot be correct. Because the universe is a system, it has to have an outside cause.

Therefore Atheism violates the laws mathematics.

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