הוכחת משפט אי השלימות הראשון של גדל: הבדלים בין גרסאות בדף

גרסה מ־06:56, 13 באוקטובר 2011

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

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

הוכחה

נגדיר פונקציה [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\} }[/math] באופן הבא:

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

אחרת, [math]\displaystyle{ f(n):=0 }[/math]

שימו לב ש[math]\displaystyle{ P(n) }[/math] הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.
כמו כן, שימו לב כי שיטה זו דומה לשיטת האלכסון של קנטור. בכל נוסחא אנו מציבים את מספר הגדל של הנוסחא.

דוגמא: נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית [math]\displaystyle{ P(x)=''x\gt 2'' }[/math]. במקרה זה [math]\displaystyle{ f(3)=[P(3)]=[''3\gt 2''] }[/math]

נגדיר כעת את הנוסחא הבאה [math]\displaystyle{ B(x)=\forall z:(z=f(x)\rightarrow P(z)) }[/math].

טענה: [math]\displaystyle{ B([B])\iff P([B([B])]) }[/math] לכל x

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

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

מסקנה: המשפט [math]\displaystyle{ s=B([B]) }[/math] מקיים [math]\displaystyle{ s \iff P([s]) }[/math] כפי שרצינו.

@@ שורה 10: / שורה 10: @@
 ::::::s אם"ם <math>P([s])</math>
 ===הוכחה===
-נגדיר פונקציה <math>f:\mathbb{N}\rightarrow\mathbb{N}</math> באופן הבא:
+נגדיר פונקציה <math>f:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\}</math> באופן הבא:
 ::אם <math>\{n\}</math> הוא נוסחא עם משתנה מספרי יחיד <math>P(x)=\{n\}</math> אזי <math>f(n):=[P(n)]</math>
-::אחרת, <math>f(n):=1</math>
+::אחרת, <math>f(n):=0</math>
 *שימו לב ש<math>P(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.
@@ שורה 20: / שורה 20: @@
 דוגמא:
 נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית <math>P(x)=''x>2''</math>. במקרה זה <math>f(3)=[P(3)]=[''3>2'']</math>
+נגדיר כעת את הנוסחא הבאה <math>B(x)=\forall z:(z=f(x)\rightarrow P(z))</math>.
+:'''טענה''': <math>B([B])\iff P([B([B])])</math> לכל x
+'''הוכחה''':
+נניח <math>B([B])</math>. לכן עבור <math>\forall z:(z=f([B])\rightarrow P(z))</math>. בפרט, עבור <math>z=[B([B])]</math> נובע כי <math>P([B([B])])</math> כפי שרצינו.
+מצד שני, נניח <math>P([B([B])])</math>. אם <math>z\neq[B([B])]</math> אזי שקר גורר כל דבר ובפרט את <math>P(z)</math>. אם <math>z=[B([B])]</math> אזי <math>z=[B([B])]\rightarrow P(z)</math> שכן אמת גוררת אמת. ולכן סה"כ, הגרירה נכונה לכל <math>z</math> ולכן <math>B([B])</math>.
+'''מסקנה''': המשפט <math>s=B([B])</math> מקיים <math>s \iff P([s])</math> כפי שרצינו.