תורת הקבוצות/אינדוקציה טרנספיניטית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
בנציון יעבץ (שיחה | תרומות) |
בנציון יעבץ (שיחה | תרומות) |
||
שורה 3:
נוכיח את עקרון האינדוקציה הטרנספיניטית: נניח בשלילה שקיימים איברים שעבורם הטענה לא מתקיימת. נסמן את קבוצת כל האיברים האלו ב<math>S</math>. על פי ההנחה, S אינה ריקה, וברור ש<math>S\subseteq A</math>, לכן יהי <math>x_0</math> האיבר הראשון בS. מכך נובע שלכל <math>x\prec x_0</math>, הטענה נכונה לגבי x (אחרת <math>x_0</math> אינו הראשון), ומהנחת האינדוקציה נובע ש <math>\phi(x_0)</math>, בסתירה לכך ש<math>x_0\in S=\{x|\lnot\phi(x)\}</math>. סתירה.
==דוגמה==
* אינדוקציה מתמטית היא בעצם סוג מסוים של אינדוקציה טרנספיניטית: הקבוצה <math>\N</math> סדורה היטב (יוכח במהלך הפרק על ה[[תורת הקבוצות/סודרים|סודרים]], שם גם נגדיר את הקבוצה), לכן ניתן לפעול לגביה באינדוקציה טרנספיניטית. בהינתן <math>n\not=0</math> (הנחנו שכבר הוכחנו את הטענה לגבי 0), ניתן לרשום <math>n=(n-1)+1:=k+1</math> כאשר <math>k<n</math>. ההנחה <math>\forall m<n,\phi(m)</math> כוללת בתוכה את הטענה <math>\phi(k)</math>, לכן הגרירה <math>\phi(k)\Rightarrow\phi(k+1)\Rightarrow\phi(n)</math> גוררת את הגרירה <math>(\forall m<n,\phi(m))\Rightarrow\phi(n)</math>, לכן הטענה <math>\phi(0)\land\forall n\in\N(\phi(n)\Rightarrow\phi(n+1))</math> גוררת את <math>\phi(0)\land\forall n\in\N(\phi(n)\Rightarrow\phi(n+1))</math>, כלומר את <math>\forall n\in\N,\phi(n)</math>.
==אינדוקציה בנויה היטב==
{{הגדרה|שם=יחס בנוי היטב|תוכן=נאמר כי יחס בינארי <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>.}}
| |||