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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

הוכחה

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

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

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

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

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

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

${\displaystyle |\{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} \}|}$

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

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

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

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

ראו גם

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

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

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

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