הצגת המקור של הדף "משפט קנטור"

{{פירוש נוסף|נוכחי=משפט בתורת הקבוצות|ראו=[[משפט קנטור (פירושונים)]]}}
[[קובץ:Georg Cantor2.jpg|שמאל|ממוזער|200 פיקסלים|[[גאורג קנטור]]]]
{{סימון מתמטי}}
'''משפט קנטור''' הוא [[משפט (מתמטיקה)|משפט מתמטי]] ב[[תורת הקבוצות]], הקובע שה[[עוצמה (מתמטיקה)|עוצמה]] של כל [[קבוצה (מתמטיקה)|קבוצה]] קטנה מהעוצמה של [[קבוצת החזקה]] שלה. בפרט, לכל קבוצה, גם אם היא [[קבוצה אינסופית|אינסופית]], יש קבוצה גדולה ממנה (במובן מדויק שיוגדר בהמשך). מזה נובע כי אין אינסוף גדול ביותר, ולכן יש [[אינסוף]] גדלים אינסופיים השונים זה מזה.

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

==מושגים==
'''[[קבוצה (מתמטיקה)|קבוצה]]''' היא עצם יסודי במתמטיקה שניתן לתארו כאוסף כלשהו של '''[[איבר (מתמטיקה)|איברים]]'''.{{הערה|ההגדרה המעורפלת של קבוצה בערך זה שייכת ל[[תורת הקבוצות הנאיבית]]. הגדרה זו בעייתית (כמוסבר בהמשך הערך), והיא הוחלפה בהגדרה מדויקת במסגרת [[תורת הקבוצות האקסיומטית]]. בכל זאת, בערך זה נשתמש בגישה הנאיבית משום שהיא פשוטה יותר להבנה. כל התוצאות בערך זה נכונות גם בתורת הקבוצות האקסיומטית, למעט דקויות שידונו במהלך הערך.}} לגבי כל איבר וכל קבוצה ייתכנו שתי אפשרויות: האיבר שייך לקבוצה או שאינו שייך לקבוצה.

===פונקציות===
[[קובץ:Bijection.svg|שמאל|ממוזער|200 פיקסלים|דוגמה לפונקציה חד-חד-ערכית ועל מקבוצה <math>X</math> לקבוצה <math>Y</math>. קיומה של הפונקציה מעיד על כך שבשתי הקבוצות אותו מספר של איברים.]]
'''[[פונקציה]]''' מקבוצה <math>A</math> לקבוצה <math>B</math> מתאימה לכל איבר ב-<math>A</math> איבר יחיד ב-<math>B</math>. ייתכן שלכמה איברים ב-<math>A</math> מותאם אותו איבר ב-<math>B</math>, וייתכן שיש איברים של <math>B</math> שאף איבר של <math>A</math> אינו מותאם להם.

על פונקציה מ-<math>A</math> ל-<math>B</math> נאמר שהיא '''[[פונקציה חד-חד-ערכית|חד-חד-ערכית]]''', אם לכל שני איברים שונים ב-<math>A</math> מותאמים איברים שונים ב-<math>B</math>. נאמר שהפונקציה היא '''[[פונקציה על|על]] <math>B</math>''' אם לכל איבר ב-<math>B</math> יש איבר ב-<math>A</math> שהותאם לו. פונקציה ששתי התכונות מתקיימות בה יחדיו נקראת '''[[פונקציה חד-חד-ערכית ועל|חד-חד-ערכית ועל]]'''. פונקציה חד-חד-ערכית ועל מתאימה את שתי הקבוצות זו לזו, כך שלכל איבר באחת מן הקבוצות יש בן זוג יחיד בקבוצה השנייה.

===השוואת גודלן של קבוצות===
קיומה של פונקציה חד-חד-ערכית ועל מ[[קבוצה סופית]] <math>A</math> לקבוצה <math>B</math> מראה שלשתי הקבוצות יש אותו מספר איברים, משום שלכל איבר מכל אחת מן הקבוצות יש בן זוג יחיד שהותאם לו מהקבוצה השנייה. אפשר לספור את איברי שתי הקבוצות יחד. קנטור הבין שניתן להשתמש ברעיון הזה כדי להשוות גם ב[[קבוצה אינסופית|קבוצות אינסופיות]] בגודלן. נניח כי <math>A,B</math> הן קבוצות כלשהן (אולי אינסופיות). אם קיימת פונקציה חד-חד-ערכית ועל מ-<math>A</math> ל-<math>B</math> נאמר שהקבוצות האלה '''[[קבוצות שקולות|שקולות]]''', ונסמן <math>A\sim B</math>.{{הערה|שקילות היא תכונה [[יחס רפלקסיבי|רפלקסיבית]], [[יחס סימטרי|סימטרית]], ו[[יחס טרנזיטיבי|טרנזיטיבית]], אבל מסיבות פורמליות שלא נכנס אליהן כאן, היא אינה [[יחס שקילות]] (או [[יחס (תורת הקבוצות)|יחס]] בכלל).}} השקילות בין הקבוצות מבטאת, על-פי קנטור, את הרעיון שיש להן אותו מספר של איברים. אם שתי קבוצות <math>A,B</math> הן שקולות, מסמנים <math>|A|=|B|</math>. על הסימן <math>|A|</math> חושבים כאילו הוא מסמן את מספר האיברים בקבוצה <math>A</math>, שיכול להיות אינסופי. זוהי ה'''[[עוצמה (מתמטיקה)|עוצמה]]''' של <math>A</math>.

מן המקרה של קבוצות סופיות ידוע לנו שהעוצמה של קבוצה אחת יכולה להיות גדולה מן העוצמה של קבוצה אחרת. למשל, בקבוצה עם ארבעה איברים יש יותר איברים מאשר בקבוצה עם איבר אחד. רעיון זה מתבטא בעובדה שקיימת פונקציה חד-חד-ערכית שאינה על מהקבוצה השנייה לראשונה. באופן כללי לכל שתי קבוצות <math>A,B</math> נאמר כי <math>|A|\le|B|</math>, אם קיימת פונקציה חד-חד-ערכית (שאינה בהכרח על) מ-<math>A</math> ל-<math>B</math>.{{הערה|כמקודם, תכונה זו מקיימת את האקסיומות המגדירות [[סדר חלקי|יחס סדר]], אבל פורמלית היא אינה יחס.}} כלומר <math>B</math> גדולה (או שווה) מ-<math>A</math> אם אפשר להתאים לכל איבר ב-<math>A</math> בן זוג יחיד ב-<math>B</math>, גם אם נשארים איברים של <math>B</math> שלא הותאם להם בן זוג. אם מתקיים <math>|A|\le|B|</math> וגם <math>|A|\ne|B|</math>, אז נאמר כי <math> |A|<|B|</math>. [[משפט קנטור-שרדר-ברנשטיין]] קובע שאם <math>|A|\le|B|</math> וגם <math>|A|\ge|B|</math>, אז <math>|A|=|B|</math> (המשפט הזה אינו מובן מאליו: הוא טוען שאם יש פונקציה חד-חד-ערכית מ-<math>A</math> ל-<math>B</math>, ופונקציה חד-חד-ערכית מ-<math>B</math> ל-<math>A</math>, אז יש גם פונקציה שהיא בו-זמנית חד-חד-ערכית ועל).

