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

מכיוון שאוסף כל המשפטים בתאורייה הוא בן מנייה ניתן לתת לכל משפט בתאוריה מספר, נסמן מספר זה בסוגריים מרובעים. לדוגמא: אם [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]