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

חזרה למשפטי אי השלימות של גדל (Gödel)

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

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

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

--לכל פרדיקט עם משתנה מספרי אחד $P(x)$ קיים בתאוריה משפט s כך ש:

s אם"ם $P([s])$

הוכחה

נגדיר פונקציה $f:\mathbb{N}\rightarrow\mathbb{N}$ באופן הבא:

אם עיבוד הנוסחה נכשל (שגיאת תחביר): {\{n\}

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

אחרת, $f(n):=1$

שימו לב ש$P(n)$ הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.