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

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

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

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

או בכתיבה מתמטית:  \forall x \in X ~~ (\forall y ~~  , y < x \Rrightarrow y \in A) \Rrightarrow  x \in A

הוכחה שהשיטה עובדת: נסמן את קבוצת האיברים ששייכים ל-X ומקיימים את התכונה ב-A. נניח בשלילה ש-A≠X, אזי, כיוון ש-X מכילה את A, קיים איבר x0∈X אבל x0∉A. עתה נסתכל על הקבוצה X\A (\ מסמן הפרש). כיוון ש-X סדורה היטב, והקבוצה הזאת אינה ריקה, יש לה איבר ראשון, b0. כיוון שb0 הראשון עבורו התכונה אינה מתקיימת, לכל קודמיו ההנחה כן מתקיימת. לכן, על פי הנחת האינדוקציה, התכונה נכונה גם לb0. סתירה.

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

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

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

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

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

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