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

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

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

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

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

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

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

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

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

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

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

נחליף את הקבוצה  בתמונה שלה , שהיא ממילא שוות עוצמה ל- משום ש- חד-חד-ערכית. 

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

 הוכחה באמצעות למת נקודת השבת 
מסמנים ב- את קבוצת החזקה של .
נשתמש בלמה הבאה:

למה: תהי  פונקציה שומרת הכלה (כלומר, אם  אז ). אז יש לה נקודת שבת (כלומר קבוצה  כך ש-). 

כעת נבחר . ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-. מכיוון ש-, קיבלנו ש-, ולכן .

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

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

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


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

 (כאשר  היא אָלֶף אֶפֶס ו- היא עוצמת הרצף)

אבל מתקיים  וכמו כן, על פי חוקי החזקות:  (להוכחת השוויון , ראו כאן)

לכן , ועל פי משפט קנטור-שרדר ברנשטיין נקבל , משמע קיבלנו .

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

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



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