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

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

בכתיב עוצמות ניתן לנסח את המשפט כך: אם $|A|\leq |B|$ וגם $|B|\leq |A|$ אז $|A|=|B|$. המשפט מכונה גם "למת הסנדוויץ'" (משום שהוא מסיק מאי-השוויונות $|A|\leq |B|\leq |A|$ את שוויון העוצמות).

חשיבותו הרבה של המשפט היא בכך שהוא מראה שהיחס "$|A|\leq |B|$ אם יש פונקציה חד-חד-ערכית מ-$A$ ל-$B$" הוא יחס יחס אנטי-סימטרי. ברור שהיחס הזה טרנזיטיבי, ואם כך הוא מהווה יחס סדר חלש. כדי להוכיח שהיחס הוא יחס סדר מלא, כלומר שלכל שתי עוצמות $a,b$ מתקיים $a\leq b$ או $b\leq a$, דרושה אקסיומת הבחירה.

הוכחות של המשפט

נניח ש-$f$ היא פונקציה חד-חד-ערכית מ-$A$ ל-$B$, וש-$g$ היא פונקציה חד-חד-ערכית מ-$B$ ל-$A$. נציג כמה הוכחות של המשפט, המבוססות כולן, בדרכים שונות, על חלוקה של אחת הקבוצות לשני חלקים ושימוש ב-$f$ עבור אחד מהחלקים וב-$g$ עבור השני כדי להגדיר את הבייקציה בין הקבוצות.

הוכחה באמצעות סיווג של האיברים

נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל $h$ מ־$A$ ל־$B$.

נניח, ללא הגבלת הכלליות שהקבוצות $A$ ו-$B$ זרות. נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר $a$ של הקבוצה $A$, וכל איבר $b$ של הקבוצה $B$, סדרת איברים מ-$A$ ומ-$B$ לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר שקודם לו:

$\cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(a)\rightarrow a\rightarrow f(a)\rightarrow g(f(a))\rightarrow \cdots$

נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש-$f^{-1}$ ו-$g^{-1}$ לא מוגדרות לכל איברי $B$ ו-$A$ בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף. הסדרות יכולות להסתיים משמאל באיבר של $A$, להסתיים משמאל באיבר של $B$, או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כסדרות קצה-$A$, סדרות קצה-$B$ או סדרות ללא קצה בהתאמה. מכיוון ש-$f$ ו-$g$ הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן. הסדרות יוצרות חלוקה של האיחוד של $A$ ו-$B$. לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ-$A$ ל-$B$ בכל אחת מהסדרות בנפרד.

כעת, נבנה את הפונקציה החד-חד-ערכית ועל $h$ מ-$A$ ל-$B$: עבור איברי $A$ ששייכים לסדרת קצה-$A$, נגדיר את $h(a)$ כ-$f(a)$ (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר). עבור איברי $A$ ששייכים לסדרת קצה-$B$, נגדיר את $h(a)$ כ-$g^{-1}(a)$ (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר), ובאותו אופן נגדיר גם את $h$ עבור איברי $A$ ששייכים לסדרה ללא קצה. קל לראות שהפונקציה $h$ היא אכן חד-חד-ערכית ועל.

בניה ישירה של ההתאמה

נחליף את הקבוצה $B$ בתמונה שלה $g(B)\subseteq A$, שהיא ממילא שוות עוצמה ל-$B$ משום ש-$g$ חד-חד-ערכית.

כעת אפשר להניח ש-$B\subseteq A$ ונתונה פונקציה חד-חד-ערכית $f:A\rightarrow B$; עלינו לבנות פונקציה כזו שהיא חד-חד-ערכית ועל. נסמן ב-$f^{n}$ את ההרכבה של $f$ על עצמה $n$ פעמים (כאשר $f^{0}$ היא פונקציית הזהות). נאמר שאיבר $x\in A$ הוא מסוג ראשון אם קיימים $a\in A\setminus B$ ו-$n\geq 0$ כך ש-$x=f^{n}(a)$, ומסוג שני אחרת. נגדיר פונקציה $h:A\rightarrow B$ באופן הבא: $h(x)=f(x)$ אם $x$ מסוג ראשון, ו-$h(x)=x$ אחרת. כעת נוכיח כמה טענות קלות:

