משפט קנטור-שרדר-ברנשטיין – הבדלי גרסאות

 

נניח ש-<math>\ f</math> היא פונקציה חד-חד ערכית מ-A ל-B, וש-<math>\ g</math> היא פונקציה חד-חד ערכית מ-B ל-A. כמו כן נניח, [[ללא הגבלת הכלליות]] שהקבוצות A ו-B זרות. נראה שקיימת התאמה חד-חד ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר <math>\ a</math> של הקבוצה A, וכל איבר <math>\ b</math> של הקבוצה 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>''

 

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

 

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

 

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