משפט קנטור

גאורג קנטור

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

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

מושגים

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

פונקציות

דוגמה לפונקציה חד-חד-ערכית ועל מקבוצה $X$ לקבוצה $Y$. קיומה של הפונקציה מעיד על כך שבשתי הקבוצות אותו מספר של איברים.

פונקציה מקבוצה $A$ לקבוצה $B$ מתאימה לכל איבר ב-$A$ איבר יחיד ב-$B$. ייתכן שלכמה איברים ב-$A$ מותאם אותו איבר ב-$B$, וייתכן שיש איברים של $B$ שאף איבר של $A$ אינו מותאם להם.

על פונקציה מ-$A$ ל-$B$ נאמר שהיא חד-חד-ערכית, אם לכל שני איברים שונים ב-$A$ מותאמים איברים שונים ב-$B$. נאמר שהפונקציה היא על $B$ אם לכל איבר ב-$B$ יש איבר ב-$A$ שהותאם לו. פונקציה ששתי התכונות מתקיימות בה יחדיו נקראת חד-חד-ערכית ועל. פונקציה חד-חד-ערכית ועל מתאימה את שתי הקבוצות זו לזו, כך שלכל איבר באחת מן הקבוצות יש בן זוג יחיד בקבוצה השנייה.

השוואת גודלן של קבוצות

קיומה של פונקציה חד-חד-ערכית ועל מקבוצה סופית $A$ לקבוצה $B$ מראה שלשתי הקבוצות יש אותו מספר איברים, משום שלכל איבר מכל אחת מן הקבוצות יש בן זוג יחיד שהותאם לו מהקבוצה השנייה. אפשר לספור את איברי שתי הקבוצות יחד. קנטור הבין שניתן להשתמש ברעיון הזה כדי להשוות גם בקבוצות אינסופיות בגודלן. נניח כי $A,B$ הן קבוצות כלשהן (אולי אינסופיות). אם קיימת פונקציה חד-חד-ערכית ועל מ-$A$ ל-$B$ נאמר שהקבוצות האלה שקולות, ונסמן $A\sim B$. השקילות בין הקבוצות מבטאת, על-פי קנטור, את הרעיון שיש להן אותו מספר של איברים. אם שתי קבוצות $A,B$ הן שקולות, מסמנים $|A|=|B|$. הסימן $|A|$ נחשב כאילו הוא מסמן את מספר האיברים בקבוצה $A$, שיכול להיות אינסופי. זוהי העוצמה של $A$.

מן המקרה של קבוצות סופיות ידוע לנו שהעוצמה של קבוצה אחת יכולה להיות גדולה מן העוצמה של קבוצה אחרת. למשל, בקבוצה עם ארבעה איברים יש יותר איברים מאשר בקבוצה עם איבר אחד. רעיון זה מתבטא בעובדה שקיימת פונקציה חד-חד-ערכית שאינה על מהקבוצה השנייה לראשונה. באופן כללי לכל שתי קבוצות $A,B$ נאמר כי $|A|\leq |B|$, אם קיימת פונקציה חד-חד-ערכית (שאינה בהכרח על) מ-$A$ ל-$B$. כלומר $B$ גדולה (או שווה) מ-$A$ אם אפשר להתאים לכל איבר ב-$A$ בן זוג יחיד ב-$B$, גם אם נשארים איברים של $B$ שלא הותאם להם בן זוג. אם מתקיים $|A|\leq |B|$ וגם $|A|\neq |B|$, אז נאמר כי $|A|<|B|$. משפט קנטור-שרדר-ברנשטיין קובע שאם $|A|\leq |B|$ וגם $|A|\geq |B|$, אז $|A|=|B|$ (המשפט הזה אינו מובן מאליו: הוא טוען שאם יש פונקציה חד-חד-ערכית מ-$A$ ל-$B$, ופונקציה חד-חד-ערכית מ-$B$ ל-$A$, אז יש גם פונקציה שהיא בו-זמנית חד-חד-ערכית ועל).

סימונים

קבוצה $C$ תקרא תת-קבוצה של $A$, אם כל איבר של $C$ הוא גם איבר של $A$. קבוצת כל התת-קבוצות של $A$ נקראת קבוצת החזקה של $A$, אשר לה ניתן הסימון ${\mathcal {P}}(A)$ (אם כי לפעמים משתמשים גם בסימון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^A} ).

קבוצה מסמנים על פי רוב באות לטינית גדולה. אם רוצים לפרט את איברי הקבוצה כותבים אותם בתוך סוגריים מסולסלים, כשהם מופרדים בפסיקים. למשל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{a,b,c\}} היא קבוצה שאיבריה הם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a,b,c} . דרך נוספת לציון קבוצה היא ציון תנאי שאיברי הקבוצה מקיימים. למשל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x:1<x<3\}} היא קבוצת המספרים שבין 1 ל-3, ואילו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{p^2:p\text{ is prime}\}} היא קבוצת המספרים שהם ריבועים של המספרים הראשוניים.

• אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} הוא איבר של הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} מסמנים זאת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in A} , ואם הוא אינו איבר של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} מסמנים זאת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\notin A} .
• פונקציה מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} מסמנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:A\to B} . את האיבר ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} שהפונקציה מתאימה לאיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} מסמנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(a)} . למשל הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} שמתאימה לכל מספר טבעי את העוקב שלו מוגדרת לפי החוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n)=n+1} , אבל ישנן פונקציות מסובכות, שלא ניתן לכתוב להן חוקים מסוג זה.
• אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , כלומר כל איבר של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} הוא גם איבר של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , מסמנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\sube A} .
• הקבוצה הריקה היא קבוצה שאין בה אף איבר והיא מסומנת כך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \empty=\{\ \}} . לכל קבוצה שהיא A מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \empty\sube A} .
• לפי הסימונים שהצגנו עתה, ניתן להגדיר את קבוצת החזקה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(A)=\{C:C\sube A\}} .

נוסח המשפט

משפט קנטור. לכל קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} (סופית או אינסופית), מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|<|\mathcal{P}(A)|} .

לבו של המשפט בטענה שהקבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(A)} אינן שקולות זו לזו, אפילו כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} אינסופית. הוא מראה שלא כל הקבוצות האינסופיות הן שוות עוצמה, ושלמעשה לכל קבוצה אינסופית ניתן למצוא קבוצה עם עוצמה גדולה יותר.

הוכחת המשפט

הוספה נאיבית של איברים לקבוצה אינסופית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} אינה משנה את העוצמה גם אם ניקח שתי קבוצות אינסופיות מעוצמה זהה, ונאחד אותן, עוצמת האיחוד תהיה שווה לעוצמה של כל אחת מהקבוצות בנפרד. אפילו עוצמתה של קבוצת המספרים הרציונלים (הכוללת את כל השברים) זהה לעוצמת קבוצת המספרים הטבעיים לבדם (להוכחה ראו כאן וכאן). עם זאת, טוען המשפט, קבוצת החזקה היא בעלת עוצמה גדולה יותר.

תהי $A$ קבוצה כלשהי. הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(a)=\{a\}} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in A} היא פונקציה חד-חד-ערכית מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(A)} , ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|\le |\mathcal{P}(A)|} .

נותר אם כך להוכיח כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|\ne|\mathcal{P}(A)|} . נניח בשלילה כלומר כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|=|\mathcal{P}(A)|} , ונראה כי הדבר מוביל לסתירה.

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|=|\mathcal{P}(A)|} , הרי שקיימת פונקציה חד-חד-ערכית ועל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:A\to\mathcal{P}(A) } (למעשה אין צורך בהנחה שהפונקציה חד-חד-ערכית; ההוכחה מראה שאפילו פונקציה על בלבד אינה אפשרית). הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} מתאימה לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in A} תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , ומכסה באופן הזה את כל התת-קבוצות. לכן לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in A} יתכנו שתי אפשרויות: או שהוא איבר של התת-קבוצה המתאימה לו, או שלא.

נגדיר קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D=\bigl\{a\in A:a\notin f(a)\bigr\}} , המורכבת מכל אותם איברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} שאינם איברי התת-קבוצה המתאימה להם. מכאן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D\sube A} . לפי ההנחה קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\in A} עבורו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(d)=D} .

עתה נשאלת השאלה האם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\in f(d)=D} ? אם נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\in D} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} איבר בקבוצה שהותאמה לו, ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\notin D} . אם נניח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\notin D} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} אינו איבר בקבוצה שהותאמה לו, ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\in D} .

בשני המקרים הגענו לסתירה, ולכן ההנחה הראשית שלנו חייבת להיות שגויה. מכאן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|\ne|\mathcal P(A)|} ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|<|\mathcal P(A)|} .

הסבר אינטואיטיבי

הפילוסוף והחידונאי ריימונד סמוליאן, בספרו "מה שמו של ספר זה?", מציג גרסה אינטואיטיבית להוכחה. הגרסה המופיעה כאן מבוססת על גרסה זו. כל קבוצה אפשרית של תושבים ביקום (שגודלו עשוי להיות אינסופי) יוצרת לה מועדון (התושבים הם איברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , והמועדונים הם איברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(A)} ). נניח שכל מועדון נקרא על שם אחד התושבים (זוהי ההנחה שקיימת פונקציה על בין הקבוצות). נקים את המועדון שחבריו הם כל התושבים שאינם חברים במועדון הקרוי על שמם. מועדון זה, ככל מועדון אחר, חייב להיקרא על שם אחד התושבים – למשל גראוצ'ו. אם גראוצ'ו חבר במועדון, הרי שהוא חבר במועדון הנקרא על שמו, בסתירה להגדרת המועדון; אבל אם הוא לא חבר במועדון, הרי שהוא מקיים את תנאי הקבלה היחיד למועדון, ונעשה בו חבר באופן אוטומטי. סתירה זו מעידה כי ההנחה שאפשר לקרוא כל מועדון על שם תושב, מוטעית. האינסוף של המועדונים גדול יותר מן האינסוף של התושבים.

