האלכסון של קנטור

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

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

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

הוכחה
ממוזער|250px|האלכסון של קנטור – מניחים שיש רשימה של כל המספרים הממשיים בין 0 ל-1, ומראים שיש מספר ממשי שלא מופיע ברשימה. m מייצג ספרות שהן 0 ו-w מייצג ספרות שאינן 0.
ההוכחה כאן מתבססת על ההצגה העשרונית של המספרים הממשיים, אך היא עובדת עם כל בסיס ספירה שאינו בסיס אונרי. כל מספר ממשי ניתן להציג כסדרה אינסופית של ספרות (לעיתים כולן 0 החל ממקום מסוים). ניתן להוכיח שהקטע הפתוח (0,1), המכיל את כל המספרים בין 0 ל-1, שווה בעוצמתו לכל הישר הממשי (כלומר קיימת התאמה חד-חד-ערכית ועל בינו לבין כל המספרים הממשיים). בקטע זה, ההצגה של כל מספר מתחילה בספרה 0, אחריה נקודה עשרונית ואחריה סדרה אינסופית של ספרות. נשמיט את כל המספרים שמסתיימים בסדרה אינסופית של 9, שכן סדרות אלו מייצגות מספר ממשי שניתן לייצגו בדרך אחרת. כעת יש לנו התאמה חד-חד-ערכית ועל בין הסדרות האינסופיות של הספרות לבין המספרים הממשיים בקטע (0,1), שכן כל מספר ממשי בקטע מיוצג על ידי סדרת ספרות אחת בדיוק.

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

נבנה את המספר הזה כך:
נבחן את הרשימה. אם הספרה במקום ה-n בפיתוח העשרוני של המספר  היא 0, במספר שלנו הספרה ה-n תהיה 1. אחרת, היא תהיה 0.

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

דוגמה:
נניח שסדרת המספרים שלנו היא כזו:

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

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

ראו גם
מונחים בתורת הקבוצות
קישורים חיצוניים



הערות שוליים

קטגוריה:הוכחות
קטגוריה:אינסוף
אלכסון של קנטור