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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

בכתיבה מתמטית פורמלית: אם $|A|\le|B|$ וגם $|B|\le|A|$ אז $\ |A|=|B|$ .

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

[עריכה] הוכחת המשפט

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

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

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

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