משפט קנטור-שרדר-ברנשטיין – ועכשיו בגרסת המלון של הילברט!

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

אני כן מניח שיש לכם היכרות כלשהי עם תורת הקבוצות, ברמה שתאפשר לכם להבין מה אומר משפט קנטור-שרדר-ברנשטיין: הוא אומר שאם \(A,B\) הן קבוצות כך שקיימות פונקציות חד-חד-ערכיות \(f:A\to B\) וגם \(g:B\to A\) אז קיימת פונקציה חד-חד-ערכית ועל \(h:A\to B\). בניסוח ציורי, זה אומר שאם \(\left|A\right|\le\left|B\right|\) וגם \(\left|B\right|\le\left|A\right|\) אז \(\left|A\right|=\left|B\right|\). אבל המשפט עושה קצת יותר מכך – הבנייה של \(h\) היא קונסטרוקטיבית לגמרי: אני יכול לתת תיאור מפורש של \(h\) שמתבסס על \(f,g\); אני לא סתם מוכיח ש"קיימת \(h\) כלשהי שעובדת" (אני קצת מרמה כאן – למילה "קונסטרוקטיבית" במתמטיקה יש גם משמעות יותר מוגבלת, ובמשמעות הזו ההוכחה לא קונסטרוקטיבית; אבל זה דיון אחר שאולי נקיים בעתיד).

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

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

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

ועכשיו אפשר לספר את סיפור המלון כך: בהתחלה המלון כולו מלא, על ידי שיטת המילוי שהפונקציה \(g\) מתארת. זה אומר שאפשר לחלק את קבוצת האנשים \(A\) לשתי קבוצות: "ברי המזל" שיש להם חדר, ו"הממורמרים" שאין להם חדר. מבחינה מתמטית, קבוצת ברי המזל היא בדיוק \(g\left(B\right)\triangleq\left\{ g\left(b\right)\ |\ b\in B\right\} \). את קבוצת "הממורמרים" אני אסמן בתור \(D_{0}\triangleq A/g\left(B\right)\), כשהאפס שנמצא פה אמור לרמוז לכם שעוד יהיו המון ממורמרים נוספים בהמשך. כי ככה זה – אנחנו חיים במציאות דיסטופית שבה בועטים אנשים מחדרי המלון שלהם.

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

השאלה שנשאלת כעת היא איך מחליטים עבור כל אדם ב-\(D_{0}\) לאיזה חדר ללכת. התשובה היא שהפונקציה \(f\) באה כאן לעזרתנו. הפונקציה \(f\) יודעת לשכן את כל האנשים בקבוצה \(A\) בלי התנגשויות; ברור שהיא יודעת בפרט לשכן את כל האנשים ב-\(D_{0}\) ללא התנגשויות. אם כן, קבוצת החדרים שאנשי \(D_{0}\) יתפסו היא הקבוצה \(f\left(D_{0}\right)\). כעת נשאלת השאלה – מהי קבוצת האנשים שייבעטו החוצה? כל האנשים הללו שייכים לקבוצת "ברי המזל" שהיו במלון כשהמשחק התחיל – ולכן, בהינתן חדר, כדי לגלות את בר המזל שהתגורר בו אני מפעיל את \(g\) על החדר. מכאן ש-\(g\left(f\left(D_{0}\right)\right)\) היא הקבוצה המתאימה – "קבוצת כל האנשים שהתגוררו בחדרים שאנשי \(D_{0}\) תפסו". לכן אני מגדיר \(D_{1}\triangleq g\left(f\left(D_{0}\right)\right)\).

עבור \(D_{2}\) העיקרון דומה. מה שכדאי לשים אליו לב הוא שכל החדרים ב-\(f\left(D_{1}\right)\) הם חדרים שבהם גרים "ברי מזל". לא ייתכן שמישהו מ-\(D_{1}\) יקבל הקצאה של חדר ששייך כרגע למישהו מ-\(D_{0}\), מכיוון שגם אנשי \(D_{1}\) וגם אנשי \(D_{0}\) משוכנים באמצעות הפונקציה \(f\) שמונעת התנגשויות. לכן \(g\left(f\left(D_{1}\right)\right)\) נותנת לנו את קבוצת "ברי המזל" שפונו מחדרם על מנת לפנות מקום לאנשי \(D_{1}\), ונסמן \(D_{2}\triangleq g\left(f\left(D_{1}\right)\right)\).

