תורת הקבוצות/אינדוקציה טרנספיניטית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
אין תקציר עריכה
שורה 1:
'''אינדוקציה טרנספיניטית''' היא שיטה מוצלחת להוכחת תכונות ב[[תורת הקבוצות/יחסי סדר#יחס סדר טוב|קבוצות סדורות היטב]], המכלילה את עקרון האינדוקציה המתמטית על קבוצת המספרים הטבעיים. מהלך השיטה הוא כך: נניח ש <math>(A,\prec)</math> סדורה היטב, ותהי <math>\phi(x)</math> טענה לוגית התלויה במשתנים, כאשר משמעות הביטוי <math>\phi(x)</math> היא ש<math>\phi</math> טענה נכונה כאשר מציבים את x במקומות הנכונים. כדוגמה, הטענה <math>\phi(x)\equiv(\exist y,x+y=0)</math> נכונה לכל <math>x\in\R</math>. לעומת זאת, הטענה <math>\phi(x)\equiv(x^2=x)</math> נכונה רק עבור <math>x=0,1</math>. נחזור לעקרון האינדוקציה: בהינתן טענה כזו על קבוצה סדורה היטב, יהי <math>a_0</math> האיבר הראשון בקבוצה. מתקיימת הטענה הבאה: <math>(\phi(a_0)\land\forall x\in A(\forall y\prec x,\phi(y)\Rightarrow\phi(x)))\Rightarrow\forall x\in A,\phi(x)</math>. במילים אחרות: אם הוכחנו את הטענה עבור האיבר הראשון, והוכחנו שאם הטענה מתקיימת לכל האיברים שקטנים מאיבר כלשהו אז היא מתקיימת גם לאיבר הזה, אז הטענה מתקיימת לכל האיברים.
==הוכחה==
נוכיח את עקרון האינדוקציה הטרנספיניטית: נניח בשלילה שקיימים איברים שעבורם הטענה לא מתקיימת. נסמן את קבוצת כל האיברים האלו ב<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>.