משפט קנטור-שרדר-ברנשטיין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 8:
המשפט מכונה גם "למת הסנדוויץ'". כינוי זה בא מניסוח שקול: "אם <math>|A|\le|B|\le|C|</math> וגם <math>|A|=|C|</math> אז <math>|A|=|B|=|C|</math>" בדומה ל[[כלל הסנדוויץ']].
==
נציג כמה הוכחות של המשפט, המבוססות כולן, בדרכים שונות, על חלוקה של אחת הקבוצות לשני חלקים.
=== הוכחה באמצעות סיווג של האברים ===
נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל <math>\ h</math> מ־A ל־B.
שורה 19 ⟵ 23:
כעת, נבנה את הפונקציה החד-חד-ערכית ועל <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> היא אכן חד-חד-ערכית ועל.
=== בניה ישירה של ההתאמה ===
נחליף את הקבוצה B בתמונה שלה <math>\ g(B) \subseteq A</math>, שהיא בעלת אותה עוצמה משום ש-g חד-חד-ערכית. כעת אפשר להניח ש-<math>\ B \subseteq A</math> ונתונה פונקציה חד-חד-ערכית <math>\ f : A \rightarrow B</math>. נסמן ב-<math>\ f^n</math> את ההרכבה של f על עצמה n פעמים (כאשר <math>\ f^0</math> היא פונקציית הזהות). נאמר שאיבר <math>\ x\in A</math> הוא מ'''סוג ראשון''' אם קיימים <math>\ a \in A \setminus B </math> ו-<math>\ n \geq 0</math> כך ש-<math>\ x = f^n(a)</math>, ומ'''סוג שני''' אחרת.
נגדיר פונקציה <math>\ h : A \rightarrow B</math> באופן הבא: <math>\ h(x) = f(x) </math> אם <math>\ x</math> מסוג ראשון, ו-<math>\ h(x) = x </math> אחרת. כעת נוכיח כמה טענות קלות:
# h מוגדרת לתוך B. אכן, כל איבר של <math>\ A \setminus B</math> הוא מסוג ראשון, ולכן <math>\ h(A) \subseteq f(A \setminus B) \cup B = B</math>.
# h חד-חד-ערכית. נניח ש-<math>\ h(x) = h(y)</math>. אם x,y שניהם מסוג ראשון הם שווים כי f חד-חד-ערכית; ואם שניהם מסוג שני הם שווים לפי ההנחה. נניח, אם כך, ש-x מסוג ראשון ו-y מסוג שני. לפי ההנחה אפשר לכתוב <math>x = f^n(a)</math> עבור <math>\ a \in A \setminus B</math>, ולפי ההנחה <math>y = h(y) = h(x) = f(x) = f^{n+1}(a)</math>, כלומר גם y מסוג ראשון, בסתירה להנחה שהאברים מסוגים שונים.
# h על: אם <math>b \in B</math> הוא מסוג שני, אז הוא שווה לתמונת h של עצמו; ואם הוא מסוג ראשון אז <math>b = f^n(a)</math> ובהכרח <math>n>0</math>, ולכן <math>\ b' = f^{n-1}(a)</math> גם הוא מסוג ראשון, ואז <math>\ h(b') = f(b') = f^n(a) = b</math>, כך ש-b בתמונת h בכל מקרה.
=== הוכחה באמצעות למת נקודת השבת ===
מסמנים ב-<math>\ P(A)</math> את [[קבוצת החזקה]] של A.
ראשית, נוכיח '''למה''': תהי <math>\ F : P(A) \rightarrow P(A)</math> פונקציה שומרת הכלה (כלומר, אם <math>\ X \subseteq Y</math> אז <math>\ F(X) \subseteq F(Y)</math>). אז יש לה נקודת שבת (כלומר קבוצה <math>C \subseteq A</math> כך ש-<math>F(C) = C</math>). הוכחה: נתבונן באוסף <math>\ \mathcal{L}</math> של כל הקבוצות <math>X \subseteq A</math> כך ש- <math>X \subseteq F(X)</math>. (זהו אוסף לא ריק כי [[הקבוצה הריקה]] מקיימת את התנאי). נסמן ב-C את איחוד כל הקבוצות באוסף. לכל <math>\ c \in C</math> יש <math>\ X \in \mathcal{L}</math> כך ש-<math>\ c \in X</math> ואז <math>\ c \in X \subseteq F(X) \subseteq F(C)</math>, כלומר <math>\ c \in F(C)</math>. הוכחנו, אם כך, ש-<math>\ C \subseteq F(C)</math>. מכיוון ש-F שומרת הכלה, מתקיים <math>\ F(C) \subseteq F(F(C))</math> ואז <math>\ F(C) \in \mathcal{L}</math> ולפי ההגדרה <math>\ F(C) \subseteq C</math>. לכן <math>C </math> היא נקודת שבת.
כעת נבחר <math>\ F(X) = A \setminus f(B \setminus g(X))</math>. ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-C. מכיוון ש-<math>f(B \setminus g(C)) = A \setminus C</math>, קיבלנו ש-<math>\ |A \setminus C| = |f(B \setminus g(C)) | = |B \setminus g(C)|</math>, ולכן <math>\ |A| = |A \setminus C| + |C| = |B \setminus g(C)|+|g(C)| = |B|</math>.
==דוגמה לשימוש במשפט==
| |||