המשחק נמשך באופן הזה ואני מגדיר \(D_{n+1}\triangleq g\left(f\left(D_{n}\right)\right)\). כך לאט לאט אנחנו נוגסים עוד ועוד מקבוצת "ברי המזל" והופכים אותם לממורמרים. עכשיו אני יכול לדבר על קבוצת הממורמרים המלאה: \(D=\bigcup_{n=0}^{\infty}D_{n}\). אנחנו יודעים שכל מי ששייך ל-\(D\) שוכן בחדר שלו באמצעות \(f\), וכל מי שלא שייך ל-\(D\) שוכן בחדר שלו באמצעות \(g\). צריך להיות טיפה זהירים בעניין הסימונים כאן: אם \(a\in A\) מקיים ש-\(a\notin D\) אז החדר של \(a\) לא נתון באמצעות \(g\left(a\right)\) – זה ביטוי חסר משמעות, כי התחום של \(g\) הוא \(B\) ולא \(A\). אפשר לומר את הדבר הבא: מכיוון ש-\(g\) היא חד-חד-ערכית ועל ומכיוון שהיא כמובן על התמונה שלה, \(g\left(B\right)\), קיימת לה פונקציה הופכית \(g^{-1}:g\left(B\right)\to B\). כעת, מכיוון ש-\(D_{0}=A\backslash g\left(B\right)\), ברור שאם \(a\notin D\) הרי ש-\(a\in g\left(B\right)\) ולכן \(g^{-1}\) מוגדרת עליו. לכן אפשר לתת את ההגדרה הבאה של \(h\):

\(h\left(a\right)=\begin{cases}f\left(a\right) & a\in D\\g^{-1}\left(a\right) & a\notin D\end{cases}\)

כל שנותר להסביר הוא למה \(h\) היא חד-חד-ערכית ועל.

האינטואיציה לגבי מדוע \(h\) על היא קלה: כל חדר במלון היה תפוס בהתחלה, כשהשתמשנו בשיטה \(g\). אחר כך, אם פינינו אורח מחדר במלון, זה היה רק כדי להכניס לשם מישהו במקומו, אז ברור שכל החדרים במלון יהיו תפוסים גם בשיטה ש-\(h\) מתאר. פורמלית נוכיח זאת כך: יהא \(b\in B\). המועמד הטבעי להיות האיש שבחדר \(b\) הוא פשוט מי שהיה בו בהתחלה, שזה \(a=g\left(b\right)\). לכן אנחנו צריכים לבדוק מה עלה בגורלו של \(a\). ייתכן ש-\(a\) היה בר מזל ואף אחד לא פינה אותו מחדרו בשום שלב, כלומר \(a\notin D\); במקרה זה, \(h\left(a\right)=g^{-1}\left(a\right)=b\) והנה, מצאנו איבר שנותן את \(b\). אבל ייתכן גם ש-\(a\) פונה מחדרו, כלומר \(a\in D\). שימו לב לניואנס כאן: \(a\) פונה מחדרו; זה לא שלא היה לו חדר מלכתחילה. פורמלית זה אומר ש-\(a\notin D_{0}\) (וזה ברור, כי \(a\in g\left(B\right)\) אבל \(D_{0}=A\backslash g\left(B\right)\)) ומכאן שאם \(a\in D\) בהכרח \(a\in D_{n}\) כך ש-\(n\ge1\). למה הניואנס הזה חשוב? כי אם \(a\) פונה מחדרו, זה אומר שהוא פונה כדי שמישהו אחר ייכנס. המישהו האחר הזה יהיה מי שתופס את החדר בסופו של דבר. איך נגלה מי זה? נשתמש בהגדרה של \(D_{n}\): אנחנו יודעים ש-\(D_{n}=g\left(f\left(D_{n-1}\right)\right)\) (זה נכון לכל \(n\ge1\)) ולכן אם \(a\in D_{n}\) קיים \(a^{\prime}\in D_{n-1}\) כך ש-\(a=g\left(f\left(a^{\prime}\right)\right)\). נפעיל את \(g^{-1}\) על שני האגפים ונקבל \(b=g^{-1}\left(a\right)=f\left(a^{\prime}\right)=h\left(a^{\prime}\right)\) – קיבלנו גם במקרה הזה איבר שנותן את \(b\). זה מסיים את ההוכחה שהפונקציה היא על.

המשמעות של הוכחה ש-\(h\) חד-חד-ערכית היא שבשיטה הסופית שלנו אין שני אנשים ששוכנו באותו החדר. ניקח שני אנשים \(a_{1},a_{2}\) שכאלו. יש שלוש אפשרויות: או ששניהם "ממורמרים" שלא היה להם חדר בהתחלה או שנבעטו מתישהו מהחדר שלהם; או ששניהם "ברי מזל" שהיה להם חדר מההתחלה והם לא נבעטו ממנו; או שאחד הוא ממורמר והשני בר מזל.

