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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

[עריכה] מבוא לא פורמלי

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

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

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

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

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

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

[עריכה] ההשפעה של המשפט

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

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

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

[עריכה] לקריאה נוספת

  • ארנסט נאגל וג'יימס ניומן, משפט גדל. מהדורה עברית בהוצאת הטכניון, 1993.
  • ארנון אברון, "משפטי גדל ובעיית יסודות המתמטיקה", משרד הביטחון - ההוצאה לאור.
  • 1979 ,Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid
  • ההוכחה והפרדוקס - משפטי האי שלמות של קורט גדל, רבקה גולדסטיין, 2006.

[עריכה] קישורים חיצוניים