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