נוסח שקול

לפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \colon A \to \{0,1\}} (כלומר פונקציה שמתאימה לכל איבר ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} את המספר 0 או 1) קוראים פונקציה מציינת. מקובל לסמן את קבוצת כל הפונקציות מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} בסימון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B^A} . על כן קבוצת הפונקציות המציינות של קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1\}^A} .

נשים לב כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1\}^A \sim \mathcal{P}(A)} . זאת משום שלכל פונקציה מציינת ניתן להתאים את התת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} שהפונקציה המציינת מתאימה לאיבריה (ורק לאיבריה) את המספר 1, ולשאר האיברים היא מתאימה 0. לכן משפט קנטור קובע כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| < |\{0,1\}^A|} (למעשה זהו הנוסח של קנטור במקור).

מגדירים את פעולת החזקה בין עוצמות באופן הבא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |B|^{|A|} = |B^A|} . הגדרה זו מכלילה את ההגדרה הרגילה לחזקה בין מספרים טבעיים, ומתלכדת עימה כאשר היא מופעלת על טבעיים (ראו חזקה: קבוצות ועצמות). בהתאם להגדרה זו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\{0,1\}^A| = |\{0,1\}|^{|A|} = 2^{|A|}} .

על כן נוכל לנסח את משפט קנטור גם באופן הבא: לכל עוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|} מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|<2^{|A|}} .

מקרים פרטיים

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=\{1,2,3\}} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|=3} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(A) = \{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}} הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathcal{P}(A)| = 8 = 2^3}

קבוצות סופיות

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} היא קבוצה סופית בעלת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} איברים (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|=n} ), אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathcal{P}(A)| = 2^n} . תוצאה זו מתקבלת משיקול קומבינטורי פשוט: בהינתן תת-קבוצה שרירותית של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , לגבי כל איבר ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} יש שתי אפשרויות: או שהוא איבר של התת-קבוצה או שהוא לא. מעקרון הכפל מקבלים שיש: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\cdot 2\cdots 2 = 2^n} אפשרויות לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} האיברים יחדיו, ולכן זהו מספר התת-קבוצות (כאמור בפרק הקודם, תוצאה זו נכונה אפילו לעוצמות אינסופיות).

לכן משפט קנטור לקבוצות סופיות קובע את האי-שוויון הידוע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n<2^n} , לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} טבעי. אי-שוויון זה ניתן להוכחה בפשטות באינדוקציה, ולכן עיקר העניין במשפט קנטור הוא בהשלכותיו לגבי קבוצות אינסופיות.

קבוצת המספרים הטבעיים והאלכסון של קנטור

ערך מורחב – האלכסון של קנטור

ישנו עניין מיוחד במשפט קנטור כאשר הוא מופעל על קבוצת המספרים הטבעיים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1,2,3,\ldots\}} . הסימון לקבוצת המספרים הטבעיים הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} . קנטור בחר לסמן את העוצמה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} , שהיא העוצמה האינסופית הקטנה ביותר, בסימון אָלֶף אֶפֶס: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}| = \aleph_0} . משפט קנטור מראה כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}|<|\mathcal{P}(\mathbb{N})|} , או באופן שקול: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0<2^{\aleph_0}} .

במקרה הזה ניתן להציג את הוכחת משפט קנטור באופן מוחשי יותר, שממנו גם ברור השם "לכסון". הוכחת המשפט נפתחת בהנחה שקיימת פונקציה חד חד ערכית ועל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \colon \mathbb{N} \to \mathcal{P}(\mathbb{N})} . ניתן להציג פונקציה שכזו כסדרה אינסופית של איברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(\mathbb{N})} , כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0, A_1, A_2,\ldots} . כאשר מוסכם ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = A_n} (למעשה זוהי ההגדרה הפורמלית של סדרה). כעת מגדירים את הקבוצה הבעייתית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = \{n \in \mathbb{N} \mid n \not\in A_n \}} . לפי ההנחה קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_m = D} , אך זה לא ייתכן, כי כזכור, נובע מכך שמתקיים בו זמנית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \in A_m} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \not\in A_m} .

את הטיעון הנ"ל ניתן גם להציג כך: נציג כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} שהוא איבר של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(\mathbb{N})} כסדרה אינסופית של ספרות באופן הבא: הספרה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} בסדרה (החל מ-0) תהיה 1 אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in A} , ואילו אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \not\in A} היא תהיה 0. למשל הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1,2,4,8,\ldots\}} תוצג בצורה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\ 1\ 1\ 0\ 1\ 0\ 0\ 0\ 1\ldots} .

את הסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0, A_1, A_2,\ldots} ניתן להציג כרשימה אינסופית של הייצוגים של כל אחד מאיברי הסדרה כסדרת ספרות. למשל את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0 = \{1\}, A_1 = \{1,3,\ldots\}, A_2 = \{0,1,2,3,4,\ldots\}, A_3 = \{2,4\}, A_4 = \{0,4\},\ldots}

נציג בצורה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix} A_n & \text{Representation} \\ \hline A_0 & 0\ 1\ 0\ 0\ 0\ldots \\ A_1 & 0\ 1\ 0\ 1\ 0\ldots \\ A_2 & 1\ 1\ 1\ 1\ 1\ldots \\ A_3 & 0\ 0\ 1\ 0\ 1\ldots \\ A_4 & 1\ 0\ 0\ 0\ 1\ldots \\ \vdots & \vdots \end{matrix}}

כעת נשים לב כיצד נבנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} . לפי ההגדרה, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \not\in A_n} , אז הספרה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} בייצוג של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} היא 1. ואילו אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in A_n} אז הספרה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} בייצוג של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} היא אפס. במילים אחרות, הספרה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} היא בדיוק ההפך מהספרה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_n} . במסגרת הדוגמה שלנו נוכל להמחיש זאת כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix} A_n & \text{Representation} \\ \hline A_0 & {\color{Red}0}\ 1\ 0\ 0\ 0\ldots \\ A_1 & 0\ {\color{Red}1}\ 0\ 1\ 0\ldots \\ A_2 & 1\ 1\ {\color{Red}1}\ 1\ 1\ldots \\ A_3 & 0\ 0\ 1\ {\color{Red}0}\ 1\ldots \\ A_4 & 1\ 0\ 0\ 0\ {\color{Red}1}\ldots \\ \vdots & \vdots \\ \hline D & {\color{blue}1\ 0\ 0\ 1\ 0\ldots} \\ \end{matrix}}

לא ייתכן כי קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_m} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_m = D} , כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} בהכרח נבדל מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_m} בספרה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} בייצוג שלו.

טיעון האלכסון שהוצג זה עתה קרוי האלכסון של קנטור. הוא הוצג על ידי קנטור באותו מאמר בו הציג את משפט קנטור, וחשיבותו חורגת מהיותו מקרה פרטי של משפט קנטור. זאת משום שהסדרות של הספרות המייצגות כאן תת-קבוצות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} , יכולות באותה מידה לייצג מספרים ממשיים בין 0 ל-1, שסדרת הספרות היא הכתיב הבינארי (אחרי הנקודה) שלהם (למשל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10000\ldots} מייצג את 0.1 שהוא חצי בכתיב בינארי). כאשר מציגים את האלכסון של קנטור כהוכחה לאי-שקילות קבוצת המספרים הטבעיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} לקבוצת המספרים הממשיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} (עובדה שיכולה להפתיע, שכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} שקולה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Q}} , שהיא קבוצת המספרים הרציונליים) נהוג, לשם הנוחות, להשתמש בהצגה של המספרים בבסיס עשרוני (מבחינה היסטורית, קנטור הוכיח לראשונה את האי-שקילות של הטבעיים והממשיים 17 שנה קודם, בשיטה מוכרת פחות).

עוצמת המספרים הממשיים (השווה גם לעוצמת הממשיים שבין 0 ל-1 בלבד) קרויה עוצמת הרצף, ומקובל לסמנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph} . העובדה שהן את הממשיים והן את התת-קבוצות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} ניתן לבטא כרצפי ספרות אינסופיים, מעידה כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(\mathbb{N})} שקולות. לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0} = \aleph} .

קבוצת כל הקבוצות

בתורת הקבוצות הנאיבית ניתן להגדיר את "קבוצת כל הקבוצות" הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} שכל קבוצה שהיא היא איבר שלה (כולל היא עצמה). באמצעות משפט קנטור ניתן להראות שהגדרה זו מובילה לפרדוקסים. כדי לפתור את הפרדוקסים פותחה תורת הקבוצות האקסיומטית שבמסגרתה בלתי אפשרי להגדיר קבוצות בעייתיות כגון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} .

שני הפרדוקסים הידועים ביותר הם:

• הפרדוקס של קנטור, שהתגלה על ידי קנטור עצמו מעט לאחר שפרסם את משפט קנטור. הפרדוקס נוצר מניסיון להפעיל את משפט קנטור על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} .
  הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(U)} היא קבוצה שכל איבריה הם קבוצות. בפרט היא תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} . לכן הפונקציה החד-חד-ערכית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: \mathcal{P}(U) \to U} המוגדרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(A)=A} קיימת ומוגדרת היטב. מכאן ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |P(U)| \le |U|} . מצד שני, לפי משפט קנטור מתקיים להפך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |P(U)|>|U|} .
