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

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

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

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

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

המשפט מכונה גם "למת הסנדוויץ'". כינוי זה בא מניסוח שקול: "אם |A|\le|B|\le|C| וגם |A|=|C| אז |A|=|B|=|C|" בדומה למשפט הסנדוויץ'.

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

נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל \ h מ־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 היא אכן חד-חד ערכית ועל.

דוגמה לשימוש במשפט[עריכת קוד מקור | עריכה]

נחשב את |\{f|f: \mathbb {N} \to \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|f: \mathbb {N} \to \{1,0\}\}| \le |\{f|f: \mathbb {N} \to \mathbb {N}\}| \le |\{f|f: \mathbb {N} \to \mathbb {R}\}|

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

2^{\aleph_0} \le \aleph_0 ^ {\aleph_0} \le \aleph^{\aleph_0} (כאשר \aleph_0 היא אלף 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.


נושאים בתורת הקבוצות

תורת הקבוצות הנאיביתתורת הקבוצות האקסיומטיתקבוצהיחידוןהקבוצה הריקהאיחודחיתוךמשליםהפרש סימטריקבוצת החזקהמכפלה קרטזיתיחסיחס שקילותפונקציהעוצמהקבוצה בת מנייההאלכסון של קנטורמשפט קנטור שרדר ברנשטייןהשערת הרצףהפרדוקס של ראסלסדר חלקימספר סודרהלמה של צורןאקסיומת הבחירה