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

בתורת הקבוצות, משפט קנטור-שרדר-ברנשטיין אומר כך:

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

ניתן לנסח את המשפט בכתיב עוצמות כך: אם $|A|\leq |B|$ וגם $|B|\leq |A|$ אז $|A|=|B|$ .

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

לעומת עוצמות סופיות (המספרים הטבעיים), שם יחס הסדר הוא גם ברור ומובן אינטואיטיבית, יחס הסדר בעוצמות אינסופיות לא תמיד ברור (למשל: עוצמת הרציונלים שווה לעוצמת השלמים, השווה לעוצמת הטבעיים, זאת למרות ההכלה ממש) ומשפט זה מוכיח שאכן קיים יחס סדר שכזה. המשפט מוכיח כי היחס $\leq$ הוא סדר חלקי. בעזרת אקסיומת הבחירה ניתן להוכיח שהיחס הוא גם סדר מלא, כלומר לכל שתי עוצמות $a,b$ מתקיים $a\leq b$ או $b\leq a$ .

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

הוכחת המשפט

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

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

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

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

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

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

כעת, נבנה את הפונקציה החד-חד-ערכית ועל $h:A\to B$ :

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

קל לראות שהפונקציה $h$ היא אכן חד-חד-ערכית ועל.

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

נחשב את ${\Big |}{\big \{}f|f:\mathbb {N} \to \mathbb {N} {\big \}}{\Big |}$ (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם):

ראשית נשים לב שמתקיים

${\bigl \{}f|f:\mathbb {N} \to \{1,0\}{\bigr \}}\subset {\bigl \{}f|f:\mathbb {N} \to \mathbb {N} {\bigr \}}\subset {\bigl \{}f|f:\mathbb {N} \to \mathbb {R} {\bigr \}}$

כי כל פונקציה מהטבעיים לקבוצה $\{0,1\}$ היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.

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

${\bigl \{}f|f:\mathbb {N} \to \{1,0\}{\bigr \}}\leq {\bigl \{}f|f:\mathbb {N} \to \mathbb {N} {\bigr \}}\leq {\bigl \{}f|f:\mathbb {N} \to \mathbb {R} {\bigr \}}$

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

$2^{\aleph _{0}}\leq \aleph _{0}^{\aleph _{0}}\leq \aleph ^{\aleph _{0}}$

כאשר: $\aleph _{0}$ אלף 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$ .

ראו גם

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