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

אין תקציר עריכה
{{תורת הקבוצות}}
'''אינדוקציה טרנספיניטית''' היא שיטה מוצלחת להוכחת תכונות ולהגדרת פעולות ב[[תורת הקבוצות/יחסי סדר#יחס סדר טוב|קבוצות סדורות היטב]], המכלילה את עקרון האינדוקציה המתמטית על קבוצת המספרים הטבעיים. מהלך השיטהשיטת ההוכחה הוא כך: נניח ש <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>f</math> על קבוצה סדורה היטב <math>(A,\prec)</math>. אם מגדירים את <math>f(a_0)</math>, ולכל <math>a</math> מגדירים את <math>f(a)</math> עם התייחסות ל<math>f(x)</math> לכל <math>x\prec a</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>\phi(x)</math> על פי "<math>f(a)</math> מוגדר". ברצוננו להוכיח כי <math>f(a)</math> מוגדר לכל a, כלומר <math>\forall x\in A,\phi(x)</math>. נשים לב שמהדרך שבה הוגדר האופרטור נובע כי <math>\phi(a_0)\land\forall a\in A(\forall x\prec a,\phi(x)\Rightarrow\phi(a))</math>, לכן מעקרון האינדוקציה עבור הוכחות נובע כי <math>\forall x\in A,\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>.
419

עריכות