שינויים

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

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

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