אינדוקציה טרנספיניטית
ויקיפדיה האנציקלופדיה encyclopedia
אינדוקציה טרנספיניטית או אינדוקציה על־סופית[1] היא שיטת הוכחה המאפשרת להוכיח שתכונה מסוימת מתקיימת לכל איברי קבוצה סדורה היטב. האינדוקציה הטרנספיניטית היא וריאציה על האינדוקציה המתמטית, שמתקיימת עבור קבוצת המספרים הטבעיים.
עקרון האינדוקציה הטרנספיניטית: תהא X קבוצה סדורה היטב ו-P תכונה מסוימת. נתון שכל x ששייך ל-X מקיים את התכונה הבאה: אם כל האיברים שקטנים ממנו מקיימים את התכונה P, אז גם הוא עצמו מקיים את התכונה P. אזי כל האיברים ב-X מקיימים את התכונה P.
אם נסמן ב-A את קבוצת האיברים ב-X המקיימים את P, ניתן לרשום זאת בכתיבה מתמטית:
אין צורך לדרוש במפורש עבור האיבר הראשון, שכן זה נובע מהתנאי: אין איברים שקטנים ממנו, לכן "כל האיברים שקטנים ממנו מקיימים את התכונה P" נכון באופן ריק, ועל כן הדרישה שהוא יקיים את P כלולה בדרישה הכללית.
הוכחה שהשיטה עובדת: נסמן את קבוצת האיברים ששייכים ל-X ומקיימים את התכונה ב-A. נניח בשלילה ש-, אזי, כיוון ש-X מכילה את A, קיים איבר אבל . עתה נסתכל על הקבוצה X\A (הסימן " \ " מסמן הפרש קבוצות). כיוון ש-X סדורה היטב, והקבוצה הזאת אינה ריקה, יש לה איבר ראשון, . כיוון ש- הוא האיבר הראשון עבורו התכונה אינה מתקיימת, לכל קודמיו (כל האיברים הקטנים ממנו) ההנחה כן מתקיימת. לכן, על פי הנחת האינדוקציה, התכונה נכונה גם עבור . סתירה.
גם המשפט ההפוך נכון: קבוצה סדורה שמקיימת את עקרון האינדוקציה הטרנספיניטית סדורה בסדר טוב.
פעמים רבות ההוכחה מתחלקת לשני חלקים: הוכחה לאיברים עוקבים (שמהווים איבר עוקב של איבר אחר) ואיברים גבוליים (שאינם מקיימים את התכונה הזאת).