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

גרסה מ־16:31, 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 בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.
כמו כן, שימו לב כי שיטה זו דומה לשיטת האלכסון של קנטור. בכל נוסחא אנו מציבים את מספר הגדל של הנוסחא.

דוגמא: נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית $P(x)=''x>2''$ . במקרה זה $f(3)=[P(3)]=[''3>2'']$

@@ שורה 14: / שורה 14: @@
 ::אחרת, <math>f(n):=1</math>
-שימו לב ש<math>P(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.
+*שימו לב ש<math>P(n)</math> הוא הצבת n בנוסחא עם משתנה, ולכן גם מהווה נוחסחא בתאוריה ולכן יש לו מספר גדל.
+*כמו כן, שימו לב כי שיטה זו דומה לשיטת האלכסון של קנטור. בכל נוסחא אנו מציבים את מספר הגדל של הנוסחא.
+דוגמא:
+נניח והמשפט השלישי בתאוריה הוא נוסחא מספרית <math>P(x)=''x>2''</math>. במקרה זה <math>f(3)=[P(3)]=[''3>2'']</math>

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

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

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

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

הוכחה

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים