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

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

אני כן מניח שיש לכם היכרות כלשהי עם תורת הקבוצות, ברמה שתאפשר לכם להבין מה אומר משפט קנטור-שרדר-ברנשטיין: הוא אומר שאם \( 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 \), ולכן המקרה הזה לא יכול להתרחש כלל. זה מסיים את ההוכחה.

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