אין סוף למוזרות: על המלון המטורף של הילברט
מושג האינסוף מדיר שינה מעיני המתמטיקאים. התובנה המדהימה שיש סוגים שונים של אינסוף, לא מוסיפה להם נחת
כשמבקשים ממני לתת דוגמאות לתוצאות מעניינות ועם זאת פשוטות במתמטיקה, הדוגמה הראשונה שאני תמיד חושב עליה היא התגלית של גאורג קנטור, לפיה קיימים אינסוף גדלים שונים של "אינסוף". לא צריך כמעט כלל ידע במתמטיקה בשביל להבין אותה, ואני חושב שהיא נותנת מושג טוב למדי לגבי האופן שבו המתמטיקה עושה סדר במושג שנראה מסובך במבט ראשון.
מהו אינסוף? יש תשובות רבות לשאלה הזאת ולכן אדבר רק על המושג שבו אעסוק כאן, של אינסוף בתור כמות. אנחנו נוהגים להשתמש במספרים טבעיים כדי למנות כמויות - אחד אלוהינו, שני לוחות הברית, שלושה אבות, ארבע אמהות... אלו שימושים של המספרים 1,2,3,4.
באופן יותר מתמטי, אפשר להגיד שאלו גדלים של קבוצות (לצורך העניין "קבוצה" היא כל אוסף של איברים ששונים זה מזה). קבוצת ה"אמהות", למשל, היא מגודל 4. קבוצת "מדינות ארצות הברית" היא מגודל 50 (כרגע). קבוצת המספרים הזוגיים שקטנים או שווים ל-10 היא מגודל 5: המספרים הם 2,4,6,8,10. ומה עם "קבוצת המספרים הזוגיים" באופן כללי? מה הגודל שלה? התשובה היא "אינסוף". וכמה מספרים טבעיים יש בכלל? אינסוף.
אני אוהב להמשיל את האינסוף הזה ל"כמה שתרצו". נניח שיש לנו מכולה עם 1,000 עגבניות. אם אנשים יבואו ויקחו עגבניות באופן חופשי, מהר מאוד לא ישאר כלום: אחרי ש-1,000 איש ייקחו כל אחד עגבניה אחת, המכולה תתרוקן. אם, לעומת זאת, במכולה היו אינסוף עגבניות, אז לא משנה כמה עגבניות היו לוקחים ממנה, היא לא הייתה מתרוקנת, וכמות העגבניות שבתוכה הייתה נותרת אינסוף.
דרך אחרת לחשוב על כך היא זו: אנחנו יכולים למספר עגבניות במכולה במספרים, ומובטח לנו שלכל מספר טבעי אפשרי, תהיה במכולה עגבניה שזהו המספר שלה, בין אם זו עגבניה מס' 2 או עגבניה מספר 942,526,216,591,402,426.
המלון של הילברט
המתמטיקאי דויד הילברט אהב להמחיש את העניין המוזר הזה עם סיפור על מלון בעל אינסוף חדרים - חדר מס' 1, חדר מס' 2, וכן הלאה. למרות אינסוף חדריו, המלון היה הצלחה מסחררת ובתפוסה מלאה, אבל אז בא אורח עיקש ורצה להשתכן בחדר.
מנהל המלון מצא פתרון פשוט: הוא ביקש בנימוס מהאורח בחדר 1 לעבור לחדר 2. מהאורח בחדר 2 הוא ביקש לעבור לחדר 3, וכן הלאה. בצורה הזו התפנה מקום חדש בחדר 1, ואף אחד מהאורחים הקיימים לא נותר ללא חדר (אם כי כולם נאלצו לעבור...). המוזרות הזו - הרי זה תעלול שאי אפשר לעשות במלון עם מספר סופי של חדרים - היא מהתכונות המאפיינות של האינסוף.
הילברט ממשיך בסיפור ומספר על תופעות יותר מוזרות. למשל, פתאום בא אוטובוס וממנו יורדים אינסוף אורחים - אורח מס' 1, אורח מס' 2 וכן הלאה, וכולם רוצים חדר במלון. מה יעשה בעל המלון עכשיו? יתחכם מעט יותר.
מהאורח בחדר 1 הוא יבקש כמקודם לעבור לחדר 2; מהאורח בחדר 2 הוא יבקש לעבור לחדר 4; מהאורח בחדר 3 לחדר 6. באופן כללי, הוא מבקש מכל אורח לעבור לחדר שמספרו כפול ממספר חדרו הנוכחי. כעת מה קרה? כל האורחים עברו לחדרים הזוגיים במספר ולכן התפנו אינסוף חדרים - כל החדרים האי-זוגיים. וכעת אפשר לשכן בהם את כל אינסוף האורחים החדשים.
ועכשיו העלילה מסתבכת עוד יותר - פתאום באים אינסוף אוטובוסים, הממוספרים ב-1,2,3 וכן הלאה; ומכל אוטובוס יורדים אינסוף אנשים - "אורח מס' 1 מאוטובוס מס' 1" וכדומה. ומה יעשה בעל המלון המסכן כעת?
בעל המלון כלל אינו מתרגש, מכיוון שהוא יודע תעלול מתמטי נחמד (מי שלא יבין אותו - לא נורא, אפשר לדלג). מספר הוא ראשוני אם הוא מתחלק רק ב-1 ובעצמו. למשל, 2 הוא ראשוני, וכך גם 3,5,7,11 אבל לא 9, למשל, כי 9 מתחלק ב-3. התכונה של ראשוניים שרלוונטית לנו כאן היא שחזקות של שני מספרים ראשוניים הן תמיד שונות זו מזו (זה נובע מתוצאה במתמטיקה לפיה לכל מספר טבעי קיים פירוק יחיד למכפלה של ראשוניים).
מה שבעל המלון עושה הוא פשוט - ראשית, הוא מבקש מכל האורחים שכרגע במלון לעבור לחדר שגדול פי 2 ממספר החדר שלהם, כמקודם. כעת כל החדרים האי זוגיים התפנו.
לאחר מכן, את האורחים של אוטובוס מס' 1 הוא משכן בכל החדרים שמספרם הוא חזקה של 3: את אורח מס' 1 מאוטובוס זה, בחדר מס' 3; את אורח מס' 2 בחדר מס' 9 (שהוא 3 בריבוע); את אורח מס' 3 בחדר מס' 27 (שהוא 3 בשלישית), וכן הלאה. מכיוון שחזקה של מספר אי זוגי היא אי זוגית בעצמה, מובטח לנו שאף אורח מאוטובוס מס' 1 לא יפלוש לחדר של אחד מהאורחים הקיימים במלון.
כעת, את אנשי אוטובוס מס' 2 הוא משכן בחדרים שהם חזקות של 5: 5,25,125 וכן הלאה. ואת אנשי אוטובוס 3 בחדרים שהם חזקות של 7. העקרון הכללי ברור – כל אוטובוס מקבל מספר ראשוני משל עצמו ומשכן את אנשיו בחדרים שהם חזקות של אותו מספר ראשוני. יש משפט ידוע שמראה כי קיימים אינסוף ראשוניים שכולם (פרט ל-2) הם אי זוגיים, כך שלכל אוטובוס אכן אפשר לחלק ראשוני משלו.
אינסופים
בעל המלון הוא רב תושייה ושולט היטב במתמטיקה, וזה מוביל אותנו באופן טבעי לשאלה פשוטה - האם יש אתגר שאיתו לא יוכל להתמודד? האם ייתכן שיגיעו "יותר מדי" אורחים ובעל המלון יצטרך לוותר? התשובה היא שכן, ושכמות האורחים הזו היא בדיוק אינסוף "גדול יותר" מאשר אינסוף החדרים שיש במלון. זה מביא אותנו לשאלה נוספת, מרכזית: איך מודדים "גודל" של קבוצות אינסופיות?
כשמדובר על קבוצה סופית יש דרך פשוטה למדוד את הגודל שלה - פשוט סופרים, איבר אחרי איבר, כמה יש. כשמדובר על קבוצות אינסופיות לא ניתן לעשות זאת כי הספירה לא תיגמר לעולם. לכן משתמשים בקריטריון "השוואתי": מנסים להגיד כמה איברים יש בקבוצה האינסופית ביחס לקבוצות אינסופיות אחרות.
כדי להבין את העניין כדאי לראות דוגמה עבור קבוצות סופיות: נניח שיש לנו אצטדיון בעל 10,000 מקומות ישיבה, הוא מלא באנשים, ואנו רוצים לדעת בערך כמה יש. אפשר לבקש מכל האנשים לשבת ולראות מה קורה - אם נותרו מקומות ישיבה פנויים אז יש פחות מ-10,000 אנשים באצטדיון; אם נותרו אנשים עומדים, יש יותר מ-10,000 אנשים באצטדיון; ואם לא קרה לא זה ולא זה, אנחנו יודעים שיש בדיוק 10,000 אנשים באצטדיון.
מה שביצענו כאן הוא התאמה בין האנשים ובין המושבים באצטדיון. כדי שההתאמה תראה שוויון בגודל של קבוצות, היא צריכה לקיים שתי תכונות: ראשית, שלכל אדם יהיה מושב שהוא שלו בלבד ושהוא לא חולק אותו עם אחרים; ושנית, שלא יהיו מושבים פנויים.
גם בדוגמת המלון ביצענו התאמה - התאמה בין "קבוצת האורחים של המלון" ובין "קבוצת החדרים של המלון". במקרה שלנו, "קבוצת החדרים של המלון" הייתה פשוט קבוצת המספרים הטבעיים. לקבוצה שאפשר להתאים אותה למספרים הטבעיים - "לשכן במלון של הילברט" - קוראים "קבוצה בת מניה" (כי ניתן למנות את איבריה - לדבר על "איבר מס' 1, איבר מס' 2..." וכן הלאה).
מה שראינו בכל סיפור המלון עד כה הוא שגם קבוצות שנראות גדולות יותר מהמספרים הטבעיים הן עדיין בנות מניה ולא באמת גדולות יותר מקבוצת הטבעיים. גם כשמוסיפים איבר אחד לקבוצה, או אינסוף (בן-מניה) של איברים לקבוצה, או אפילו אינסוף כפול אינסוף איברים – עדיין מקבלים קבוצה בת מניה.
בעזרת רעיונות דומים אפשר להראות שקבוצת המספרים הרציונליים (שברים) היא בת מניה, כלומר, "כמות" המספרים הרציונליים זהה לכמות הטבעיים, וזאת למרות שנראה שאמורים היו להיות הרבה יותר רציונליים.
אפשר לפטור את הדיון למעלה בטענה ש"כל שתי קבוצות אינסופיות הן מאותו גודל" וחסל, אבל התגלית הגדולה של קנטור הייתה שזה לא כך. אציג כעת את ההוכחה שלו – "האלכסון של קנטור", בעזרת סיפור המלון (בדרך כלל מראים אותה על מספרים ממשיים אבל אין שום יתרון שצומח מכך, לדעתי). מה שאני רוצה להראות היא קבוצת אורחים שגדולה מכדי להיות בת מניה; שלא משנה איך ננסה לשכן אותה במלון של הילברט, תמיד יישאר אורח בלי חדר.
עוד ועוד אורחים, עוד ועוד חדרים
למרבה המזל, די קל לתאר את קבוצת האורחים הזו, ואני הולך לעשות זאת בעזרת מספרי הזהות שלהם. מספר הזהות בישראל הוא בן 9 ספרות, אבל אין בעיה לדבר גם על מספר זהות בן 10 ספרות, או 11, או 12. מכיוון שכל אלו לא יאתגרו את המלון של הילברט, אני אציע רעיון מוזר: לכל אחד מהאורחים בקבוצה שאבנה יהיה מספר זהות בן אינסוף (בן מניה) של ספרות.
בואו נניח שלכל סדרה אינסופית של ספרות יש אורח שמעוניין להשתכן במלון של הילברט. אני טוען שלא משנה מה בעל המלון יעשה כעת, יהיה אורח שנשאר בחוץ. איך נראה דבר כזה? נניח בשלילה שכל האורחים שוכנו איכשהו במלון, ואז נבנה באופן הדרגתי את מספר הזהות של מישהו שבטוח - במאה אחוזים - לא שוכן במלון.
אז בואו נניח שכל האורחים שוכנו במלון. אני הולך לחדר מס' 1, דופק בדלת, ושואל את האורח שבפנים "סליחה, מה הספרה הראשונה בתעודת הזהות שלך?". הוא אומר לי, נניח, "7", אז אני רושם לעצמי על דף נייר "8" וצוחק צחוק מרושע.
אז אני הולך לחדר 2 ושואל את האורח שבפנים מה הספרה השנייה בתעודת הזהות שלו. הוא אומר לי, נניח, ש-3, ואז אני כותב בדף שלי את הספרה 4 וצוחק צחוק מרושע. כעת כתוב לי בדף 84.
הלאה - חדר 3, האורח אומר לי שהספרה השלישית בתעודת הזהות שלו היא 9, ואני כותב לי 0 בדף וצוחק צחוק מרושע. כעת כתוב לי בדף 840.
בשלב הזה עוצרים אותי אנשים עם חלוקים לבנים ורשתות ושואלים אותי מה אני עושה. אני מסביר להם בנימוס שאני בונה, לאט לאט, מספר זהות של אורח שבודאות לא משוכן במלון.
הנה למשל, כל מספר זהות שמתחיל ב-840 הוא בודאות לא מספר הזהות של אורח ששוכן בחדרים מס' 1, 2 או 3; כי לאורח בחדר מס' 1 ספרת הזיהוי הראשונה היא 7, ואילו במספר הזהות שאני בונה הספרה הראשונה היא 8; ועבור השני, ספרת הזהות השנייה שלו היא 3, אבל אצלי ספרת הזהות השנייה היא 4; וכן הלאה וכן הלאה.
באופן כללי, את האורח מס' n אני אשאל על ספרת הזהות ה-n-ית שלו, וכך עם כל אורח חדש אני מוסיף ספרה אחת למספר הזהות ואף פעם לא נקלע לקשיים בסגנון "כבר החלטתי מה תהיה הספרה הראשונה בתעודת הזהות אבל על סמך מה שהאורח הנוכחי אמר לי אני חייב לשנות אותה", כי, כאמור, אני בכל פעם מתעסק בספרה אחרת.
תהליך התשאול הזה מניב סדרה אינסופית של ספרות - כלומר, מספר זהות של מישהו. אותו מישהו, כאמור, לא יכול להיות משוכן באף חדר במלון - כי לכל n, מספר הזהות שלו לא מתאים למספר הזהות של האורח שבחדר n כי הספרה ה-n-ית במספרי הזהות שלהם שונה. זה הסוף.
ייתכן שחלקכם מרגישים שיש בעיות בהוכחה הזו – למשל, האם יש משמעות ל"הליך תשאול" שהוא אינסופי?. בהוכחה של קנטור אין צורך אמיתי בכך – אני מציג את הדברים בצורה הזו כי כך יותר קל להמחיש את הרעיון שבהוכחה. אני יכול לתאר את כל מה שעשיתי כאן בצורה יותר מתמטית-פורמלית, אבל המוזרות לא תשתנה: המלון של הילברט מופרע יותר מכפי שהיה נדמה במבט ראשון. יש, במובן קונקרטי מאוד ומוחשי, סוגים שונים של אינסוף.
גדי אלכסנדרוביץ' הוא בעל תואר שלישי במדעי המחשב ומחבר הבלוג "לא מדויק".
לפנייה לכתב/ת 
