תורת הקבוצות/אינדוקציה טרנספיניטית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
בנציון יעבץ (שיחה | תרומות) אין תקציר עריכה |
בנציון יעבץ (שיחה | תרומות) |
||
שורה 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>\phi(a_0)</math>, כי הטענה <math>\forall x\prec a_0,\phi(x)</math> מתקיימת באופן ריק, לכן <math>\phi(a_0)</math>. למרות זאת נהוג להוכיח <math>\phi(a_0)</math>, כי בדרך כלל ההוכחה שמתקיים <math>\forall x\prec a,\phi(x)\Rightarrow\phi(a)</math> נשענת על כך שאכן קיים <math>x\prec a</math>, ולכן היא תיכשל במקרה <math>a=a_0</math>.
נהוגות שתי טכניקות להוכחה באינדוקציה טרנספיניטית:
# הוכחה כללית, כלומר:
* <math>\phi(a_0)</math>
* <math>\forall x\prec a,\phi(x)\Rightarrow\phi(a)</math>
# הוכחה בהתאם למקרים, כלומר:
* <math>\phi(a_0)</math>
* מקרה א' - <math>a</math> [[תורת הקבוצות/יחסי סדר#יחס סדר טוב|איבר עוקב]], לכן יהי <math>S(x)=a</math>. מכיוון ש<math>x\prec S(x)=a</math>, הטענה <math>\forall y\prec a,\phi(y)</math> גוררת את הטענה <math>\phi(x)</math>, לכן לובשת ההוכחה צורה של <math>\phi(x)\Rightarrow\phi(S(x))</math>.
* מקרה ב' - <math>a</math> [[תורת הקבוצות/יחסי סדר#יחס סדר טוב|איבר גבולי]], לכן 'אין ברירה', וההוכחה נשארת בתבנית של <math>\forall x\prec a,\phi(x)\Rightarrow\phi(a)</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>.
| |||