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

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

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

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

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

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

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

הוכחה

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

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

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

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

דוגמא: נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית $P(x)=''x>2''$. במקרה זה $f(3)=[P(3)]=[''3>2'']$

נגדיר כעת את הנוסחא הבאה $B(x)=\forall z:(z=f(x)\rightarrow P(z))$.

טענה: $B([B])\iff P([B([B])])$ לכל x

הוכחה: נניח $B([B])$. לכן עבור $\forall z:(z=f([B])\rightarrow P(z))$. נשים לב כי $f([B])=[B([B])]$. בפרט, עבור $z=[B([B])]$ נובע כי $P([B([B])])$ כפי שרצינו.

מצד שני, נניח $P([B([B])])$. אם $z\neq[B([B])]$ אזי שקר גורר כל דבר ובפרט את $P(z)$. אם $z=[B([B])]$ אזי $z=[B([B])]\rightarrow P(z)$ שכן אמת גוררת אמת. ולכן סה"כ, הגרירה נכונה לכל $z$ ולכן $B([B])$.

מסקנה: המשפט $s=B([B])$ מקיים

--$P([s])\iff s$ כפי שרצינו.