משפט קנטור

מושגים

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

פונקציות

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

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

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

נוסח המשפט

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

הוכחת המשפט

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

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

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

נוסח שקול

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

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

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

שימושים

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

בעיות הכרעה

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

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

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

היסטוריה

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