• הפרדוקס של ראסל, שהוצג על ידי המתמטיקאי ברטראנד ראסל בשנת 1901 ושואב השראה מהוכחת משפט קנטור. ואכן, ניתן לראות בפרדוקס של ראסל מקרה פרטי של הוכחת משפט קנטור לגבי הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} . כאמור, הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(A)=A} היא פונקציה חד-חד-ערכית מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(U)} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} . אולם מעקב אחרי שלבי הוכחת קנטור יוביל אותנו למסקנה שפונקציה שכזו לא תיתכן. נגדיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = \{a \in U \mid a \not\in f(a)\} = \{a \mid a\not\in a\}} . כעת נקבל שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D \in D} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D \not\in D} , ואילו אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D \not\in D} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D \in D} .

מסקנות והשלכות

שימושים

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

בעיות הכרעה

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

כל קלט (סופי) אפשרי הנתון בשפה כלשהי ניתן לקודד (לייצג) כמספר טבעי. קידוד שכזה נקרא מספור גדל ומחשבים מודרניים מיישמים אותו על ידי קידוד בינארי. בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהפך, לכל קבוצה של מספרים טבעיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(\mathbb{N})} .

מצד שני, כל תוכנית מחשב היא רצף סופי של סימנים של שפת תכנות. לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד (ואכן בפועל כל תוכנית מחשב בשפה מסוימת מתרגמת לקידוד בינארי שונה בשפת מכונה). מכאן שקבוצת כל תוכניות המחשב שקולה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} .

משפט קנטור קובע ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}|<|\mathcal{P}(\mathbb{N})|} , ולכן יש הרבה יותר בעיות הכרעה מאשר תוכניות מחשב. מכאן שישנן בעיות הכרעה (ולמעשה, כמעט כל בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב. הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא בעיית העצירה. אלן טיורינג הוכיח זאת בשנת 1936 בשיטת האלכסון. דוגמאות רבות נוספות מגיעות ממשפט רייס.

טיעון דומה קובע שמרבית המספרים הממשיים אינם ניתנים לחישוב. זאת מכיוון שעוצמת החישובים האפשריים היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}|} (שכן כל חישוב יכול להעשות על ידי תוכנית מחשב), ואילו לפי האלכסון של קנטור, עוצמה זו קטנה מעוצמת הממשיים.

פונקציות רציפות

פונקציה רציפה היא פונקציה ממשית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \colon \mathbb{R} \to \mathbb{R}} (פונקציה מקבוצת המספרים הממשיים לעצמה) שיש לה את התכונה שככל שמתקרבים לנקודה (מספר ממשי) כלשהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , ערכי הפונקציה הולכים וקרבים ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} , שהוא ערך הפונקציה בנקודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} (הגרף של פונקציות רציפות הוא קו רציף, ומכאן שמן). את קבוצת הפונקציות הרציפות מקובל לסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} , ואילו קבוצת הפונקציות הממשיות כולן היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^{\mathbb{R}}} . נראה כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C|<|\mathbb{R}^{\mathbb{R}}|} , כלומר כמעט כל הפונקציות הממשיות אינן רציפות.

ראשית נמצא את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C|} . הערכים שפונקציה רציפה מקבלת בכל נקודה בישר הממשי נקבעים על ידי הערכים שהיא מקבלת בנקודות הרציונליות. זאת משום שהמספרים הרציונליים צפופים בישר, ולכן ניתן לקבל את הערך בכל נקודה אי-רציונלית כגבול של סדרת הערכים בנקודות רציונליות המתקרבת לנקודה (פורמלית: לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ממשי, בהינתן סדרת רציונליים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n \to a} , מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(a) = \lim_{n \to \infty} f(x_n)} ). מכאן שיש פונקציה חד-חד-ערכית מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} לקבוצת הפונקציות מהרציונליים לממשיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^{\mathbb{Q}}} , ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C| \le |\mathbb{R}^{\mathbb{Q}}|} . קבוצת הרציונליים שקולה לקבוצת הטבעיים, ולכן בעזרת כללי אריתמטיקה של עוצמות (ומהזהות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0\cdot\aleph_0=\aleph_0} הנובעת מפונקציית הזיווג של קנטור) נקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C| \le |\mathbb{R}^{\mathbb{Q}}| = \aleph^{\aleph_0} = \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0\cdot\aleph_0} = 2^{\aleph_0} = \aleph}

מצד שני, לכל מספר ממשי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ניתן להתאים את הפונקציה הקבועה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = a} שהיא רציפה. מכאן ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C| \ge |\mathbb{R}| = \aleph} . ממשפט קנטור-שרדר-ברנשטיין נקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C| = \aleph} .

נעבור ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^{\mathbb{R}}} . קבוצה זו כוללת בין השאר כל פונקציה מציינת של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} . קבענו כבר כי עוצמת קבוצת הפונקציות המציינות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{|\mathbb{R}|} = 2^{\aleph}} . לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{R}^{\mathbb{R}}|\ge 2^{\aleph}} (למעשה מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{R}^{\mathbb{R}}| = 2^{\aleph}} ,,).

לפי משפט קנטור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph<2^{\aleph}} , ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |C|<|\mathbb{R}^{\mathbb{R}}|} .

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

