קבוצת המספרים הטבעיים והאלכסון של קנטור.
ישנו עניין מיוחד במשפט קנטור כאשר הוא מופעל על קבוצת המספרים הטבעיים, formula_150. הסימון לקבוצת המספרים הטבעיים הוא formula_151. קנטור בחר לסמן את העוצמה של formula_151, שהיא העוצמה האינסופית הקטנה ביותר, בסימון אָלֶף אֶפֶס: formula_153. משפט קנטור מראה כי formula_154, או באופן שקול: formula_155.
במקרה הזה ניתן להציג את הוכחת משפט קנטור באופן מוחשי יותר, שממנו גם ברור השם "לכסון". הוכחת המשפט נפתחת בהנחה שקיימת פונקציה חד חד ערכית ועל formula_156. ניתן להציג פונקציה שכזו כסדרה אינסופית של איברי formula_157, כך: formula_158. כאשר מוסכם ש-formula_159 (למעשה זוהי ההגדרה הפורמלית של סדרה). כעת מגדירים את הקבוצה הבעייתית formula_160. לפי ההנחה קיים formula_161 כך ש-formula_162, אך זה לא ייתכן, כי כזכור, נובע מכך שמתקיים בו זמנית formula_163 ו-formula_164.
את הטיעון הנ"ל ניתן גם להציג כך: נציג כל formula_1 שהוא איבר של formula_157 כסדרה אינסופית של ספרות באופן הבא: הספרה ה-formula_141 בסדרה (החל מ-0) תהיה 1 אם formula_168, ואילו אם formula_169 היא תהיה 0. למשל הקבוצה formula_170 תוצג בצורה: formula_171.
את הסדרה formula_158 ניתן להציג כרשימה אינסופית של הייצוגים של כל אחד מאיברי הסדרה כסדרת ספרות. למשל את:
נציג בצורה:
כעת נשים לב כיצד נבנה formula_101. לפי ההגדרה, אם formula_176, אז הספרה ה-formula_141 בייצוג של formula_101 היא 1. ואילו אם formula_179 אז הספרה ה-formula_141 בייצוג של formula_101 היא אפס. במילים אחרות, הספרה ה-formula_141 של formula_101 היא בדיוק ההפך מהספרה ה-formula_141 של formula_185. במסגרת הדוגמה שלנו נוכל להמחיש זאת כך:
לא ייתכן כי קיים formula_187 כך ש-formula_162, כי formula_101 בהכרח נבדל מ-formula_187 בספרה ה-formula_161 בייצוג שלו.
טיעון האלכסון שהוצג זה עתה קרוי האלכסון של קנטור. הוא הוצג על ידי קנטור באותו מאמר בו הציג את משפט קנטור, וחשיבותו חורגת מהיותו מקרה פרטי של משפט קנטור. זאת משום שהסדרות של הספרות המייצגות כאן תת-קבוצות של formula_151, יכולות באותה מידה לייצג מספרים ממשיים בין 0 ל-1, שסדרת הספרות היא הכתיב הבינארי (אחרי הנקודה) שלהם (למשל formula_193 מייצג את 0.1 שהוא חצי בכתיב בינארי). כאשר מציגים את האלכסון של קנטור כהוכחה לאי-שקילות קבוצת המספרים הטבעיים formula_151 לקבוצת המספרים הממשיים formula_195 (עובדה שיכולה להפתיע, שכן formula_151 שקולה ל-formula_197, שהיא קבוצת המספרים הרציונליים) נהוג, לשם הנוחות, להשתמש בהצגה של המספרים בבסיס עשרוני (מבחינה היסטורית, קנטור הוכיח לראשונה את האי-שקילות של הטבעיים והממשיים 17 שנה קודם, בשיטה מוכרת פחות).
עוצמת המספרים הממשיים (השווה גם לעוצמת הממשיים שבין 0 ל-1 בלבד) קרויה עוצמת הרצף, ומקובל לסמנה formula_198. העובדה שהן את הממשיים והן את התת-קבוצות של formula_151 ניתן לבטא כרצפי ספרות אינסופיים, מעידה כי formula_195 ו-formula_157 שקולות. לכן formula_202.
קבוצת כל הקבוצות.
בתורת הקבוצות הנאיבית ניתן להגדיר את "קבוצת כל הקבוצות" formula_203 שכל קבוצה שהיא היא איבר שלה (כולל היא עצמה). באמצעות משפט קנטור ניתן להראות שהגדרה זו מובילה לפרדוקסים. כדי לפתור את הפרדוקסים פותחה תורת הקבוצות האקסיומטית שבמסגרתה בלתי אפשרי להגדיר קבוצות בעייתיות כגון formula_203.
שני הפרדוקסים הידועים ביותר הם:
מסקנות והשלכות.
שימושים.
מעבר לשימוש בתורת הקבוצות כתחום מחקר בפני עצמו, משפט קנטור משמש גם בתחומים אחרים של המתמטיקה. נביא דוגמה ממדעי המחשב ודוגמה מאנליזה מתמטית.
בעיות הכרעה.
תורת החישוביות היא תחום יסודי במדעי המחשב החוקר את היכולות והמגבלות של כל המחשבים באשר הם. בעיית הכרעה היא שאלה, שבהינתן קלט כלשהו, יש לה תשובה של "כן" או "לא" (למשל האם מספר טבעי נתון הוא מספר זוגי). שאלה מרכזית בתורת החישוביות היא האם כל בעיית הכרעה ניתנת לפתרון על ידי תוכנית מחשב כלשהי. בהסתמך על משפט קנטור ניתן להראות שהתשובה שלילית.
כל קלט (סופי) אפשרי הנתון בשפה כלשהי ניתן לקודד (לייצג) כמספר טבעי. קידוד שכזה נקרא מספור גדל ומחשבים מודרניים מיישמים אותו על ידי קידוד בינארי. בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה formula_1 הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהפך, לכל קבוצה של מספרים טבעיים formula_1 ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-formula_1. במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, formula_157.
מצד שני, כל תוכנית מחשב היא רצף סופי של סימנים של שפת תכנות. לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד (ואכן בפועל כל תוכנית מחשב בשפה מסוימת מתרגמת לקידוד בינארי שונה בשפת מכונה). מכאן שקבוצת כל תוכניות המחשב שקולה ל-formula_151.
משפט קנטור קובע ש-formula_154, ולכן יש הרבה יותר בעיות הכרעה מאשר תוכניות מחשב. מכאן שישנן בעיות הכרעה (ולמעשה, כמעט כל בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב. הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא בעיית העצירה. אלן טיורינג הוכיח זאת בשנת 1936 בשיטת האלכסון. דוגמאות רבות נוספות מגיעות ממשפט רייס.
טיעון דומה קובע שמרבית המספרים הממשיים אינם ניתנים לחישוב. זאת מכיוון שעוצמת החישובים האפשריים היא formula_227 (שכן כל חישוב יכול להעשות על ידי תוכנית מחשב), ואילו לפי האלכסון של קנטור, עוצמה זו קטנה מעוצמת הממשיים.
פונקציות רציפות.
פונקציה רציפה היא פונקציה ממשית formula_228 (פונקציה מקבוצת המספרים הממשיים לעצמה) שיש לה את התכונה שככל שמתקרבים לנקודה (מספר ממשי) כלשהי formula_229, ערכי הפונקציה הולכים וקרבים ל-formula_230, שהוא ערך הפונקציה בנקודה formula_229 (הגרף של פונקציות רציפות הוא קו רציף, ומכאן שמן). את קבוצת הפונקציות הרציפות מקובל לסמן formula_44, ואילו קבוצת הפונקציות הממשיות כולן היא formula_233. נראה כי formula_234, כלומר כמעט כל הפונקציות הממשיות אינן רציפות.
ראשית נמצא את formula_235. הערכים שפונקציה רציפה מקבלת בכל נקודה בישר הממשי נקבעים על ידי הערכים שהיא מקבלת בנקודות הרציונליות. זאת משום שהמספרים הרציונליים צפופים בישר, ולכן ניתן לקבל את הערך בכל נקודה אי-רציונלית כגבול של סדרת הערכים בנקודות רציונליות המתקרבת לנקודה (פורמלית: לכל formula_53 ממשי, בהינתן סדרת רציונליים formula_237, מתקיים formula_238). מכאן שיש פונקציה חד-חד-ערכית מ-formula_44 לקבוצת הפונקציות מהרציונליים לממשיים formula_240, ולכן formula_241. קבוצת הרציונליים שקולה לקבוצת הטבעיים, ולכן בעזרת כללי אריתמטיקה של עוצמות (ומהזהות formula_242 הנובעת מפונקציית הזיווג של קנטור) נקבל:
מצד שני, לכל מספר ממשי formula_53 ניתן להתאים את הפונקציה הקבועה formula_245 שהיא רציפה. מכאן ש-formula_246. ממשפט קנטור-שרדר-ברנשטיין נקבל formula_247.
נעבור ל-formula_248. קבוצה זו כוללת בין השאר כל פונקציה מציינת של formula_195. קבענו כבר כי עוצמת קבוצת הפונקציות המציינות של formula_195 היא formula_251. לכן formula_252 (למעשה מתקיים formula_253
,| = 2^{\aleph_0}&lt;/math&gt;. דרך אחרת היא להבחין כי הגרף הקרטזי של כל פונקציה formula_254 הוא תת-קבוצה של המישור האוקלידי formula_255, ולכן formula_256.
לפי משפט קנטור formula_257, ולכן formula_234.
תוצאה זו תקפה, באותה מידה ומאותם שיקולים, לקבוצת הפונקציות שיש להן לכל היותר מספר בן מנייה של נקודות אי רציפות. שיקולי עוצמות הם גסים מידי מכדי להראות שרוב הפונקציות אינן רציפות באף נקודה. לשם כך דרושים כלים עדינים יותר מתחום הטופולוגיה.
מספרי ב'.
ממשפט קנטור מגיעה המוטיבציה להגדרת סדרה של עוצמות הקרויה מספרי ב'. איברי הסדרה הם:
כלומר זוהי סדרת העוצמות:
משפט קנטור מבטיח כי כל העוצמות הללו שונות.
בהגדרה רקורסיבית, מספרי ב' מוגדרים:
מספרי ב' מוגדרים גם לאינדקסים סודרים, ולא רק טבעיים. לשם כך יש להוסיף להגדרה הרקורסיבית את המקרה של סודר גבולי:
למשל formula_263 הוא העוצמה הקטנה ביותר שגדולה מכל העוצמות formula_264 לכל formula_141 טבעי.
בנוסף קנטור הגדיר את הסדרה (המוכללת) formula_266 כסדרת כל העוצמות (formula_266 הוא העוצמה ה-formula_268 בגודלה). קנטור שיער ש-formula_269 (כלומר שאין עוצמה בין עוצמת הטבעיים לעוצמת הממשיים). ובאופן כללי יותר ש-formula_270. השערות אלו ידועות כהשערת הרצף והשערת הרצף המוכללת בהתאמה.
חרף מאמציו הרבים, קנטור מעולם לא הצליח להוכיח או להפריך את ההשערה עד יום מותו. התקדמות ראשונה בנושא הושגה על ידי קורט גדל שהוכיח בשנת 1937 כי השערת הרצף אינה סותרת את האקסיומות המקובלות של תורת הקבוצות. גורלה של ההשערה הוכרע סופית בשנת 1963 כאשר פול כהן הוכיח כי גם שלילתה של השערת הרצף אינה סותרת את האקסיומות של תורת הקבוצות. מכאן שהשערת הרצף היא טענה עצמאית (והיא הדוגמה המפורסמת ביותר לטענה שכזו), שאין אפשרות להוכיחה או להפריכה.
שיטת האלכסון.
הוכחת משפט קנטור יחד עם טיעון האלכסון של קנטור שהוצג לצדה הולידו שיטה כללית להוכחת טענות המשמשת בתחומים רבים במתמטיקה. השיטה נקראת אלכסון, והיא משמשת בעיקר במדעי המחשב ובלוגיקה מתמטית.