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

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

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

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

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

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

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

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

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

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

$latex 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}$

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

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

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

$latex 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}$

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

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

$latex 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}$

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

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

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

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

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com