משפט קנטור-שרדר-ברנשטיין

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

ראשית, רקע קצר (אם כי הפוסט הזה כן מיועד רק למי שכבר מכירים את הרקע): הכלי המתמטי שבו אנו משתמשים כדי להשוות בין הגדלים של שתי קבוצות - סופיות או אינסופיות, הוא פונקציות חד-חד-ערכיות ועל. \( f:A\to B \) היא חד-חד-ערכית (חח”ע) אם \( f\left(x\right)=f\left(y\right) \) גורר ש-\( x=y \) (“שני איברים שונים של \( A \) לא מועברים לאותו איבר ב-\( B \)”) ו-\( f:A\to B \) היא על אם לכל \( b\in B \) קיים \( a\in A \) כך ש-\( f\left(a\right)=b \) (“כל איבר של \( B \) הוא תמונה של איבר כלשהו ב-\( A \)”).

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

וחוץ מזה, עבור קבוצות סופיות זה עובד.

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

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

אנחנו רוצים לבנות את \( h \) וכלי הנשק שלנו הם \( f \) ו-\( g \). אולי הכי מתבקש להגדיר \( h\left(a\right)=f\left(a\right) \) לכל \( a\in A \) אבל זה חסר טעם לגמרי - \( h \) לא תהיה בהכרח על \( B \), ולא עשינו כלום. נסיון א’ כשל.

מצד שני, אפשר לעשות את ההתחכמות הבאה: \( g\left(B\right)=\left\{ g\left(b\right)|b\in B\right\} \) היא תת-קבוצה של \( A \) (כל האיברים ש”נתפסים” על ידי \( B \)). אם \( a\in g\left(B\right) \) זה אומר שיש \( b\in B \) יחיד (כי \( g \) חח”ע) כך ש-\( g\left(b\right)=a \); אפשר להגדיר אם כן פונקציה הפוכה, \( g^{-1}:g\left(B\right)\to B \) כך ש-\( g^{-1}\left(a\right)=b \). הפונקציה הזו, למרבה השמחה, היא על - כל איבר של \( B \) נתפס על ידה (למה?). בנוסף, היא גם חח”ע, כי אם \( g^{-1}\left(a_{1}\right)=g^{-1}\left(a_{2}\right)=b \) זה אומר ש-\( g\left(b\right)=a_{1} \) וגם \( g\left(b\right)=a_{2} \), כלומר \( a_{1}=a_{2} \). הרי לנו פונקציה חח”ע ועל. האם סיימנו? ודאי שלא, כי \( g^{-1} \) לא הוגדרה לכל איבר של \( A \). אנחנו חייבים להגדיר את \( h \) המיועדת שלנו לכל אברי \( A \).

אם כן, בואו נסמן \( C_{0}=A\backslash g\left(B\right)=\left\{ a\in A|a\notin g\left(B\right)\right\} \) (ה-0 בא לרמז שעוד מעט נגדיר עוד קבוצות כאלו) . זו קבוצת כל ה”דחויים” - כל אלו שלא נבחרו על ידי איבר מ-\( B \) באמצעות \( g \). מה אפשר לעשות איתם? ובכן, פשוט להפעיל עליהם את \( f \). במילים אחרות, הבה וננסה את ההגדרה הבאה:

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

הפונקציה \( h \) היא חוקית לגמרי, והיא בוודאי על \( B \) בגלל שתמונת כל האיברים \( a\notin C_{0} \) לבדם מכסה את \( B \), אבל כאן גם נעוצה הבעיה: היא לא חח”ע. ייתכן שיש התנגשות ו-\( h \) מעבירה לאותו איבר ב-\( B \) גם איבר של \( C_{0} \) וגם איבר שאינו ב-\( C_{0} \). אז מה עושים? פשוט מאוד: איברים שאינם ב-\( C_{0} \) ומתנגשים עם תמונה של איברים מ-\( C_{0} \) - נפעיל עליהם את \( f \). החח”ע של \( f \) תבטיח שהתמונה של אותם איברים לא תתנגש יותר עם כלום.

מכיוון שלהגיד “איברים שאינם ב-\( C_{0} \) ומתנגשים עם תמונה של איברים מ-\( C_{0} \)” זה מסורבל, הבה וניתן שם קומפקטי לקבוצה הזו: \( C_{1}=g\left(f\left(C_{0}\right)\right) \). מה עשינו פה? ראשית, הלכנו ומצאנו את כל האיברים ב-\( B \) שמתקבלים באמצעות הפעלת \( f \) על \( C_{0} \) (זוהי \( f\left(C_{0}\right) \)); כעת חזרנו ל-\( A \) ומצאנו את כל אותם איברים שהם תמונה של הפעלת \( g \) על \( f\left(C_{0}\right) \) (זוהי \( g\left(f\left(C_{0}\right)\right) \)).

עכשיו אפשר לנסות ולהגדיר את \( h \) בצורה טובה יותר:

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

אבל גם ההגדרה הזו נכשלת! כי שוב, מי יערוב לנו שאין איזה \( a \) שאיננו ב-\( C_{0}\cup C_{1} \) אבל \( g^{-1}\left(a\right) \) מתנגש עם התמונה של \( f \) על איזה איבר של \( C_{0}\cup C_{1} \)? למעשה, הדבר היחיד שיכול לקרות הוא התנגשות עם הפעלת \( f \) על איבר של \( C_{1} \) כי באלו של \( C_{0} \) כבר טיפלנו (אם \( a\notin C_{1} \) אז מובטח לנו ש-\( g^{-1}\left(a\right) \) לא מתנגש עם תמונה של איבר מ-\( C_{0} \)) אז שוב, אפשר לנקוט באותו תעלול ולהגדיר קבוצה \( C_{2}=g\left(f\left(C_{1}\right)\right) \) ולהגדיר את \( h \) הפעם בהסתמך על \( C_{0}\cup C_{1}\cup C_{2} \), אבל שוב זה יכול להיכשל! ולכן…

כבר הבנתם לאן זה הולך. הגדרנו סדרה אינסופית של קבוצות, \( C_{0},C_{1},C_{2},\dots \) באופן אינדוקטיבי, כך ש-\( C_{n+1}=g\left(f\left(C_{n}\right)\right) \). אם נעצור אחרי מספר סופי של קבוצות, ניכשל, אבל אחרי מספר אינסופי? ובכן, שווה לנסות את זה, לכל הפחות. נגדיר \( C=\bigcup_{n=0}^{\infty}C_{n} \), וכעת נגדיר:

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

ברור כי \( h \) מוגדרת על כל אברי \( A \), כי זה מה שקורה בהגדרה: \( a\notin C \) פירושו בעצם \( a\in A\backslash C \). נותר להראות שהיא חח”ע, ושהיא על. החח”ע הוא המעניין יותר, כי כל הבניה שלנו הוקדשה כדי להבטיח ש-\( h \) תהיה חח”ע. אז למה זה עובד? עצרו שניה ונסו להוכיח זאת לעצמכם. זה קל עד להפתיע.

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

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

נסיים את ההוכחה על ידי כך שנראה ש-\( h \) על. יהיה \( b\in B \) כלשהו. האם אתם מנחשים לאן זה הולך? ובכן, נתבונן על \( a=g\left(b\right) \). אם \( a\notin C \), סיימנו; \( h\left(a\right)=b \) כנדרש. אם לעומת זאת \( a\in C \) זה אומר שקיים \( n \) כך ש-\( a\in C_{n} \). אם \( n=0 \), זה אומר ש-\( a\in A\backslash g\left(B\right) \), אבל זה בוודאי לא נכון כי ראינו ש-\( a=g\left(b\right) \) ולכן \( a\in g\left(B\right) \). לכן \( n>0 \). מכאן ש-\( a\in g\left(f\left(C_{n-1}\right)\right) \), כלומר קיים \( b_{2}\in f\left(C_{n-1}\right) \) כך ש-\( a=g\left(b_{2}\right) \). קיבלנו ש-\( g\left(b\right)=g\left(b_{2}\right) \) ומהחח”ע של \( g \) נקבל ש-\( b=b_{2}\in f\left(C_{n-1}\right) \), כלומר קיים איבר כלשהו ב-\( A \) שעובר ל-\( b \), ובזאת תמה ההוכחה.

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