הגודל כן קובע

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

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

הרעיון של קנטור הוא למעשה פשוט למדי, ואמחיש אותו באמצעות דוגמה מקובלת. נניח שישנו אצטדיון כדורגל בן 30,000 מושבים, והוא מלא באנשים. אני רוצה לדעת האם תפוסת האצטדיון מלאה - כלומר, האם הוא מכיל 30,000 אנשים. דרך אחת לעשות זאת היא להשתמש בשיטת הספירה שתיארתי בפוסט הקודם - לעבור אדם אדם, להוריד אותו מקבוצת “האנשים שטרם נספרו” ולהגדיל את המונה ב-1. זו שיטה איטית ומסורבלת להחריד.

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

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

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

כשאני אומר “על” הכוונה היא שכל איבר ב-B מותאם לאיבר כלשהו ב-A. כלומר - שכל כיסא באצטדיון נבחר על ידי אדם אחד לפחות.

זה תרגיל לא מסובך במיוחד להראות שאם קיימת פונקציה חח”ע מ-A אל B, אז קיימת פונקציה על מ-B אל A, ושאם יש פונקציה על מ-A אל B, אז קיימת פונקציה חח”ע מ-B אל A. נסו להוכיח זאת! (יש להשתמש הן בתכונה שמתקיימת - חח”ע או על - והן בתכונות המגדירות פונקציה). מכאן עולה שאפשר לדבר על “התאמה חח”ע ועל בין שתי קבוצות, בלי לציין מאיפה לאיפה. עוד תוצאה חשובה, הרבה פחות פשוטה להוכחה באופן כללי, היא שאם יש פונקציה חח”ע מ-A אל B, ופונקציה חח”ע מ-B אל A, אז קיימת התאמה חח”ע ועל בין A ו-B. התוצאה הזו מכונה משפט קנטור-שרדר-ברנשטיין. אם קיימת התאמה חח”ע ועל בין שתי קבוצות (במקרה כזה אומרים שהן שקולות), אז אפשר לסדר את האיברים שלהן זוגות זוגות, כשבכל זוג יש איבר אחד מ-A ואיבר אחד מ-B. בבירור הדבר גורר ששתי הקבוצות הן מאותו הגודל כאשר הן סופיות; אנו בוחרים להגדיר כך שוויון עוצמות בין קבוצות אינסופיות. כאן נפרד מושג ה”עוצמה” ממושג ה”גודל” האינטואיטיבי; אתם כקוראים אינכם חייבים לקבל את ההגדרה שלי בתור “גודל”. מה שלא תוכלו לעשות, גם אם אינכם מקבלים את ההגדרה, הוא להתעלם מתוצאותיה המתמטיות - למשל, שיש מספרים ממשיים שאף תוכנת מחשב בשפת ++C לא תוכל לחשב.

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

לכל מספר טבעי אפשר להתאים את הריבוע שלו (ל-1 מתאימים את 1, ל-2 מתאימים את 4, ל-3 את 9 וכן הלאה). ההתאמה הזו היא בבירור פונקציה, היא בבירור חד חד ערכית (כי לשני מספרים טבעיים שונים יש ריבועים שונים) והיא גם בבירור על קבוצת המספרים שיש להם שורש שלם (1,4,9,16,25 וכן הלאה). אם כן, מההגדרה של קנטור עולה שעוצמת קבוצת המספרים הטבעיים זהה לעוצמת קבוצת הריבועים.

אבל זה נראה מופרך; הרי הקבוצה של כל הריבועים היא קבוצה חלקית לקבוצת כל המספרים הטבעיים, ובפרט קיימים מספרים טבעיים רבים שאינם ריבועים! (2, 3, 5, 6, 7, 8, 10, וכן הלאה). ואכן, ה”פרדוקס” הזה הוא פשוט התוצאה הלא אינטואיטיבית והבלתי נמנעת של השימוש בעוצמות. למעשה, אחת מההגדרות המקובלות ל”קבוצה אינסופית” היא “קבוצה ששקולה לתת קבוצה ממש של עצמה” (ה”ממש” פירושו כאן “לא שווה”, שכן מבחינה פורמלית קבוצה היא תמיד גם תת קבוצה של עצמה, וגם קבוצות סופיות שקולות לעצמן, כמובן).

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

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

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

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

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

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

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