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

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

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

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

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

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

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

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

::*<math> \cdots \rightarrow  f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow   a  \rightarrow  f(a) \rightarrow  g(f(a)) \rightarrow \cdots </math>*

נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש-f^{-1} ו-g^{-1} לא מוגדרות לכל איברי B ו-A בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף. הסדרות יכולות להסתיים משמאל באיבר של A, להסתיים משמאל באיבר של B, או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כ**סדרות קצה-<math>A</math>**, **סדרות קצה-<math>B</math>** או **סדרות ללא קצה** בהתאמה. מכיוון ש-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  אחרת. כעת נוכיח כמה טענות קלות:
#h מוגדרת לתוך B. אכן, כל איבר של A \setminus B הוא מסוג ראשון, ולכן h(A) \subseteq f(A \setminus B) \cup B = B.
#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 מסוג ראשון, בסתירה להנחה שהאברים מסוגים שונים.
#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). 

כעת נבחר 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\}\}| \le |\{f \mid f \colon \mathbb {N} \to \mathbb {N}\}| \le |\{f \mid f \colon \mathbb {N} \to \mathbb {R}\}|
 
לפי ההגדרה המוכללת לחזקה, האי שוויון הנ"ל שקול ל:

2^{\aleph_0} \le \aleph_0 ^ {\aleph_0} \le \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 \le \aleph_0^{\aleph_0} \le \aleph, ועל פי משפט קנטור-שרדר ברנשטיין נקבל \aleph_0^{\aleph_0} = \aleph, משמע קיבלנו |\mathbb{N}^\mathbb{N}| = \aleph.

## ראו גם
* פונקציית הזיווג של קנטור

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

* 

קנטור שרדר ברנשטיין
סנדוויץ