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

משפט קנטור-שרדר-ברנשטיין קובע: אם קיימת פונקציה חד-חד-ערכית מ‑A ל‑B ו קיימת פונקציה חד-חד-ערכית מ‑B ל‑A, אז קיימת פונקציה שהיא גם חד-חד-ערכית וגם על מ‑A ל‑B. פונקציה חד-חד-ערכית אומרת שכל שני איברים שונים בקבוצה המקורית נשלחים לתמונות שונות. פונקציה עלית (על) אומרת שכל איבר ב‑B הוא תמונה של איזה איבר ב‑A. משמעות המשפט היא ששתי הקבוצות שקולות, כלומר עוצמתן זהה. בעיצוב בעוצמות נוהגים לכתוב: אם |A| ≤ |B| וגם |B| ≤ |A| אז |A| = |B|. כאן |A| מסמל את "גודל" או מספר האיברים של A.


יש כמה הוכחות שונות. כולן בנויות על חלוקה של האיחוד A∩B לחלקים, ושימוש ב‑f וב‑g ליצירת ההתאמה (ביקציה) בין הקבוצות.


מגדירים עבור כל איבר שרשרת של איברים לסירוגין מ‑A ומ‑B על ידי החלת f או g. למשל: ... → g^{-1}(a) → a → f(a) → g(f(a)) → ... .

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


ניתן גם להניח בלי הגבלת הכלליות ש‑B ⊆ A באמצעות ההעתקה g. נגדיר סוגים של איברים ב‑A לפי ההרכבות של f, החל מ‑A\B. קוראים "סוג ראשון" לאיברים שהם תמונה של איבר מ‑A\B אחרי כמה החלות של f, ו"סוג שני" לאחרים. נגדיר h(x)=f(x) אם x מסוג ראשון, ו‑h(x)=x אם לא. קל לבדוק ש‑h היא חד-חד-ערכית ועל. זאת משום שאיברים מסוג ראשון נבדלים זה מזה על ידי f, ואיברי B נתקפים על ידי תמונה של איברים מתאימים.


משתמשים בלמה פיקס‑פוינט על מפעיל F על קבוצות משנה של A ששומר הכלה (אם X⊆Y אז F(X)⊆F(Y)). הלמה מבטיחה קיומה של קבוצה C שאינה משתנה תחת F, כלומר F(C)=C. עבור F(X)=A\g(B\f(X)) מתקבלת קבוצת C כזו. מחישוב לפי ההגדרה מקבלים חלוקה שמובילה להשוואת העוצמות |A|=|B|.


מחשבים את גודל קבוצת כל הפונקציות ℕ^ℕ (מהמספרים הטבעיים אליהם). מכיוון שכל פונקציה מ‑ℕ ל‑
{0,1} היא גם פונקציה מ‑ℕ ל‑ℕ, ויש אף פונקציות מ‑ℕ לריאלים, מקבלים הכללות שבאמצעות חישובי חזקות מובילות לשני אי-שוויונות. בעזרת חישומי חזקות סטנדרטיים ומיצוי משפט קנטור‑שרדר‑ברנשטיין מקבלים כי |ℕ^ℕ| שווה לעוצמת הרצף (הקונטינואום).

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


יש כמה דרכים להראות את זה. כל דרך מחלקת את האיברים לקבוצות קטנות ואז בוחרת חיבור מתאים בכל קבוצה.


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


אפשר גם לעשות זאת ככה: נניח ש‑B היא חלק מ‑A. נסמן את האיברים שמתחילים מחוץ ל‑B ואז נעקוב אחרי התמונות שלהם ב‑f. לכל איבר שמגיע משרשרת כזו משתמשים ב‑f; לשאר האיברים משאירים אותם כפי שהם. כך מקבלים חיבור חזק שכל A מקושר ל‑B.


יש כלל מתמטי שאומר שאם פונקציה על קבוצות שומרת הכלה, אז יש קבוצה שמתאימה לעצמה. מגדירים פונקציה מתאימה ומוצאים קבוצה כזו. מכך נובע ש‑A ו‑B שוות בגודל.


שוקלים את כל הפונקציות מהמספרים הטבעיים לעצמם. משווים אותן לפונקציות שכותבות רק 0 ו‑1 ולפונקציות לריאלים. עם חישוב פשוט וממשפט קנטור‑שרדר‑ברנשטיין מקבלים שהתוצאה היא אותה "כמות" כמו של כל הרצפים הממשיים.