מספרי ב'

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \beth_0 = \aleph_0, \ \beth_1 = 2^{\aleph_0} = \aleph, \ \beth_2 = 2^{2^{\aleph_0}} \ \beth_3 = 2^{2^{2^{\aleph_0}}}\ \ldots}

כלומר זוהי סדרת העוצמות:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}|,\ |P(\mathbb{N})|,\ |P(P(\mathbb{N}))|,\ |P(P(P(\mathbb{N})))|,\ \ldots}

משפט קנטור מבטיח כי כל העוצמות הללו שונות.

בהגדרה רקורסיבית, מספרי ב' מוגדרים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_0 = \aleph_0\ ;\ \beth_{\alpha+1} = 2^{\beth_{\alpha}} }

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_{\lambda}=\sup\{ \beth_{\alpha}\mid \alpha<\lambda \}}

למשל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_{\omega}} הוא העוצמה הקטנה ביותר שגדולה מכל העוצמות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_n} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} טבעי.

בנוסף קנטור הגדיר את הסדרה (המוכללת) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{\alpha}} כסדרת כל העוצמות (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{\alpha}} הוא העוצמה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} בגודלה). קנטור שיער ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_1 = \aleph_1} (כלומר שאין עוצמה בין עוצמת הטבעיים לעוצמת הממשיים). ובאופן כללי יותר ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beth_\alpha = \aleph_\alpha} . השערות אלו ידועות כהשערת הרצף והשערת הרצף המוכללת בהתאמה.

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

שיטת האלכסון

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

הרעיון הכללי בשיטת האלכסון הוא לבנות אובייקט מתמטי קביל המתייחס לעצמו באופן עקיף. אופי ההתייחסות תלוי בטענה שאותה רוצים להוכיח. הוכחה כללית בשיטה זו בנויה כך: בהינתן אוסף של איברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Lambda} ואוסף של אובייקטים מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} , לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \in \Lambda} . נניח שכל אובייקט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} פועל בצורה כלשהי על איברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Lambda} . נסמן את הפעולה של $\phi _{\alpha }$ על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta \in \Lambda} כ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha(\beta)} (ניתן לחשוב על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} כפונקציה של איברי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Lambda} ). מגדירים אובייקט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D} שנקרא ה"אלכסון", כך שתוצאת הפעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D(\beta)} נקבעת על פי תוצאת הפעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_{\beta}(\beta)} . אם קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma \in \Lambda} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\gamma = \phi_D} , אז הכרח שהוא מתייחס לעצמו, שכן לפי ההגדרה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D(\gamma)} נקבע על פי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\gamma(\gamma)} , כלומר על פי עצמו.

השם "אלכסון" מקורו בהמחשה הוויזואלית של שיטת ההוכחה, כפי שהיא מודגמת בטיעון האלכסון של קנטור. הרעיון הוא לדמיין טבלה (אינסופית לרוב) שכל שורה בה מייצגת איבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} וכל עמודה בה מייצגת אובייקט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} (באותו הסדר). בהצטלבות בין השורה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} לעמודה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} מופיע הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha(\beta)} . אובייקט ה"אלכסון" הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D} נבנה על סמך התאים בטבלה שהם מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_{\beta}(\beta)} , שמסודרים בקו אלכסוני לאורך ורוחב הטבלה.

להלן דוגמאות חשובות להוכחה בשיטת האלכסון:

