הבדלים בין גרסאות בדף "משפטי האי-שלמות של גדל"

מ
אין תקציר עריכה
מ (r2.7.2+) (בוט משנה: no:Gödels ufullstendighetsteoremer)
מ
'''משפטי האי-שלמות של [[קורט גדל]]''' הנם צמד [[משפט (מתמטיקה)|משפטים]] יסודיים ב[[לוגיקה מתמטית]], הענף החוקר את יסודות ה[[לוגיקה]] בכלים [[מתמטיקה|מתמטיים]].
 
גדל הראה שבכל מערכת אקסיומות סופית ועשירה מספיק (כזו המכילה את אקסיומותחלק מספיק גדול מאקסיומות ה[[אריתמטיקה]] החלשה) שהיא [[עקביות (לוגיקה מתמטית)|עקבית]], היא בהכרח לא [[שלמות|שלמה]], משמע שקיימות [[עצמאות_(לוגיקה_מתמטית)|טענות שלא ניתנות להכרעה]], כלומר שלא ניתן להוכיחן או להפריכן. בכך גדל שם קץ לניסיונות רבים [[תוכנית הילברט|לבנות מערכת אקסיומטית כוללת]] שממנה תנבע כל המתמטיקה.
 
המשפטים אינם אומרים, למרות הניסוח הפופוליסטי שלהם, ש־"קיימות טענות אמתיותאמיתיות שלא ניתן להוכיח", דבר ש[[משפט השלמות של גדל]], שקדם למשפטי האי־שלמות, סותר לחלוטין. למעשה, עבור טענה שלא ניתנת להכרעה, ניתן לבנות למערכת [[מודל (לוגיקה מתמטית)|מודל]] בו היא תהיה נכונה, ומודל אחר בו היא תהיה שגויה.
 
==מבוא לא פורמלי==
'''משפט האי-שלמות הראשון של גדל''', שהפך לאבן פינה ב[[לוגיקה מתמטית|לוגיקה המתמטית]], הוסיף אפשרות שלישית לגורל הצפוי לטענה מתמטית. המשפט קובע כי בכל מערכת לוגית מקיפה, ניתן לבנות באמצעות [[אלגוריתם]] טענות שמחד אינן ניתנות להוכחה ומאידך אינן ניתנות להפרכה מתוך אותה קבוצת אקסיומות. הטענה דומה מאוד ל[[פרדוקס השקרן]] (פרדוקס שבו אדם מסוים אומר "אני עכשיו משקר"), אך שונה ממנה, שכן לא נטען בה שהיא איננה נכונה. ההוכחה הפורמלית של המשפט מראה בצורה קונסטרוקטיבית כיצד ניתן לבנות טענה פורמלית האומרת "לא ניתן להוכיח אותי".
 
דוגמהבמשך לטענהשנים מסוגלאחר זהפרסום היאהמשפטים רווחה ההנחה שאמנם קיימות טענות שלא ניתן להוכיח או להפריך אך הן "לא טבעיות", כלומר לא סביר שבמהלך פיתוח סטנדרטי של תורה מתמטית ניתקל במשפטים כאלו. ההנחה הזו התבררה כשגויה באופן קיצוני בעקבות הוכחת ה[[עצמאות (לוגיקה מתמטית)|עצמאות]] של [[השערת הרצף]]. השערת הרצף שהוצעה על ידי [[גיאורג קנטור]], וקובעתטוענת שלאכי לא קיימת קבוצה ש[[עוצמה (מתמטיקה)|עוצמתה]] גדולה מזו של המספרים הטבעיים וקטנה מזו של המספרים הממשיים. השערה זו נחשבה לאחת מהבעיות הפתוחות המרכזיות במתמטיקה בתחילת המאה ה-20 (זו הבעיה הראשונה ברשימת [[23 הבעיות של הילברט]]). בשנת [[1937]] הוכיח גדל כי לא ניתן '''להפריך''' השערה זו במסגרת [[תורת הקבוצות האקסיומטית| אקסיומות ZF+CZFC]] ובשנת [[1963]] הוכיח [[פול כהן]] כי לא ניתן '''להוכיח''' השערה זו במסגרת ZF+CZFC.
 
ב'''משפט האי-שלמות השני''' הוכיח גדל כי [[תורה (לוגיקה מתמטית)|תורה]] עקבית שהנה מספיק חזקה לקיים את [[אקסיומות פאנופיאנו]] (שהאריתמטיקה הרגילה מכילה אותה) ובפרט כזאת שמקיימת את ה[[תורת הקבוצות האקסיומטית|אקסיומות של תורת הקבוצות (ZF)]] לא יכולה להוכיח את העקביות של עצמה. משמעות הדבר היא שאין אפשרות להוכיח בתוך המערכת כי האקסיומות הן עקביות. אולם, האפשרות שאי אפשר להפריך את העקביות של עצמה תלויה במערכת האקסיומות שלה (יכול להיות שטענה זאת בלתי תלויה במערכת האקסיומות שלך ויכול להיות שהיא לא נכונה).
 
תנאי המשפט אינם מחייבים מספר סופי של אקסיומות. כלומר, גם אילו היו בידינו אינסוף אקסיומות של [[תורת המספרים]], היה המשפט מתקיים בתנאי הרגיל, שניתן יהיה לזהות בקלות האם טענה נתונה היא אקסיומה של המערכת (תכונה זו נקראת [[תורה אפקטיבית|אפקטיביות]]).
* [[משפט האי-שלמות של צ'ייטין]]
* [[משפט הרקורסיה]] - משמשת בחלק מההוכחות למשפטי האי-שלמות של גדל.
* [[משפט סקולם-לוונהיים]] - משפט נוסף על מגבלות כוח התיאור של [[לוגיקה מסדר ראשון|הלוגיקה מסדר ראשון]].
* [[משפט אי-הגדירות של האמת של טרסקי]]
 
==לקריאה נוספת==
* ארנסט נאגל וג'יימס ניומן, '''משפט גדל''', תרגמו: יעל הרפז רובין ונצה מובשוביץ הדר, הוצאת [[הטכניון]], 1993.