===סימונים===
קבוצה <math>C</math> תקרא [[תת-קבוצה]] של <math>A</math>, אם כל איבר של <math>C</math> הוא גם איבר של <math>A</math>. קבוצת כל התת-קבוצות של <math>A</math> נקראת '''[[קבוצת החזקה]]''' של <math>A</math>, אשר לה ניתן הסימון <math>\mathcal{P}(A)</math> (אם כי לפעמים משתמשים גם בסימון <math>2^A</math>).

קבוצה מסמנים על פי רוב ב[[אלפבית לטיני|אות לטינית]] [[אות גדולה|גדולה]]. אם רוצים לפרט את איברי הקבוצה כותבים אותם בתוך [[סוגריים|סוגריים מסולסלים]], כשהם מופרדים בפסיקים. למשל <math>\{a,b,c\}</math> היא קבוצה שאיבריה הם <math>a,b,c</math>. דרך נוספת לציון קבוצה היא ציון תנאי שאיברי הקבוצה מקיימים. למשל <math>\{x:1<x<3\}</math> היא קבוצת המספרים שבין 1 ל-3, ואילו <math>\{p^2:p\text{ is prime}\}</math> היא קבוצת המספרים שהם [[מספר ריבועי|ריבועים]] של [[מספר ראשוני|המספרים הראשוניים]].
*אם <math>a</math> הוא איבר של הקבוצה <math>A</math> מסמנים זאת <math>a\in A</math>, ואם הוא אינו איבר של <math>A</math> מסמנים זאת <math>a\notin A</math>.
*פונקציה מ-<math>A</math> ל-<math>B</math> מסמנים <math>f:A\to B</math>. את האיבר ב-<math>B</math> שהפונקציה מתאימה לאיבר <math>a</math> ב-<math>A</math> מסמנים <math>f(a)</math>. למשל הפונקציה <math>f</math> שמתאימה לכל מספר טבעי את העוקב שלו מוגדרת לפי החוק <math>f(n)=n+1</math>, אבל ישנן פונקציות מסובכות, שלא ניתן לכתוב להן חוקים מסוג זה.
*אם <math>C</math> תת-קבוצה של <math>A</math>, כלומר כל איבר של <math>C</math> הוא גם איבר של <math>A</math>, מסמנים <math>C\sube A</math>.
*[[הקבוצה הריקה]] היא קבוצה שאין בה אף איבר והיא מסומנת כך <math>\empty=\{\ \}</math>. לכל קבוצה שהיא A מתקיים <math>\empty\sube A</math>.
*לפי הסימונים שהצגנו עתה, ניתן להגדיר את קבוצת החזקה של <math>A</math> כך: <math>\mathcal{P}(A)=\{C:C\sube A\}</math>.

==נוסח המשפט==
'''משפט קנטור'''. לכל קבוצה <math>A</math> (סופית או אינסופית), מתקיים <math>|A|<|\mathcal{P}(A)|</math>.

לבו של המשפט בטענה שהקבוצות <math>A</math> ו-<math>P(A)</math> אינן שקולות זו לזו, אפילו כאשר <math>A</math> אינסופית. הוא מראה שלא כל הקבוצות האינסופיות הן שוות עוצמה, ושלמעשה לכל קבוצה אינסופית ניתן למצוא קבוצה עם עוצמה גדולה יותר.