• הוכחת משפט קנטור היא מקרה כללי של הוכחה בשיטת האלכסון. נדגים זאת עם נוסח ההוכחה לפונקציות מציינות, שנוח יותר לשימוש במקרה הזה. האוסף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Lambda} הוא הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . מניחים בשלילה כי לכל פונקציה מציינת של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ניתן להתאים איבר של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . האובייקט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} הוא הפונקציה המציינת שהותאמה לאיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \in A} . הפעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha(\beta)} היא פשוט הפעולה הרגילה של הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha} על האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} . אובייקט האלכסון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D} הוא פונקציה מציינת כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D(\beta)} מוגדר כהיפך מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_{\beta}(\beta)} (0 אם הוא 1, ו-1 אם הוא 0). לפי ההנחה קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma \in A} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\gamma = \phi_D} , ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\gamma(\gamma) \ne \phi_D(\gamma) = \phi_\gamma(\gamma)} . זוהי סתירה, ולכן ההנחה שגויה ומשפט קנטור נכון.
• כאמור, אלן טיורינג הוכיח בלכסון כי בעיית העצירה אינה ניתנת להכרעה. כלומר לא קיימת תוכנית מחשב שבהינתן כל תוכנית מחשב וקלט אפשרי, תכריע האם התוכנית הנתונה תסיים את פועלה על הקלט הנתון, או שתכנס ללולאה אינסופית. במקרה הזה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Lambda} היא קבוצת כל תוכניות המחשב (בשפה כלשהי). נניח שקיימת תוכנית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} שבהינתן תוכנית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} וקלט $\beta$ מכריעה האם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} עוצרת על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} . הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\alpha(\beta)} יהיה "כן" אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} עוצרת על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} , ו"לא" אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} נכנסת ללולאה אינסופית בהינתן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} . נגדיר תוכנית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} שבהינתן קלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta} , מריצה את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} כדי לגלות מהו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\beta(\beta)} (תוכנית יכולה לקבל כקלט את עצמה, שכן כל תוכנית היא בסך הכל רצף של סימנים בשפה) - אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\beta(\beta)} הוא "לא" אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} משיבה "כן", ואם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\beta(\beta)} הוא "לא", אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} לא עוצרת. מכאן ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D(\beta)} הוא "כן" אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\beta(\beta)} הוא "לא", והוא "לא" אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_\beta(\beta)} הוא "כן". כמסקנה נקבל ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D(D)} הוא ההפך מעצמו. סתירה זו מראה כי ההנחה שלנו כי קיימת תוכנית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} שמסוגלת להכריע את בעיית העצירה היא שגויה.
• משפט האי-שלמות הראשון, שהוכח על ידי קורט גדל בשנת 1931, הוא משפט מרכזי בלוגיקה מתמטית. המשפט קובע שבכל תורה העונה לתנאים מסוימים, קיימות טענות עצמאיות שלא ניתנות להוכחה או להפרכה. השלב העיקרי בהוכחת גדל מתבצע בלכסון. במסגרת ההוכחה מתעניינים בכל התכונות שניתן לנסח בתורה הנוגעות למספרים טבעיים. את התכונה שמספרה הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} (מספור גדל מראה כיצד להצמיד לכל תכונה מספר משלה) נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_n} . הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_n(k)} הוא הטענה שהמספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} מקיים את התכונה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} (הטענה עשויה להיות נכונה או שגויה). גדל הראה כיצד ניתן לבנות בשפה תכונה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_m} (זוהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_D} ) שמתקיימת רק לאותם מספרים טבעיים שלגביהם לא קיימת הוכחה לטענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_n(n)} . כלומר הטענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_m(n)} נכונה אם ורק אם אין הוכחה לטענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_n(n)} . כעת נפרש את המשמעות של הטענה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_m(m)} . לפי הבניה, זוהי טענה שנכונה אם ורק אם אין הוכחה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_m(m)} . כלומר זוהי טענה שאומרת "אני נכונה אם ורק אם אי אפשר להוכיח אותי".

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

הפרדוקסים שנתגלו בגישתו של קנטור לתורת הקבוצות – גישה שלימים נקראה תורת הקבוצות הנאיבית – הביאו לפיתוחה של תורת הקבוצות האקסיומטית. התורה האקסיומטית מסתמכת על מערכת של אקסיומות בסיסיות ומוגדרות היטב, כדי למנוע את הופעתם של פרדוקסים. המערכת המקובלת היא מערכת האקסיומות של צרמלו-פרנקל (ZF). במערכת זו משפט קנטור תקף לגבי כל קבוצה. אקסיומת קבוצת החזקה מבטיחה את קיומה של קבוצת החזקה ואקסיומת ההחלפה מבטיחה את קיומה של הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} הנדרשת בהוכחה. אקסיומת האינסוף קובעת את קיומה של קבוצה אינסופית, ולכן המסקנה ממשפט קנטור כי יש אינסוף עוצמות אינסופיות שונות, אף היא תקפה. הפרדוקסים אינם מופיעים ב-ZF, כי במערכת זו אוסף כל הקבוצות ואוספים דומים לו אינם קבוצות.

בגישות חלופיות לתורת הקבוצות משפט קנטור עשוי שלא להיות תקף. בתורות טיפוסים שונות להוכחת משפט קנטור אין משמעות, כי לא ניתן להשוות בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(A)} שלהן טיפוסים שונים. כדי להתגבר על כך מגדירים קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}_1(A) = \{\{a\}\mid a\in A\}} שיש לה טיפוס זהה ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}(A)} , ולגביה אכן מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathcal{P}_1(A)| < |\mathcal{P}(A)|} בהתאם למשפט קנטור. לאור העובדה שבתורת הטיפוסים קיימת קבוצת כל הקבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} , נשאלת השאלה כיצד בתורה זו נמנעים הפרדוקסים של קנטור ושל ראסל. התשובה היא שבתורת הטיפוסים הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \colon \mathcal{P}(U) \to U} המוגדרת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(A)=A} אינה קיימת. למעשה בתורה זו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathcal{P}_1(U)| < |\mathcal{P}(U)| < |U|} . בתורת הטיפוסים, כאשר מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathcal{P}_1(A)|=|A|} , הקבוצה נקראת "קבוצה קנטורית" ולגביה מתקיים משפט קנטור במובנו הרגיל.

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

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

הכללות