במקרה הראשון, שני הממורמרים שוכנו בחדר שלהם בסופו של דבר בעזרת \(f\) שמבטיחה שלא יהיו התנגשויות. פורמלית, אם \(a_{1},a_{2}\in D\) אז \(h\left(a_{1}\right)=f\left(a_{1}\right)\) ו-\(h\left(a_{2}\right)=f\left(a_{2}\right)\), ולכן אם \(h\left(a_{1}\right)=h\left(a_{2}\right)\) נובע מכך ש-\(f\left(a_{1}\right)=f\left(a_{2}\right)\) ומכיוון ש-\(f\) חד-חד-ערכית נובע מכך ש-\(a_{1}=a_{2}\) מה שמסיים את המקרה הזה.

המקרה השני, של שני ברי מזל, דומה: הרי ההתאמה לחדרים ש-\(g\) מגדירה גם כן לא מאפשרת התנגשויות. אם \(a_{1},a_{2}\notin D\) אז אם \(h\left(a_{1}\right)=h\left(a_{2}\right)\) נקבל ש-\(g^{-1}\left(a_{1}\right)=g^{-1}\left(a_{2}\right)\) ועל ידי הפעלת \(g\) על שני האגפים נקבל \(a_{1}=a_{2}\).

במקרה השלישי אפשר להניח בלי הגבלת הכלליות ש-\(a_{1}\in D\) ו-\(a_{2}\notin D\). מה קורה פה, אינטואיטיבית? \(a_{2}\) הוא "בר מזל", כלומר הוא לא פונה אף פעם מהחדר שלו; לעומתו, \(a_{1}\) הוא "ממורמר", וכדי לשכן אותו היה צריך להעיף מישהו אחר מהחדר שלו. לכן לא ייתכן ש-\(a_{1}\) יחלוק חדר עם מישהו שלא היה צריך להעיף מעולם. פורמלית, אם \(h\left(a_{1}\right)=h\left(a_{2}\right)\) אז \(f\left(a_{1}\right)=g^{-1}\left(a_{2}\right)\); נפעיל את \(g\) על שני האגפים ונקבל \(a_{2}=g\left(f\left(a_{1}\right)\right)\), שאומר "\(a_{2}\) נבעט מהחדר שלו כדי לפנות מקום ל-\(a_{1}\)". כי אם \(a_{1}\in D\) זה אומר שקיים \(n\) כך ש-\(a_{1}\in D_{n}\), ואז על פי הגדרה \(a_{2}\in g\left(f\left(D_{n}\right)\right)=D_{n+1}\), בסתירה להנחה ש-\(a_{2}\notin D\), ולכן המקרה הזה לא יכול להתרחש כלל. זה מסיים את ההוכחה.

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

16 תגובות על הפוסט “משפט קנטור-שרדר-ברנשטיין – ועכשיו בגרסת המלון של הילברט!

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

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

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

  4. הסבר מעולה! אני מלמד מתמטיקה דיסקרטית, ואני אפנה את הסטודנטים שלי לפוסט הזה.

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

  6. אני חושב שהמקום שמציג את ההוכחה הכי בפשטות ובאלגנטיות הוא הספר הזה בעמוד 29: https://www.google.co.il/url?sa=t&source=web&rct=j&url=http://susanka.org/HSforQM/%5BSimmons%5D_Introduction_to_Topology_and_Modern_Analysis.pdf&ved=0ahUKEwjOi-v19dzQAhWEC5oKHUjgBMoQFggYMAA&usg=AFQjCNHQ6BId5MTssy6_h2eTrSm_4Zj3nw&sig2=TJ4aERNv4HdnbcmD1NPvig. מאוד ממליץ להעיף מבט..

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

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

  9. יריב, לא: ב-D_0 יש רק את האנשים שמלכתחילה לא היה להם חדר. מי שלא פונה מחדרו לא שייך ל-D_0.

  10. לקורא שביקש דיאגרמות – אתה צודק. לו רק היה מישהו שיכול לצייר בשבילי דיאגרמות סבירות ללא תשלום!

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

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

  12. יפה מאד, אהבתי. תודה רבה.

    תיקון קל – בפסקה לפני ההגדרה של h כתבת: "מכיוון ש-g היא חד-חד-ערכית ועל ומכיוון…". g היא כמובן לא בהכרח על, אלא רק ביחס לתמונה שלה, כפי שאתה כותב כמה מילים לאחר מכן.

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

    שוב תודה!

  13. איזה מגניב שאתה מכיר את סימונס! D:
    מה אתה חושב עליו בהשוואה לספרים כמו רודין וכ"ו? (בסוף קניתי את סימונס אגב)

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

כתיבת תגובה

האימייל לא יוצג באתר.