שינויים

קפיצה אל: ניווט, חיפוש

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

הוסרו 285 בתים, 12:36, 28 באפריל 2020
===הוכחה===
נגדיר פונקציה <math>f:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\}</math> באופן הבא:
::אם <math>\{n\}</math> הוא נוסחא עם משתנה מספרי יחיד <math>PQ(x)=\{n\}</math> אזי <math>f(n):=[PQ(n)]</math>
::אחרת, <math>f(n):=0</math>
*שימו לב ש<math>PQ(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא נוסחא בתאוריה ולכן יש לו מספר גדל.
*כמו כן, שימו לב כי שיטה זו דומה לשיטת האלכסון של קנטור. בכל נוסחא אנו מציבים את מספר הגדל של הנוסחא.
דוגמא:
נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית <math>PQ(x)=''x>2''</math>. במקרה זה <math>f(3)=[PQ(3)]=[''3>2'']</math>
נגדיר כעת את הנוסחא הבאה <math>B(x)=\forall z:P(z=f(x)\rightarrow P(z))</math>.
:'''טענה''': <math>B([B])\iff P([B([B])])</math> לכל x
'''הוכחה''':
נניח <math>B([B])</math>. לכן עבור <math>\forall z:P(z=f([B])\rightarrow P(z))</math>. נשים לב כי <math>f([B])=[B([B])]</math>. בפרט, עבור <math>z=[B([B])]</math> נובע כי <math>P([B([B])])</math> כפי שרצינו.
מצד שני, נניח <math>P([B([B])])</math>. אם כיוון ש<math>z\neq[Bf([B])]</math> אזי שקר גורר כל דבר ובפרט את <math>P(z)</math>. אם <math>z=[B([B])]</math> אזי נובע כי <math>z=[BP(f([B])]\rightarrow P(z))</math> שכן אמת גוררת אמת. ולכן סה"כ, הגרירה נכונה לכל <math>z</math> ולכן לכן לפי ההגדרה <math>B([B])</math>.