משפט קניג, שהוכח על ידי המתמטיקאי ההונגרי דיולה קניג (נודע גם כיוליוס קניג; 1849-1913) הוא הכללה מרחיקת לכת של משפט קנטור. המשפט קובע שלכל קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , אם לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in A} נתונות זוג עוצמות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa_i} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_i} , כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa_i < \mu_i} , אז:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i\in A}\kappa_i<\prod_{i\in A}\mu_i}

אגף שמאל הוא סכום העוצמות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa_i} , ואילו אגף ימין הוא מכפלת העוצמות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_i} . האי-שוויון טריוויאלי כאשר העוצמות והקבוצה סופיים, אבל כלל אינו ברור מאליו למקרים אינסופיים. אם למשל תוחלף המכפלה באגף ימין בסכום, עשוי להתקיים שוויון (מה שבוודאי לא נכון במקרה הסופי).

משפט קנטור מתקבל כמקרה פרטי של משפט קניג. אם לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in A} בוחרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa_i = 1} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu_i = 2} , אז ממשפט קניג נקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| = \sum_{i\in A} 1<\prod_{i\in A} 2 = 2^{|A|}}

משפט קניג מניח את אקסיומת הבחירה, ולמעשה שקול לה.

מגדירים את הקופינליות של עוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} בתור העוצמה הקטנה ביותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |I|} שמקיימת את התנאי הבא: לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in I} קיימת עוצמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda_i < \kappa} כך שמתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa = \sum_{i \in I} \lambda_i} . מסמנים את הקופינליות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} בסימון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{cf}(\kappa)} . נשים לב שתמיד ניתן לבחור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |I| = \kappa} , ואז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa = \sum_{i \in I} 1} . לכן תמיד מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{cf}(\kappa) \le \kappa} .

ממשפט קניג נובע מיד ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa < \kappa^{\mathrm{cf}(\kappa)}} (בוחרים את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} ממשפט קניג להיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} מהגדרת הקופינליות). מהזהות האחרונה נקבל שלכל קבוצה אינסופית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|<\mathrm{cf}\left(2^{|A|}\right)} . ההוכחה נעשית בדרך השלילה:

נניח בשלילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|\ge\mathrm{cf}\left(2^{|A|}\right)} . אז לפי הזהות האחרונה נקבל את הסתירה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{|A|}<\left(2^{|A|}\right)^{cf\left(2^{|A|}\right)}\le\left(2^{|A|}\right)^{|A|}=2^{|A|\cdot|A|}=2^{|A|}}

קיבלנו שלקבוצות אינסופיות מתקיים האי-שוויון החזק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A|<\mathrm{cf}\left(2^{|A|}\right)} . זהו אי-שוויון חזק יותר מאשר משפט קנטור משום ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{cf}\left(2^{|A|}\right)\le 2^{|A|}} , וייתכנו מקרים בהם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{cf}\left(2^{|A|}\right)<2^{|A|}} .

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

היסטוריה

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

ב-1891 פרסם קנטור מאמר בגרמנית בשם "Über eine elementare Frage der Mannigfaltigkeitslehre" ("על שאלה אלמנטרית בתורת הקבוצות"). במאמר מופיע האלכסון של קנטור, ומיד לאחריו כתב קנטור:

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

בהמשך המאמר, פונה קנטור להוכחת המשפט. ההוכחה המקורית של קנטור זהה במהותה לנוסח המודרני של ההוכחה, אך היא נוסחה בצורה שונה במעט. במקור קנטור הראה שאין התאמה חד-חד-ערכית ועל בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} לבין קבוצת הפונקציות המציינות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} (כאמור, נוסח זה שקול לנוסח על קבוצת החזקה). קנטור טען שאילו הייתה התאמה כזו, הרי שהייתה קיימת פונקציה דו-מקומית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(a,x)} , כך שלכל פונקציה מציינת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} שהותאם לה האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(a,x) = f(x)} . כעת קנטור בונה פונקציה מציינת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x)} שמוגדרת כהיפך מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(x,x)} (ניתן להגדיר כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) = 1-\phi(x,x)} ). לפי ההנחה קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \in A} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(d,x) = g(x)} , ולכן מקבלים סתירה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(d,d) = g(d) \ne \phi(d,d)} .‏

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

ראו גם

• תורת הקבוצות - מונחים
• הפרדוקס של קנטור

לקריאה נוספת

• Nikolai Konstantinovich Vereshchagin, Alexander Shen, Basic set theory, p. 24-30, American Mathematical Soc., 2002, מסת"ב 0-8218-2731-6
• Robert Lawson Vaught, Set theory: an introduction, p. 53-54, Springer, 2001, מסת"ב 0-8176-4256-0

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

מדיה וקבצים בנושא משפט קנטור בוויקישיתוף

• גדי אלכסנדרוביץ', הפרדוקס של ראסל ומשפט קנטור, באתר "לא מדויק", 20 בנובמבר 2010
• Arindama Singh, Cantor's Little Theorem
• משפט קנטור, באתר MathWorld (באנגלית)
• משפט קנטור, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

ערך מומלץ

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

משפט קנטור38157683Q474881