אינדוקציה טרנספיניטית

אינדוקציה טרנספיניטית או אינדוקציה על־סופית^[1] היא שיטת הוכחה המאפשרת להוכיח שתכונה מסוימת מתקיימת לכל איברי קבוצה סדורה היטב. האינדוקציה הטרנספיניטית היא וריאציה על האינדוקציה המתמטית, שמתקיימת עבור קבוצת המספרים הטבעיים.

עקרון האינדוקציה הטרנספיניטית: תהא X קבוצה סדורה היטב ו-P תכונה מסוימת. נתון שכל x ששייך ל-X מקיים את התכונה הבאה: אם כל האיברים שקטנים ממנו מקיימים את התכונה P, אז גם הוא עצמו מקיים את התכונה P. אזי כל האיברים ב-X מקיימים את התכונה P.

אם נסמן ב-A את קבוצת האיברים ב-X המקיימים את P, ניתן לרשום זאת בכתיבה מתמטית:

${\displaystyle \forall x\in X~~(\forall y~~,y<x\Rrightarrow y\in A)\Rrightarrow x\in A}$

אין צורך לדרוש במפורש עבור האיבר הראשון, שכן זה נובע מהתנאי: אין איברים שקטנים ממנו, לכן "כל האיברים שקטנים ממנו מקיימים את התכונה P" נכון באופן ריק, ועל כן הדרישה שהוא יקיים את P כלולה בדרישה הכללית.

הוכחה שהשיטה עובדת: נסמן את קבוצת האיברים ששייכים ל-X ומקיימים את התכונה ב-A. נניח בשלילה ש-${\displaystyle A\not =X}$, אזי, כיוון ש-X מכילה את A, קיים איבר ${\displaystyle x_{0}\in X}$ אבל ${\displaystyle x_{0}\not \in A}$. עתה נסתכל על הקבוצה X\A (הסימן " \ " מסמן הפרש קבוצות). כיוון ש-X סדורה היטב, והקבוצה הזאת אינה ריקה, יש לה איבר ראשון, ${\displaystyle b_{0}}$. כיוון ש-${\displaystyle b_{0}}$ הוא האיבר הראשון עבורו התכונה אינה מתקיימת, לכל קודמיו (כל האיברים הקטנים ממנו) ההנחה כן מתקיימת. לכן, על פי הנחת האינדוקציה, התכונה נכונה גם עבור ${\displaystyle b_{0}}$. סתירה.

גם המשפט ההפוך נכון: קבוצה סדורה שמקיימת את עקרון האינדוקציה הטרנספיניטית סדורה בסדר טוב.

פעמים רבות ההוכחה מתחלקת לשני חלקים: הוכחה לאיברים עוקבים (שמהווים איבר עוקב של איבר אחר) ואיברים גבוליים (שאינם מקיימים את התכונה הזאת).

דוגמה להוכחה באינדוקציה טרנספיניטית

נוכיח שהאיזומורפיזם היחיד שקיים מקבוצה סדורה היטב לעצמה הוא איזומורפיזם הזהות:

נסתכל על התכונה "בכל איזומורפיזם, האיבר הזה מועתק לעצמו". נבחר איבר כלשהו a ונניח שכל האיברים הקטנים ממנו בעלי התכונה הזאת. לאיזה איבר יכול להיות מועתק a? לא לאיבר שקטן ממנו, שהרי כל האיברים שקטנים ממנו חייבים להיות מועתקים לעצמם, ולכן זו לא תהיה העתקה חד-חד ערכית. גם לא לאיבר שגדול ממנו, כי איזומורפיזם הוא על ולכן a יהיה חייב להיות תמונה של איבר מסוים, אבל כל האיברים שקטנים מ-a מועתקים לעצמם, a מועתק לאיבר אחר, ואם a יהיה תמונה של איבר שגדול ממנו, אז ההעתקה לא תהיה שומרת סדר. כלומר קיבלנו ש-a חייב להיות מועתק לעצמו, כלומר גם הוא מקיים את התכונה.

קיבלנו שאם כל האיברים שקטנים מאיבר מסוים מקיימים את התכונה, גם הוא מקיים אותה. לכן על פי אינדוקציה טרנספיניטית כל האיברים בהכרח מועתקים לעצמם, והטענה הוכחה. (שימו לב שזה לא נכון לקבוצה שאינה סדורה בסדר טוב: למשל, f (x) = x-1 הוא איזומורפיזם מהממשיים לעצמם שאינו זהות.)

קישורים חיצוניים

• גדי אלכסנדרוביץ', תורת הקבוצות - מחלקות, אקסיומת ההחלפה ואינדוקציה ורקורסיה על-סופיות, באתר "לא מדויק", 18 בינואר 2023
• מארק שוורצמן, To infinity and beyond, באתר "מהומה רבה על לא דבר" (בעברית)
• מארק שוורצמן, עוד כמה מילים על סודרים ואינדוקציה טרנספיניטית, באתר "מהומה רבה על לא דבר"
• אינדוקציה טרנספיניטית, באתר MathWorld (באנגלית)

הערות שוליים

1. אִינְדּוּקְצִיָּה עַל־סוֹפִית במילון מתמטיקה (תשמ"ה, 1985), באתר האקדמיה ללשון העברית

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.