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

גרסה מ־16:27, 12 באוקטובר 2011

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

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

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

--לכל פרדיקט עם משתנה מספרי אחד

P(x)

קיים בתאוריה משפט s כך ש:

s אם"ם

P([s])

הוכחה

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

אם עיבוד הנוסחה נכשל (שגיאת תחביר): {\{n\}

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

אחרת,

f(n):=1

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

@@ שורה 9: / שורה 9: @@
 ::::::s אם"ם <math>P([s])</math>
+===הוכחה===
+נגדיר פונקציה <math>f:\mathbb{N}\rightarrow\mathbb{N}</math> באופן הבא:
+::אם <math>{\{n\}</math> הוא נוסחא עם משתנה מספרי יחיד <math>P(x)=\{n\}</math> אזי <math>f(n):=[P(n)]</math>
+::אחרת, <math>f(n):=1</math>
+שימו לב ש<math>P(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.

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

גרסה מ־16:27, 12 באוקטובר 2011

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

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

הוכחה

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים