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

'''אינדוקציה טרנספיניטית''' היא שיטה מוצלחת להוכחת תכונות ב[[תורת הקבוצות/יחסי סדר#יחס סדר טוב|קבוצות סדורות היטב]], המכלילה את עקרון האינדוקציה המתמטית על קבוצת המספרים הטבעיים. מהלך השיטה הוא כך: נניח ש <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>(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>.}}