1. $h$ מוגדרת לתוך $B$. אכן, כל איבר של $A\setminus B$ הוא מסוג ראשון, ולכן $h(A)\subseteq f(A\setminus B)\cup B=B$.
2. $h$ חד-חד-ערכית. נניח ש-$h(x)=h(y)$. אם $x,y$ שניהם מסוג ראשון הם שווים כי $f$ חד-חד-ערכית; ואם שניהם מסוג שני הם שווים לפי ההנחה. נניח, אם כך, ש-$x$ מסוג ראשון ו-$y$ מסוג שני. מכיוון ש-$x$ מסוג ראשון אפשר לכתוב $x=f^{n}(a)$ עבור $a\in A\setminus B$, ומכיוון ש-$y$ מסוג שני, $y=h(y)=h(x)=f(x)=f^{n+1}(a)$, כלומר גם $y$ מסוג ראשון, בסתירה להנחה שהאברים מסוגים שונים.
3. $h$ על: אם $b\in B$ הוא מסוג שני, אז הוא שווה לתמונת $h$ של עצמו; ואם הוא מסוג ראשון אז $b=f^{n}(a)$ ובהכרח $n>0$, ולכן $b'=f^{n-1}(a)$ גם הוא מסוג ראשון, ואז $h(b')=f(b')=f^{n}(a)=b$, כך ש-$b$ בתמונת $h$ בכל מקרה.

הוכחה באמצעות למת נקודת השבת

מסמנים ב-$P(A)$ את קבוצת החזקה של $A$. נשתמש בלמה הבאה:

למה: תהי $F:P(A)\rightarrow P(A)$ פונקציה שומרת הכלה (כלומר, אם $X\subseteq Y$ אז $F(X)\subseteq F(Y)$). אז יש לה נקודת שבת (כלומר קבוצה $C\subseteq A$ כך ש-$F(C)=C$).

הוכחה

נתבונן באוסף ${\mathcal {L}}$ של כל הקבוצות $X\subseteq A$ כך ש- $X\subseteq F(X)$. (זהו אוסף לא ריק כי הקבוצה הריקה מקיימת את התנאי). נסמן ב-$C$ את איחוד כל הקבוצות באוסף. לכל $c\in C$ יש $X\in {\mathcal {L}}$ כך ש-$c\in X$ ואז $c\in X\subseteq F(X)\subseteq F(C)$, כלומר $c\in F(C)$. הוכחנו, אם כך, ש-$C\subseteq F(C)$. מכיוון ש-$F$ שומרת הכלה, מתקיים $F(C)\subseteq F(F(C))$, כלומר $F(C)\in {\mathcal {L}}$, ולפי ההגדרה של $C$ כאיחוד, $F(C)\subseteq C$. לכן $C$ היא נקודת שבת.

כעת נבחר $F(X)=A\setminus g(B\setminus f(X))$. ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-$C$. מכיוון ש-$g(B\setminus f(C))=A\setminus C$, קיבלנו ש-$|A\setminus C|=|g(B\setminus f(C))|=|B\setminus f(C)|$, ולכן $|A|=|A\setminus C|+|C|=|B\setminus f(C)|+|f(C)|=|B|$.

דוגמה לשימוש במשפט

נחשב את $|\{f\mid f\colon \mathbb {N} \to \mathbb {N} \}|$ (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם, שמסומנת גם $\mathbb {N} ^{\mathbb {N} }$):

ראשית נשים לב שמתקיים $\{f|f:\mathbb {N} \to \{1,0\}\}\subset \{f|f:\mathbb {N} \to \mathbb {N} \}\subset \{f|f:\mathbb {N} \to \mathbb {R} \}$ כי כל פונקציה מהטבעיים לקבוצה $\{0,1\}$ היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.

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

$|\{f\mid f\colon \mathbb {N} \to \{1,0\}\}|\leq |\{f\mid f\colon \mathbb {N} \to \mathbb {N} \}|\leq |\{f\mid f\colon \mathbb {N} \to \mathbb {R} \}|$

לפי ההגדרה המוכללת לחזקה, האי שוויון הנ"ל שקול ל:

$2^{\aleph _{0}}\leq \aleph _{0}^{\aleph _{0}}\leq \aleph ^{\aleph _{0}}$ (כאשר $\aleph _{0}$ היא אָלֶף אֶפֶס ו-$\aleph$ היא עוצמת הרצף)

אבל מתקיים $|2^{\aleph _{0}}|=\aleph$ וכמו כן, על פי חוקי החזקות: $\aleph ^{\aleph _{0}}=(2^{\aleph _{0}})^{\aleph _{0}}=2^{\aleph _{0}\cdot \aleph _{0}}=2^{\aleph _{0}}=\aleph$ (להוכחת השוויון $\aleph _{0}\cdot \aleph _{0}=\aleph _{0}$, ראו כאן)

לכן $\aleph \leq \aleph _{0}^{\aleph _{0}}\leq \aleph$, ועל פי משפט קנטור-שרדר ברנשטיין נקבל $\aleph _{0}^{\aleph _{0}}=\aleph$, משמע קיבלנו $|\mathbb {N} ^{\mathbb {N} }|=\aleph$.

ראו גם

• פונקציית הזיווג של קנטור

קישורים חיצוניים

מדיה וקבצים בנושא משפט קנטור-שרדר-ברנשטיין בוויקישיתוף

• משפט קנטור-שרדר-ברנשטיין, באתר MathWorld (באנגלית)