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