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

גרסה מ־12:31, 28 באפריל 2020

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

מכיוון שאוסף כל המשפטים בתאורייה הוא בן מנייה ניתן לתת לכל משפט בתאוריה מספר (הנקרא מספר גדל), נסמן מספר זה בסוגריים מרובעים. לדוגמא: אם [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{ f([B])=[B([B])] }[/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{ P([s])\iff s }[/math]

כפי שרצינו.

סיום הוכחת משפט אי השלימות הראשון של גדל בעזרת הלמה של טרצקי

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

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

מכאן המשפט נובע באופן ישיר: או שהתאוריה אינה שלימה (היא מכילה סתירה) או שהיא אינה עקבית (קיים משפט שלא ניתן להוכיחו ולא ניתן להפריכו).

@@ שורה 11: / שורה 11: @@
 ===הוכחה===
 נגדיר פונקציה <math>f:\mathbb{N}\rightarrow\mathbb{N}\cup\{0\}</math> באופן הבא:
-::אם <math>\{n\}</math> הוא נוסחא עם משתנה מספרי יחיד <math>Q(x)=\{n\}</math> אזי <math>f(n):=[Q(n)]</math>
+::אם <math>\{n\}</math> הוא נוסחא עם משתנה מספרי יחיד <math>P(x)=\{n\}</math> אזי <math>f(n):=[P(n)]</math>
 ::אחרת, <math>f(n):=0</math>
-*שימו לב ש<math>Q(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוסחא בתאוריה ולכן יש לו מספר גדל.
+*שימו לב ש<math>P(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.
 *כמו כן, שימו לב כי שיטה זו דומה לשיטת האלכסון של קנטור. בכל נוסחא אנו מציבים את מספר הגדל של הנוסחא.
 דוגמא:
-נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית <math>Q(x)=''x>2''</math>. במקרה זה <math>f(3)=[Q(3)]=[''3>2'']</math>
+נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית <math>P(x)=''x>2''</math>. במקרה זה <math>f(3)=[P(3)]=[''3>2'']</math>
-נגדיר כעת את הנוסחא הבאה <math>B(x)=P(f(x))</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>P(f([B]))</math>. נשים לב כי <math>f([B])=[B([B])]</math>. נובע כי <math>P([B([B])])</math> כפי שרצינו.
+נניח <math>B([B])</math>. לכן עבור <math>\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> כפי שרצינו.