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

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

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

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

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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