תורת הקבוצות/אינדוקציה טרנספיניטית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
בנציון יעבץ (שיחה | תרומות) אין תקציר עריכה |
בנציון יעבץ (שיחה | תרומות) |
||
שורה 6:
==אינדוקציה בנויה היטב==
{{הגדרה|שם=יחס בנוי היטב|תוכן=נאמר כי יחס בינארי <math>\mathcal R</math> על קבוצה <math>A</math> הוא '''בנוי היטב''', אם ורק אם לכל תת קבוצה לא ריקה <math>S\subseteq A</math> קיים איבר <math>x_0\in S</math> כך שלכל <math>x\in S</math> מתקיים <math>\lnot x\mathcal R x_0</math>.}}
ניתן להכליל את עקרון האינדוקציה הטרנספיניטית לכל יחס בנוי היטב: יהי <math>(A,\mathcal R)</math> יחס בנוי היטב, ותהי <math>\phi</math> טענה. נסמן ב<math>a_0</math> את האיבר ב<math>A</math> כך שלכל <math>x\in A</math> מתקיים <math>\lnot x\mathcal R a_0</math>. אז מתקיים <math>\phi(a_0)\land\forall a\in A((\forall x\mathcal R a,\phi(x))\Rightarrow\phi(a))\Rightarrow\forall x\in A,\phi(x)</math>: כלומר מפסיק להוכיח את הטענה לגבי האיבר ה"מינימלי" (כלומר האיבר שאף איבר לא עומד ביחס איתו) של הקבוצה, ולהוכיח שאם הטענה נכונה לכל האיברים העומדים ביחס עם איבר כלשהו של הקבוצה אז הטענה נכונה גם לגבי האיבר, כדי להוכיח שהטענה נכונה לכל איברי הקבוצה.
{{הוכחה|נניח בשלילה שהקבוצה <math>S=\{x|\lnot\phi(x)\}</math> לא ריקה. אז קיים <math>x_0\in S</math> כך שלכל <math>x\in S</math> מתקיים <math>\lnot x\mathcal R x_0</math>. לכן לכל <math>x\mathcal R x_0</math> מתקיים <math>x\not\in S</math>, כלומר <math>\phi(x)</math>, לכן <math>\phi(x_0)</math> בסתירה לכך ש<math>x_0\in S</math>.}}
| |||