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

מתוך המכלול
קפיצה אל: ניווט, חיפוש

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

עקרון האינדוקציה הטרנספיניטית: תהי קבוצה סדורה היטב ו־ תכונה מסוימת. נתון שהאבר הראשון (האבר הכי קטן – נסמן אותו ) ב־ מקיים את התכונה המסוימת, וכן שכל מקיים את התכונה הבאה: אם כל האברים שקטנים ממנו מקיימים את התכונה , אז גם הוא עצמו מקיים את . אזי כל האברים ב־ מקיימים את .

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

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

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

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

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

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

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

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

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

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רישיון cc-by-sa 3.0