==הוכחת המשפט==
הוספה נאיבית של איברים לקבוצה אינסופית <math>A</math> אינה משנה את העוצמה{{הערה|אחת ה'''הגדרות''' למושג "קבוצה אינסופית" היא שזו קבוצה שהוספה של איבר אחד אינה משנה את העוצמה שלה; ראו [[אינסופיות לפי דדקינד]].}} גם אם ניקח שתי קבוצות אינסופיות מעוצמה זהה, ו[[איחוד (מתמטיקה)|נאחד]] אותן, עוצמת האיחוד תהיה שווה לעוצמה של כל אחת מהקבוצות בנפרד. אפילו עוצמתה של קבוצת [[מספר רציונלי|המספרים הרציונלים]] (הכוללת את כל ה[[שבר (מתמטיקה)|שברים]]) זהה לעוצמת [[קבוצת המספרים הטבעיים]] לבדם (להוכחה ראו [[מספר רציונלי#עוצמה|כאן]] ו[[עוצמה (מתמטיקה)#שקילות בין קבוצות|כאן]]). עם זאת, טוען המשפט, קבוצת החזקה היא בעלת עוצמה גדולה יותר. <!-- לדעתי הפסקה הזו מיותרת; ע.ו.-->

תהי <math>A</math> קבוצה כלשהי. הפונקציה <math>g(a)=\{a\}</math> לכל <math>a\in A</math> היא פונקציה חד-חד-ערכית מ-<math>A</math> ל-<math>\mathcal{P}(A)</math>, ולכן <math>|A|\le |\mathcal{P}(A)|</math>.

נותר אם כך להוכיח כי <math>|A|\ne|\mathcal{P}(A)|</math>. [[הוכחה בדרך השלילה|נניח בשלילה]] כלומר כי <math>|A|=|\mathcal{P}(A)|</math>, ונראה כי הדבר מוביל ל[[סתירה (לוגיקה)|סתירה]].

אם <math>|A|=|\mathcal{P}(A)|</math>, הרי שקיימת פונקציה חד-חד-ערכית ועל <math>f:A\to\mathcal{P}(A) </math> (למעשה אין צורך בהנחה שהפונקציה חד-חד-ערכית; ההוכחה מראה שאפילו פונקציה על בלבד אינה אפשרית). <math>f</math> מתאימה לכל <math>a\in A</math> תת-קבוצה של <math>A</math>, ומכסה באופן הזה את כל התת-קבוצות. לכן לכל <math>a\in A</math> ייתכנו שתי אפשרויות: או שהוא איבר של התת-קבוצה המתאימה לו, או שלא.

נגדיר קבוצה <math>D=\bigl\{a\in A:a\notin f(a)\bigr\}</math>, המורכבת מכל אותם איברי <math>A</math> שאינם איברי התת-קבוצה המתאימה להם. מכאן <math>D\sube A</math>. לפי ההנחה קיים <math>d\in A</math> עבורו <math>f(d)=D</math>.{{הערה|כבר בשלב הזה מתקבלת סתירה במקרה שבו <math>A</math> היא [[הקבוצה הריקה]], שכן לא ייתכן שהאיבר <math>d</math> קיים. ואכן קבוצת החזקה של הקבוצה הריקה כוללת איבר אחד (הקבוצה הריקה עצמה), בעוד הקבוצה הריקה לא כוללת איברים כלל.}}

עתה נשאלת השאלה האם <math>d\in f(d)=D</math>? אם נניח <math>d\in D</math> אז <math>d</math> איבר בקבוצה שהותאמה לו, ולכן <math>d\notin D</math>. אם נניח <math>d\notin D</math> אז <math>d</math> אינו איבר בקבוצה שהותאמה לו, ולכן <math>d\in D</math>.

בשני המקרים הגענו לסתירה, ולכן ההנחה הראשית שלנו חייבת להיות שגויה. מכאן <math>|A|\ne|\mathcal P(A)|</math> ולכן <math>|A|<|\mathcal P(A)|</math>.

===הסבר אינטואיטיבי===
ה[[פילוסוף]] וה[[חידונאי]] [[ריימונד סמוליאן]], בספרו "מה שמו של ספר זה?", מציג גרסה אינטואיטיבית להוכחה. הגרסה המופיעה כאן מבוססת על גרסה זו. כל קבוצה אפשרית של תושבים ביקום (שגודלו עשוי להיות אינסופי) יוצרת לה מועדון (התושבים הם איברי <math>A</math>, והמועדונים הם איברי <math>\mathcal{P}(A)</math>). נניח שכל מועדון נקרא על שם אחד התושבים (זוהי ההנחה שקיימת פונקציה על בין הקבוצות). נקים את המועדון שחבריו הם כל התושבים שאינם חברים במועדון הקרוי על שמם. מועדון זה, ככל מועדון אחר, חייב להיקרא על שם אחד התושבים – למשל [[גראוצ'ו מרקס|גראוצ'ו]].{{הערה|על שם [[גראוצ'ו מרקס]], שאמר "אינני מוכן להיות חבר במועדון המוכן לקבל אנשים כמוני".}} אם גראוצ'ו חבר במועדון, הרי שהוא חבר במועדון הנקרא על שמו, בסתירה להגדרת המועדון; אבל אם הוא לא חבר במועדון, הרי שהוא מקיים את תנאי הקבלה היחיד למועדון, ונעשה בו חבר באופן אוטומטי. סתירה זו מעידה כי ההנחה שאפשר לקרוא כל מועדון על שם תושב, מוטעית. האינסוף של המועדונים גדול יותר מן האינסוף של התושבים.

== נוסח שקול ==
לפונקציה <math>f \colon A \to \{0,1\}</math> (כלומר פונקציה שמתאימה לכל איבר ב-<math>A</math> את המספר 0 או 1) קוראים [[פונקציה מציינת]]. מקובל לסמן את קבוצת כל הפונקציות מ-<math>A</math> ל-<math>B</math> בסימון <math>B^A</math>. על כן קבוצת הפונקציות המציינות של קבוצה <math>A</math> היא <math>\{0,1\}^A</math>.

נשים לב כי <math>\{0,1\}^A \sim \mathcal{P}(A)</math>. זאת משום שלכל פונקציה מציינת ניתן להתאים את התת-קבוצה של <math>A</math> שהפונקציה המציינת מתאימה לאיבריה (ורק לאיבריה) את המספר 1, ולשאר האיברים היא מתאימה 0. לכן משפט קנטור קובע כי <math>|A| < |\{0,1\}^A|</math> (למעשה זהו הנוסח של קנטור במקור).

מגדירים את פעולת ה[[חזקה (מתמטיקה)|חזקה]] בין עוצמות באופן הבא: <math>|B|^{|A|} = |B^A|</math>. הגדרה זו מכלילה את ההגדרה הרגילה לחזקה בין [[מספר טבעי|מספרים טבעיים]], ומתלכדת עימה כאשר היא מופעלת על טבעיים (ראו [[חזקה (מתמטיקה)#קבוצות ועוצמות|חזקה: קבוצות ועצמות]]). בהתאם להגדרה זו: <math> |\{0,1\}^A| = |\{0,1\}|^{|A|} = 2^{|A|}</math>.

על כן נוכל לנסח את משפט קנטור גם באופן הבא: לכל עוצמה <math>|A|</math> מתקיים: <math>|A|<2^{|A|}</math>.

== מקרים פרטיים ==
{{חלונית
|רקע= #FFFFFF
|רוחב=10%
| כותרת =
|יישור= left
|תוכן=
<math>A=\{1,2,3\}</math>

<math>|A|=3</math>

<math>\mathcal{P}(A) = \{\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}</math>

<math> |\mathcal{P}(A)| = 8 = 2^3</math>
}}

=== קבוצות סופיות ===
אם <math>A</math> היא [[קבוצה סופית]] בעלת <math>n</math> איברים (<math>|A|=n</math>), אז <math>|\mathcal{P}(A)| = 2^n</math>. תוצאה זו מתקבלת משיקול [[קומבינטוריקה|קומבינטורי]] פשוט: בהינתן תת-קבוצה שרירותית של <math>A</math>, לגבי כל איבר ב-<math>A</math> יש שתי אפשרויות: או שהוא איבר של התת-קבוצה או שהוא לא. מ[[עקרון הכפל]] מקבלים שיש: <math>2\cdot 2\cdots 2 = 2^n</math> אפשרויות לכל <math>n</math> האיברים יחדיו, ולכן זהו מספר התת-קבוצות (כאמור בפרק הקודם, תוצאה זו נכונה אפילו לעוצמות אינסופיות).

לכן משפט קנטור לקבוצות סופיות קובע את ה[[אי-שוויון (מתמטיקה)|אי-שוויון]] הידוע <math>\ n<2^n</math>, לכל <math>n</math> טבעי. אי-שוויון זה ניתן להוכחה בפשטות ב[[אינדוקציה מתמטית|אינדוקציה]], ולכן עיקר העניין במשפט קנטור הוא בהשלכותיו לגבי קבוצות אינסופיות.

=== קבוצת המספרים הטבעיים והאלכסון של קנטור ===
{{ערך מורחב|האלכסון של קנטור}}
ישנו עניין מיוחד במשפט קנטור כאשר הוא מופעל על [[קבוצת המספרים הטבעיים]], <math>\{0,1,2,3,\ldots\}</math>.{{הערה|המספר [[אפס (מספר)|0]] נחשב למספר טבעי במסגרת ערך זה.}} הסימון לקבוצת המספרים הטבעיים הוא <math>\mathbb{N}</math>. קנטור בחר לסמן את העוצמה של <math>\mathbb{N}</math>, שהיא העוצמה האינסופית הקטנה ביותר, בסימון [[אלף אפס|אָלֶף אֶפֶס]]: <math>|\mathbb{N}| = \aleph_0</math>. משפט קנטור מראה כי <math> |\mathbb{N}|<|\mathcal{P}(\mathbb{N})|</math>, או באופן שקול: <math>\aleph_0<2^{\aleph_0}</math>.

במקרה הזה ניתן להציג את הוכחת משפט קנטור באופן מוחשי יותר, שממנו גם ברור השם "לכסון". הוכחת המשפט נפתחת בהנחה שקיימת פונקציה חד חד ערכית ועל <math>f \colon \mathbb{N} \to \mathcal{P}(\mathbb{N})</math>. ניתן להציג פונקציה שכזו כ[[סדרה אינסופית]] של איברי <math>\mathcal{P}(\mathbb{N})</math>, כך: <math>A_0, A_1, A_2,\ldots</math>. כאשר מוסכם ש-<math>f(n) = A_n</math> (למעשה זוהי ההגדרה הפורמלית של סדרה). כעת מגדירים את הקבוצה הבעייתית <math>D = \{n \in \mathbb{N} \mid n \not\in A_n \}</math>. לפי ההנחה קיים <math>m</math> כך ש-<math>A_m = D</math>, אך זה לא ייתכן, כי כזכור, נובע מכך שמתקיים בו זמנית <math>m \in A_m</math> ו-<math>m \not\in A_m</math>.

את הטיעון הנ"ל ניתן גם להציג כך: נציג כל <math>A</math> שהוא איבר של <math>\mathcal{P}(\mathbb{N})</math> כסדרה אינסופית של ספרות באופן הבא: הספרה ה-<math>n</math> בסדרה (החל מ-0) תהיה 1 אם <math>n \in A</math>, ואילו אם <math>n \not\in A</math> היא תהיה 0. למשל הקבוצה <math>\{0,1,2,4,8,\ldots\}</math> תוצג בצורה: <math>1\ 1\ 1\ 0\ 1\ 0\ 0\ 0\ 1\ldots</math>.

את הסדרה <math>A_0, A_1, A_2,\ldots</math> ניתן להציג כרשימה אינסופית של הייצוגים של כל אחד מאיברי הסדרה כסדרת ספרות. למשל את:
: <math>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</math>
נציג בצורה:
:<math>\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}</math>

כעת נשים לב כיצד נבנה <math>D</math>. לפי ההגדרה, אם <math>n \not\in A_n</math>, אז הספרה ה-<math>n</math> בייצוג של <math>D</math> היא 1. ואילו אם <math>n \in A_n</math> אז הספרה ה-<math>n</math> בייצוג של <math>D</math> היא אפס. במילים אחרות, הספרה ה-<math>n</math> של <math>D</math> היא בדיוק ההפך מהספרה ה-<math>n</math> של <math>A_n</math>. במסגרת הדוגמה שלנו נוכל להמחיש זאת כך:
:<math>\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}</math>

לא ייתכן כי קיים <math>A_m</math> כך ש-<math>A_m = D</math>, כי <math>D</math> בהכרח נבדל מ-<math>A_m</math> בספרה ה-<math>m</math> בייצוג שלו.

טיעון האלכסון שהוצג זה עתה קרוי '''[[האלכסון של קנטור]]'''. הוא הוצג על ידי קנטור באותו מאמר בו הציג את משפט קנטור, וחשיבותו חורגת מהיותו מקרה פרטי של משפט קנטור. זאת משום שהסדרות של הספרות המייצגות כאן תת-קבוצות של <math>\mathbb{N}</math>, יכולות באותה מידה לייצג [[מספר ממשי|מספרים ממשיים]] בין 0 ל-1, שסדרת הספרות היא ה[[בסיס בינארי|כתיב הבינארי]] (אחרי הנקודה) שלהם (למשל <math>10000\ldots</math> מייצג את 0.1 שהוא [[חצי]] בכתיב בינארי). כאשר מציגים את האלכסון של קנטור כהוכחה לאי-שקילות קבוצת המספרים הטבעיים <math>\mathbb{N}</math> לקבוצת המספרים הממשיים <math>\mathbb{R}</math> (עובדה שיכולה להפתיע, שכן <math>\mathbb{N}</math> שקולה ל-<math>\mathbb{Q}</math>, שהיא קבוצת ה[[מספר רציונלי|מספרים הרציונליים]]) נהוג, לשם הנוחות, להשתמש בהצגה של המספרים ב[[בסיס עשרוני]] (מבחינה היסטורית, קנטור הוכיח לראשונה את האי-שקילות של הטבעיים והממשיים 17 שנה קודם, ב[[הוכחת האי-מנייה הראשונה של קנטור|שיטה מוכרת פחות]]).

עוצמת המספרים הממשיים (השווה גם לעוצמת הממשיים שבין 0 ל-1 בלבד) קרויה [[עוצמת הרצף]], ומקובל לסמנה <math>\aleph</math>. העובדה שהן את הממשיים והן את התת-קבוצות של <math>\mathbb{N}</math> ניתן לבטא כרצפי ספרות אינסופיים, מעידה כי <math>\mathbb{R}</math> ו-<math>\mathcal{P}(\mathbb{N})</math> שקולות.{{הערה|ישנו קושי אחד המעיב על ההתאמה הזו: אמנם כל סדרת ספרות בינאריות מייצגת תת-קבוצה אחת ויחידה של <math>\mathbb{N}</math>, אולם בממשיים המצב מעט שונה. לכל מספר ממשי שיש לו פיתוח סופי בבסיס בינארי, ישנם שני ייצוגים שונים כסדרות של ספרות. אחד הנגמר באינסוף אפסים, ואחר הנגמר באינסוף אחדות (ראו {{משמאל לימין|[[0.999...]]}} להסבר התופעה). קושי זה אינו מהווה מכשול אמיתי שכן הופעות כפולות הן זניחות בהתאמות אינסופיות (אם <math>|A|</math> עוצמה אינסופית, אז <math>2|A|=|A|</math>).}} לכן <math>2^{\aleph_0} = \aleph</math>.

=== קבוצת כל הקבוצות ===
ב[[תורת הקבוצות הנאיבית]] ניתן להגדיר את "[[הקבוצה האוניברסלית|קבוצת כל הקבוצות]]" <math>U</math> שכל קבוצה שהיא היא איבר שלה (כולל היא עצמה). באמצעות משפט קנטור ניתן להראות שהגדרה זו מובילה ל[[פרדוקס]]ים. כדי לפתור את הפרדוקסים פותחה [[תורת הקבוצות האקסיומטית]] שבמסגרתה בלתי אפשרי להגדיר קבוצות בעייתיות כגון <math>U</math>.

שני הפרדוקסים הידועים ביותר הם:
* '''[[הפרדוקס של קנטור]]''', שהתגלה על ידי קנטור עצמו מעט לאחר שפרסם את משפט קנטור. הפרדוקס נוצר מניסיון להפעיל את משפט קנטור על <math>U</math>.{{ש}}הקבוצה <math>\mathcal{P}(U)</math> היא קבוצה שכל איבריה הם קבוצות. בפרט היא תת-קבוצה של <math>U</math>. לכן הפונקציה החד-חד-ערכית <math>f: \mathcal{P}(U) \to U</math> המוגדרת <math>f(A)=A</math> קיימת ו[[מוגדר היטב|מוגדרת היטב]]. מכאן ש-<math>|P(U)| \le |U|</math>. מצד שני, לפי משפט קנטור מתקיים להפך <math>|P(U)|>|U|</math>.
* '''[[הפרדוקס של ראסל]]''', שהוצג על ידי המתמטיקאי [[ברטראנד ראסל]] בשנת [[1901]] ושואב השראה מהוכחת משפט קנטור. ואכן, ניתן לראות בפרדוקס של ראסל [[מקרה פרטי]] של הוכחת משפט קנטור לגבי הקבוצה <math>U</math>. כאמור, הפונקציה <math>f(A)=A</math> היא פונקציה חד-חד-ערכית מ-<math>\mathcal{P}(U)</math> ל-<math>U</math>. אולם מעקב אחרי שלבי הוכחת קנטור יוביל אותנו למסקנה שפונקציה שכזו לא תיתכן. נגדיר את <math>D = \{a \in U \mid a \not\in f(a)\} = \{a \mid a\not\in a\}</math>. כעת נקבל שאם <math>D \in D</math> אז <math>D \not\in D</math>, ואילו אם <math>D \not\in D</math> אז <math>D \in D</math>.

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

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

כל קלט (סופי) אפשרי הנתון ב[[שפה פורמלית|שפה]] כלשהי ניתן לקודד (לייצג) כמספר טבעי. קידוד שכזה נקרא [[מספור גדל]] ומחשבים מודרניים מיישמים אותו על ידי [[בסיס בינארי|קידוד בינארי]].{{הערה|קיומו של הקידוד נובע למעשה מהעובדה שקבוצת המילים האפשריות בשפה כלשהי היא [[קבוצה בת-מנייה]].}} בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה <math>A</math> הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן". ולהפך, לכל קבוצה של מספרים טבעיים <math>A</math> ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-<math>A</math>. במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, <math>\mathcal{P}(\mathbb{N})</math>.

מצד שני, כל תוכנית מחשב היא רצף סופי של סימנים של [[שפת תכנות]]. לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד (ואכן בפועל כל תוכנית מחשב בשפה מסוימת מתרגמת לקידוד בינארי שונה ב[[שפת מכונה]]). מכאן שקבוצת כל תוכניות המחשב שקולה ל-<math>\mathbb{N}</math>.

משפט קנטור קובע ש-<math> |\mathbb{N}|<|\mathcal{P}(\mathbb{N})|</math>, ולכן יש הרבה יותר בעיות הכרעה מאשר תוכניות מחשב. מכאן שישנן בעיות הכרעה (ולמעשה, [[כמעט כל]] בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב. הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא [[בעיית העצירה]]. [[אלן טיורינג]] הוכיח זאת בשנת [[1936]] בשיטת האלכסון. דוגמאות רבות נוספות מגיעות מ[[משפט רייס]].

טיעון דומה קובע שמרבית המספרים הממשיים אינם [[מספר חשיב|ניתנים לחישוב]]. זאת מכיוון שעוצמת החישובים האפשריים היא <math>|\mathbb{N}|</math> (שכן כל [[חישוב (מדעי המחשב)|חישוב]] יכול להעשות על ידי תוכנית מחשב), ואילו לפי האלכסון של קנטור, עוצמה זו קטנה מעוצמת הממשיים.

==== פונקציות רציפות ====
[[פונקציה רציפה (אנליזה)|פונקציה רציפה]] היא [[פונקציה ממשית]] <math>f \colon \mathbb{R} \to \mathbb{R}</math> (פונקציה מקבוצת ה[[מספר ממשי|מספרים הממשיים]] לעצמה) שיש לה את התכונה שככל שמתקרבים לנקודה (מספר ממשי) כלשהי <math>x</math>, ערכי הפונקציה הולכים וקרבים ל-<math>f(x)</math>, שהוא ערך הפונקציה בנקודה <math>x</math> (ה[[גרף של פונקציה|גרף]] של פונקציות רציפות הוא קו רציף, ומכאן שמן). את קבוצת הפונקציות הרציפות מקובל לסמן <math>C</math>, ואילו קבוצת הפונקציות הממשיות כולן היא <math>\mathbb{R}^{\mathbb{R}}</math>. נראה כי <math>|C|<|\mathbb{R}^{\mathbb{R}}|</math>, כלומר [[כמעט כל]] הפונקציות הממשיות אינן רציפות.

ראשית נמצא את <math>|C|</math>. הערכים שפונקציה רציפה מקבלת בכל נקודה ב[[הישר הממשי|ישר הממשי]] נקבעים על ידי הערכים שהיא מקבלת בנקודות ה[[מספר רציונלי|רציונליות]]. זאת משום שהמספרים הרציונליים [[קבוצה צפופה|צפופים]] בישר, ולכן ניתן לקבל את הערך בכל נקודה אי-רציונלית כ[[גבול (מתמטיקה)|גבול]] של סדרת הערכים בנקודות רציונליות המתקרבת לנקודה (פורמלית: לכל <math>a</math> ממשי, בהינתן סדרת רציונליים <math>x_n \to a</math>, מתקיים <math>f(a) = \lim_{n \to \infty} f(x_n)</math>). מכאן שיש פונקציה חד-חד-ערכית מ-<math>C</math> לקבוצת הפונקציות מהרציונליים לממשיים <math>\mathbb{R}^{\mathbb{Q}}</math>, ולכן <math>|C| \le |\mathbb{R}^{\mathbb{Q}}|</math>. קבוצת הרציונליים שקולה לקבוצת הטבעיים, ולכן בעזרת כללי [[אריתמטיקה של עוצמות]] (ומהזהות <math>\aleph_0\cdot\aleph_0=\aleph_0</math> הנובעת מ[[פונקציית הזיווג של קנטור]]) נקבל:
:<math>|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</math>

מצד שני, לכל מספר ממשי <math>a</math> ניתן להתאים את ה[[פונקציה קבועה|פונקציה הקבועה]] <math>f(x) = a</math> שהיא רציפה. מכאן ש-<math>|C| \ge |\mathbb{R}| = \aleph</math>. מ[[משפט קנטור-שרדר-ברנשטיין]] נקבל <math>|C| = \aleph</math>.

נעבור ל-<math> \mathbb{R}^{\mathbb{R}}</math>. קבוצה זו כוללת בין השאר כל פונקציה מציינת של <math>\mathbb{R}</math>. [[#נוסח שקול|קבענו כבר]] כי עוצמת קבוצת הפונקציות המציינות של <math>\mathbb{R}</math> היא <math>2^{|\mathbb{R}|} = 2^{\aleph}</math>. לכן <math> |\mathbb{R}^{\mathbb{R}}|\ge 2^{\aleph}</math> (למעשה מתקיים <math> |\mathbb{R}^{\mathbb{R}}| = 2^{\aleph}</math>
,,{{הערה|
ניתן להראות זאת בעזרת אריתמטיקה של עוצמות בצורה דומה למקרה <math>|\mathbb{R}^{\mathbb{Q}}| = 2^{\aleph_0}</math>. דרך אחרת היא להבחין כי ה[[גרף של פונקציה|גרף]] ה[[קואורדינטות קרטזיות|קרטזי]] של כל פונקציה <math>f: \mathbb{R} \to \mathbb{R}</math> הוא תת-קבוצה של ה[[מרחב אוקלידי|מישור האוקלידי]] <math>\mathbb{R}^2</math>, ולכן <math> |\mathbb{R}^{\mathbb{R}}| \le |\mathcal{P}(\mathbb{R}^2)| = 2^{\aleph}</math>.
}}).

לפי משפט קנטור <math>\aleph<2^{\aleph}</math>, ולכן <math>|C|<|\mathbb{R}^{\mathbb{R}}|</math>.

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

=== מספרי ב' ===
ממשפט קנטור מגיעה המוטיבציה להגדרת סדרה של עוצמות הקרויה '''מספרי ב''''. איברי הסדרה הם:
:<math>\ \beth_0 = \aleph_0, \ \beth_1 = 2^{\aleph_0} = \aleph, \ \beth_2 = 2^{2^{\aleph_0}} \ \beth_3 = 2^{2^{2^{\aleph_0}}}\ \ldots</math>

כלומר זוהי סדרת העוצמות:
:<math>|\mathbb{N}|,\ |P(\mathbb{N})|,\ |P(P(\mathbb{N}))|,\ |P(P(P(\mathbb{N})))|,\ \ldots</math>

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

ב[[הגדרה רקורסיבית]], מספרי ב' מוגדרים:
:<math> \beth_0 = \aleph_0\ ;\ \beth_{\alpha+1} = 2^{\beth_{\alpha}} </math>

מספרי ב' מוגדרים גם ל[[אינדקס (מתמטיקה)|אינדקסים]] [[מספר סודר|סודרים]], ולא רק טבעיים. לשם כך יש להוסיף להגדרה הרקורסיבית את המקרה של סודר גבולי:
:<math>\beth_{\lambda}=\sup\{ \beth_{\alpha}\mid \alpha<\lambda \}</math>

למשל <math>\beth_{\omega}</math> הוא העוצמה הקטנה ביותר שגדולה מכל העוצמות <math> \beth_n</math> לכל <math>n</math> טבעי.

בנוסף קנטור הגדיר את הסדרה (המוכללת) <math>\aleph_{\alpha}</math> כסדרת כל העוצמות (<math>\aleph_{\alpha}</math> הוא העוצמה ה-<math>\alpha</math> בגודלה). קנטור שיער ש-<math> \beth_1 = \aleph_1</math> (כלומר שאין עוצמה בין עוצמת הטבעיים לעוצמת הממשיים). ובאופן כללי יותר ש-<math> \beth_\alpha = \aleph_\alpha</math>. השערות אלו ידועות כ[[השערת הרצף]] ו[[השערת הרצף המוכללת]] בהתאמה.

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

=== שיטת האלכסון ===
הוכחת משפט קנטור יחד עם טיעון האלכסון של קנטור שהוצג לצדה הולידו שיטה כללית להוכחת טענות המשמשת בתחומים רבים במתמטיקה. השיטה נקראת '''[[לכסון (שיטת הוכחה)|אלכסון]]''', והיא משמשת בעיקר ב[[מדעי המחשב]] וב[[לוגיקה מתמטית]].

הרעיון הכללי בשיטת האלכסון הוא לבנות [[אובייקט מתמטי]] קביל ה[[התייחסות עצמית|מתייחס לעצמו]] באופן עקיף. אופי ההתייחסות תלוי בטענה שאותה רוצים להוכיח. הוכחה כללית בשיטה זו בנויה כך: בהינתן אוסף של איברים <math>\Lambda</math> ואוסף של אובייקטים מהצורה <math>\phi_\alpha</math>, לכל <math>\alpha \in \Lambda</math>. נניח שכל אובייקט <math>\phi_\alpha</math> פועל בצורה כלשהי על איברי <math>\Lambda</math>. נסמן את הפעולה של <math>\phi_\alpha</math> על <math>\beta \in \Lambda</math> כ-<math> \phi_\alpha(\beta)</math> (ניתן לחשוב על <math>\phi_\alpha</math> כפונקציה של איברי <math>\Lambda</math>). מגדירים אובייקט <math>\phi_D</math> שנקרא ה"אלכסון", כך שתוצאת הפעולה <math>\phi_D(\beta)</math> נקבעת על פי תוצאת הפעולה <math>\phi_{\beta}(\beta)</math>. אם קיים <math>\gamma \in \Lambda</math> כך ש-<math> \phi_\gamma = \phi_D</math>, אז הכרח שהוא מתייחס לעצמו, שכן לפי ההגדרה, <math>\phi_D(\gamma)</math> נקבע על פי <math>\phi_\gamma(\gamma)</math>, כלומר על פי עצמו.

השם "אלכסון" מקורו בהמחשה הוויזואלית של שיטת ההוכחה, כפי שהיא מודגמת בטיעון האלכסון של קנטור. הרעיון הוא לדמיין טבלה (אינסופית לרוב) שכל שורה בה מייצגת איבר <math>\alpha</math> וכל עמודה בה מייצגת אובייקט <math>\phi_\alpha</math> (באותו הסדר). בהצטלבות בין השורה של <math>\beta</math> לעמודה של <math>\phi_\alpha</math> מופיע <math>\phi_\alpha(\beta)</math>. אובייקט ה"אלכסון" <math>\phi_D</math> נבנה על סמך התאים בטבלה שהם מהצורה <math>\phi_{\beta}(\beta)</math>, שמסודרים בקו אלכסוני לאורך ורוחב הטבלה.

להלן דוגמאות חשובות להוכחה בשיטת האלכסון:
* הוכחת משפט קנטור היא מקרה כללי של הוכחה בשיטת האלכסון. נדגים זאת עם נוסח ההוכחה לפונקציות מציינות, שנוח יותר לשימוש במקרה הזה. האוסף <math>\Lambda</math> הוא הקבוצה <math>A</math>. מניחים בשלילה כי לכל פונקציה מציינת של <math>A</math> ניתן להתאים איבר של <math>A</math>. האובייקט <math>\phi_\alpha</math> הוא הפונקציה המציינת שהותאמה לאיבר <math>\alpha \in A</math>. הפעולה <math> \phi_\alpha(\beta)</math> היא פשוט הפעולה הרגילה של הפונקציה <math>\phi_\alpha</math> על האיבר <math> \beta</math>. אובייקט האלכסון <math>\phi_D</math> הוא פונקציה מציינת כך ש-<math>\phi_D(\beta)</math> מוגדר כהיפך מ-<math>\phi_{\beta}(\beta)</math> (0 אם הוא 1, ו-1 אם הוא 0). לפי ההנחה קיים <math>\gamma \in A</math> כך ש-<math> \phi_\gamma = \phi_D</math>, ולכן <math>\phi_\gamma(\gamma) \ne \phi_D(\gamma) = \phi_\gamma(\gamma)</math>. זוהי סתירה, ולכן ההנחה שגויה ומשפט קנטור נכון.
* כאמור, אלן טיורינג הוכיח בלכסון כי [[בעיית העצירה]] אינה ניתנת להכרעה. כלומר לא קיימת תוכנית מחשב שבהינתן כל תוכנית מחשב וקלט אפשרי, תכריע האם התוכנית הנתונה תסיים את פועלה על הקלט הנתון, או שתכנס ל[[לולאה אינסופית]]. במקרה הזה <math>\Lambda</math> היא קבוצת כל תוכניות המחשב (בשפה כלשהי). נניח שקיימת תוכנית <math>\phi</math> שבהינתן תוכנית <math>\alpha</math> וקלט <math>\beta</math> מכריעה האם <math>\alpha</math> עוצרת על <math>\beta</math>. הביטוי <math>\phi_\alpha(\beta)</math> יהיה "כן" אם <math>\alpha</math> עוצרת על <math>\beta</math>, ו"לא" אם <math>\alpha</math> נכנסת ללולאה אינסופית בהינתן <math>\beta</math>. נגדיר תוכנית <math>D</math> שבהינתן קלט <math>\beta</math>, מריצה את <math> \phi</math> כדי לגלות מהו <math>\phi_\beta(\beta)</math> (תוכנית יכולה לקבל כקלט את עצמה, שכן כל תוכנית היא בסך הכל רצף של סימנים בשפה) - אם <math>\phi_\beta(\beta)</math> הוא "לא" אז <math>D</math> משיבה "כן", ואם <math>\phi_\beta(\beta)</math> הוא "לא", אז <math>D</math> לא עוצרת. מכאן ש-<math>\phi_D(\beta)</math> הוא "כן" אם <math>\phi_\beta(\beta)</math> הוא "לא", והוא "לא" אם <math>\phi_\beta(\beta)</math> הוא "כן". כמסקנה נקבל ש-<math>\phi_D(D)</math> הוא ההפך מעצמו. סתירה זו מראה כי ההנחה שלנו כי קיימת תוכנית <math>\phi</math> שמסוגלת להכריע את בעיית העצירה היא שגויה.
* [[משפט האי-שלמות הראשון]], שהוכח על ידי [[קורט גדל]] בשנת [[1931]], הוא משפט מרכזי ב[[לוגיקה מתמטית]]. המשפט קובע שבכל [[תורה (לוגיקה מתמטית)|תורה]] העונה לתנאים מסוימים, קיימות טענות [[עצמאות (לוגיקה מתמטית)|עצמאיות]] שלא ניתנות להוכחה או להפרכה. השלב העיקרי בהוכחת גדל מתבצע בלכסון. במסגרת ההוכחה מתעניינים בכל התכונות שניתן לנסח בתורה הנוגעות למספרים טבעיים. את התכונה שמספרה הוא <math>n</math> ([[מספור גדל]] מראה כיצד להצמיד לכל תכונה מספר משלה) נסמן <math>\phi_n</math>. הביטוי <math>\phi_n(k)</math> הוא הטענה שהמספר <math>k</math> מקיים את התכונה <math>\phi</math> (הטענה עשויה להיות נכונה או שגויה). גדל הראה כיצד ניתן לבנות בשפה תכונה <math>\phi_m</math> (זוהי <math>\phi_D</math>) שמתקיימת רק לאותם מספרים טבעיים שלגביהם לא קיימת הוכחה לטענה <math>\phi_n(n)</math>. כלומר הטענה <math>\phi_m(n)</math> נכונה [[אם ורק אם]] אין הוכחה לטענה <math>\phi_n(n)</math>. כעת נפרש את המשמעות של הטענה <math>\phi_m(m)</math>. לפי הבניה, זוהי טענה שנכונה אם ורק אם אין הוכחה ל-<math>\phi_m(m)</math>. כלומר זוהי טענה שאומרת "אני נכונה אם ורק אם אי אפשר להוכיח אותי".

== משפט קנטור בתורת הקבוצות האקסיומטית ובתורות חלופיות ==
הפרדוקסים שנתגלו בגישתו של קנטור לתורת הקבוצות – גישה שלימים נקראה [[תורת הקבוצות הנאיבית]] – הביאו לפיתוחה של [[תורת הקבוצות האקסיומטית]]. התורה האקסיומטית מסתמכת על מערכת של [[אקסיומה|אקסיומות]] בסיסיות ו[[מוגדר היטב|מוגדרות היטב]], כדי למנוע את הופעתם של פרדוקסים. המערכת המקובלת היא [[אקסיומות צרמלו-פרנקל|מערכת האקסיומות של צרמלו-פרנקל]] (ZF).{{הערה|לרוב מוסיפים למערכת גם את [[אקסיומת הבחירה]], אך זו אינה רלוונטית לדיוננו.}} במערכת זו משפט קנטור תקף לגבי כל קבוצה. [[אקסיומת קבוצת החזקה]] מבטיחה את קיומה של קבוצת החזקה ו[[אקסיומת ההחלפה]] מבטיחה את קיומה של הקבוצה <math>D</math> הנדרשת בהוכחה. [[אקסיומת האינסוף]] קובעת את קיומה של קבוצה אינסופית, ולכן המסקנה ממשפט קנטור כי יש אינסוף עוצמות אינסופיות שונות, אף היא תקפה. הפרדוקסים אינם מופיעים ב-ZF, כי במערכת זו אוסף כל הקבוצות ואוספים דומים לו אינם קבוצות.

בגישות חלופיות לתורת הקבוצות משפט קנטור עשוי שלא להיות תקף. ב[[תורת הטיפוסים|תורות טיפוסים]] שונות להוכחת משפט קנטור אין משמעות, כי לא ניתן להשוות בין <math>A</math> ל-<math> \mathcal{P}(A)</math> שלהן טיפוסים שונים. כדי להתגבר על כך מגדירים קבוצה <math> \mathcal{P}_1(A) = \{\{a\}\mid a\in A\}</math> שיש לה טיפוס זהה ל-<math> \mathcal{P}(A)</math>, ולגביה אכן מתקיים <math> |\mathcal{P}_1(A)| < |\mathcal{P}(A)|</math> בהתאם למשפט קנטור. לאור העובדה שבתורת הטיפוסים קיימת קבוצת כל הקבוצות <math>U</math>, נשאלת השאלה כיצד בתורה זו נמנעים הפרדוקסים של קנטור ושל ראסל. התשובה היא שבתורת הטיפוסים הפונקציה <math>f \colon \mathcal{P}(U) \to U</math> המוגדרת <math>f(A)=A</math> אינה קיימת. למעשה בתורה זו <math> |\mathcal{P}_1(U)| < |\mathcal{P}(U)| < |U|</math>. בתורת הטיפוסים, כאשר מתקיים <math>|\mathcal{P}_1(A)|=|A|</math>, הקבוצה נקראת "קבוצה קנטורית" ולגביה מתקיים משפט קנטור במובנו הרגיל.{{הערה|שם=LTR-טיפוסים|1=M. Randall Holmes, [http://math.boisestate.edu/~holmes/holmes/head.pdf#page=123 Elementary Set Theory with a Universal Set]|כיוון=שמאל}}

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

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

== הכללות ==
[[משפט קניג (תורת הקבוצות)|משפט קניג]], שהוכח על ידי המתמטיקאי ה[[הונגרי]] [[דיולה קניג]] (נודע גם כיוליוס קניג; [[1849]]-[[1913]]) הוא [[הכללה (מתמטיקה)|הכללה]] מרחיקת לכת של משפט קנטור. המשפט קובע שלכל קבוצה <math>A</math>, אם לכל <math>i \in A</math> נתונות זוג עוצמות <math>\kappa_i</math> ו-<math>\mu_i</math>, כך שמתקיים <math> \kappa_i < \mu_i</math>, אז:
:<math>\sum_{i\in A}\kappa_i<\prod_{i\in A}\mu_i</math>

אגף שמאל הוא [[אריתמטיקה של עוצמות|סכום העוצמות]] <math>\kappa_i</math>, ואילו אגף ימין הוא מכפלת העוצמות <math>\mu_i</math>. האי-שוויון טריוויאלי כאשר העוצמות והקבוצה סופיים, אבל כלל אינו ברור מאליו למקרים אינסופיים. אם למשל תוחלף המכפלה באגף ימין בסכום, עשוי להתקיים שוויון (מה שבוודאי לא נכון במקרה הסופי).

משפט קנטור מתקבל כמקרה פרטי של משפט קניג. אם לכל <math>i \in A</math> בוחרים <math> \kappa_i = 1</math> ו-<math> \mu_i = 2</math>, אז ממשפט קניג נקבל:
:<math>|A| = \sum_{i\in A} 1<\prod_{i\in A} 2 = 2^{|A|}</math>

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

מגדירים את ה[[קופינליות (תורת הקבוצות)|קופינליות]] של עוצמה <math>\kappa</math> בתור העוצמה הקטנה ביותר <math>|I|</math> שמקיימת את התנאי הבא: לכל <math>i \in I</math> קיימת עוצמה <math>\lambda_i < \kappa</math> כך שמתקיים: <math>\kappa = \sum_{i \in I} \lambda_i</math>. מסמנים את הקופינליות של <math>\kappa</math> בסימון <math>\mathrm{cf}(\kappa)</math>. נשים לב שתמיד ניתן לבחור <math>|I| = \kappa</math>, ואז <math>\kappa = \sum_{i \in I} 1</math>. לכן תמיד מתקיים <math>\mathrm{cf}(\kappa) \le \kappa</math>.

ממשפט קניג נובע מיד ש-<math> \kappa < \kappa^{\mathrm{cf}(\kappa)}</math> (בוחרים את <math>A</math> ממשפט קניג להיות <math>I</math> מהגדרת הקופינליות). מהזהות האחרונה נקבל שלכל קבוצה אינסופית <math>A</math> מתקיים <math>|A|<\mathrm{cf}\left(2^{|A|}\right)</math>. ההוכחה נעשית בדרך השלילה:
:נניח בשלילה <math>|A|\ge\mathrm{cf}\left(2^{|A|}\right)</math>. אז לפי הזהות האחרונה נקבל את הסתירה:
:<math>2^{|A|}<\left(2^{|A|}\right)^{cf\left(2^{|A|}\right)}\le\left(2^{|A|}\right)^{|A|}=2^{|A|\cdot|A|}=2^{|A|}</math>

קיבלנו שלקבוצות אינסופיות מתקיים האי-שוויון החזק <math>|A|<\mathrm{cf}\left(2^{|A|}\right)</math>. זהו אי-שוויון חזק יותר מאשר משפט קנטור משום ש-<math>\mathrm{cf}\left(2^{|A|}\right)\le 2^{|A|}</math>, וייתכנו מקרים בהם <math>\mathrm{cf}\left(2^{|A|}\right)<2^{|A|}</math>.

תוצאות אנלוגיות למשפט קנטור מראות אי קיום [[איזומורפיזם]] בין [[מבנה (מתמטיקה)|מבנים]] מסוימים לבין מבנים המורכבים מתת-מבנים שלהם (למשל [[קבוצה סדורה|קבוצות סדורות]]{{הערה|שם=LTR-הכללה1|[http://www.ams.org/journals/proc/1962-013-05/S0002-9939-1962-0144824-3/S0002-9939-1962-0144824-3.pdf A generalized Cantor theorem]|כיוון=שמאל}}{{הערה|שם=LTR-הכללה2|[http://www.ams.org/journals/proc/1971-027-02/S0002-9939-1971-0268091-0/S0002-9939-1971-0268091-0.pdf Complete Lattices and the Generalized Cantor Theorem]|כיוון=שמאל}}). משפט קנטור מתקבל לעיתים כמקרה פרטי של משפטים כאלה, כאשר נבחר מבנה [[טריוויאלי (מתמטיקה)|טריוויאלי]], כך שאוסף התת-מבנים הוא קבוצת החזקה וכל פונקציה חד-חד-ערכית ועל היא איזומורפיזם.

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

ב-[[1891]] פרסם קנטור מאמר ב[[גרמנית]] בשם "''Über eine elementare Frage der Mannigfaltigkeitslehre''" ("על שאלה אלמנטרית בתורת הקבוצות").{{הערה|מילולית, המילה "Mannigfaltigkeitslehre" שבה משתמש קנטור במובן של "תורת הקבוצות" משמעה "תורת ה[[יריעה|יריעות]]". השימוש של קנטור במונח מעיד ככל הנראה על ההשראה ששאב מעבודתו של [[ברנהרד רימן]]. קנטור מתחיל להשתמש במונח "Mengenlehre" שמשמעו "קבוצה" רק ב-[[1895]]. להרחבה ראו ''Labyrinth of thought: a history of set theory and its role in modern mathematics'', עמודים 39 ו-72, {{ISBN|3-7643-8349-6}}.}} במאמר מופיע האלכסון של קנטור, ומיד לאחריו כתב קנטור:{{הערה|שם=LTR-קנטור1|Georg Cantor, "Über eine elementare Frage der Mannigfaltigkeitslehre"{{כ}}, Jahresbericht der Deutschen Math. Vereinigung I, 278-281, 1891}}{{הערה|שם=קנטור2|[http://www.geocities.jp/mickindex/cantor/cnt_uFM_gm.html הקטע הרלוונטי מתוך המאמר]}}
{{ציטוט|תוכן=הוכחה זו מופלאה לא רק בשל פשטותה, אלא במיוחד משום שניתן להרחיב מיד את העקרון שבבסיסה למשפט כללי, שלחזקות של קבוצות [[מוגדר היטב|מוגדרות היטב]] אין מקסימום, או, באופן שקול, שלצד כל קבוצה נתונה L, תמיד ניתן לשים קבוצה אחרת M שעוצמתה גדולה יותר מזו של L.}}

בהמשך המאמר, פונה קנטור להוכחת המשפט. ההוכחה המקורית של קנטור זהה במהותה לנוסח המודרני של ההוכחה, אך היא נוסחה בצורה שונה במעט. במקור קנטור הראה שאין התאמה חד-חד-ערכית ועל בין <math>A</math> לבין קבוצת הפונקציות המציינות של <math>A</math> ([[#נוסח שקול|כאמור]], נוסח זה שקול לנוסח על קבוצת החזקה). קנטור טען שאילו הייתה התאמה כזו, הרי שהייתה קיימת פונקציה דו-מקומית <math>\phi(a,x)</math>, כך שלכל פונקציה מציינת <math>f(x)</math> שהותאם לה האיבר <math>a</math> מתקיים: <math>\phi(a,x) = f(x)</math>. כעת קנטור בונה פונקציה מציינת <math>g(x)</math> שמוגדרת כהיפך מ-<math>\phi(x,x)</math> (ניתן להגדיר כך: <math>g(x) = 1-\phi(x,x)</math>). לפי ההנחה קיים <math>d \in A</math> כך ש-<math>\phi(d,x) = g(x)</math>, ולכן מקבלים סתירה: <math>\phi(d,d) = g(d) \ne \phi(d,d)</math>.{{כ}}{{הערה|שם=LTR-קנטור1}}{{הערה|שם=קנטור2}}

לנוסח המודרני של ההוכחה אחראי [[ארנסט צרמלו]]. משפט קנטור והוכחתו מופיעים במאמר של צרמלו משנת [[1908]] שבו ייסד את [[תורת הקבוצות האקסיומטית]].{{הערה|שם=LTR-צרמלו|E. Zermelo "Untersuchungen über die Grundlagen der Mengenlehre I",{{כ}} [[Mathematische Annalen]] 65 (2), 276,{{כ}} 1908
}}{{הערה|1=[http://dfg-viewer.de/v2/?set%5Bimage%5D=286&set%5Bzoom%5D=default&set%5Bdebug%5D=0&set%5Bdouble%5D=0&set%5Bmets%5D=http%3A%2F%2Fwww.digizeitschriften.de%2Fdms%2Fmetsresolver%2F%3FPPN%3DPPN235181684_0065 הקטע הרלוונטי מתוך המאמר]}} צרמלו הוא גם זה שקרא למשפט על שמו של קנטור.

== ראו גם ==
* [[תורת הקבוצות - מונחים]]
* [[הפרדוקס של קנטור]]

== לקריאה נוספת ==
<div class="mw-content-ltr">
* Nikolai Konstantinovich Vereshchagin, Alexander Shen, '''Basic set theory''', p. 24-30, American Mathematical Soc., 2002, {{ISBN|0-8218-2731-6}}
* Robert Lawson Vaught, '''Set theory: an introduction''', p. 53-54, Springer, 2001, {{ISBN|0-8176-4256-0}}
</div>

== קישורים חיצוניים ==
{{ויקישיתוף בשורה}}
* {{לא מדויק|2010/11/20/russel_paradox_and_cantor_theorem/|הפרדוקס של ראסל ומשפט קנטור}}
* Arindama Singh, [https://www.ias.ac.in/article/fulltext/reso/009/08/0008-0017 Cantor's Little Theorem]
* {{MathWorld}}
* {{בריטניקה}}

== הערות שוליים ==
{{הערות שוליים|יישור=ימין}}


{{ערך מומלץ}}

[[קטגוריה:משפטים בתורת הקבוצות|קנטור]]
[[קטגוריה:אי-שוויונות|קנטור]]
[[קטגוריה:אינסוף]]
[[קטגוריה:הוכחות]]