הוכחת משפט אי השלימות הראשון של גדל

מכיוון שאוסף כל המשפטים בתאורייה הוא בן מנייה ניתן לתת לכל משפט בתאוריה מספר (הנקרא מספר גדל), נסמן מספר זה בסוגריים מרובעים. לדוגמא: אם [math]\displaystyle{ ''3 \gt 5'' }[/math] הוא המשפט השלישי בתאורייה אזי [math]\displaystyle{ [''3 \gt 5'']=3 }[/math]. באופן דומה, נשתמש בסוגריים מסולסלים על מנת לחזור מהמספר אל המשפט. בדוגמא: [math]\displaystyle{ \{3\}=''3 \gt 5'' }[/math].

הלמה של טרצקי (Diagonal lemma)

--לכל פרדיקט עם משתנה מספרי אחד [math]\displaystyle{ P(x) }[/math] קיים בתאוריה משפט s כך ש:

s אם"ם [math]\displaystyle{ P([s]) }[/math]

הוכחה

נגדיר פונקציה [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N} }[/math] באופן הבא:

אם [math]\displaystyle{ {\{n\} }[/math] הוא נוסחא עם משתנה מספרי יחיד [math]\displaystyle{ P(x)=\{n\} }[/math] אזי [math]\displaystyle{ f(n):=[P(n)] }[/math]

אחרת, [math]\displaystyle{ f(n):=1 }[/math]

שימו לב ש[math]\displaystyle{ P(n) }[/math] הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.