משפט קנטור-שרדר-ברנשטיין – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 36:
=== הוכחה באמצעות למת נקודת השבת ===
מסמנים ב-<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(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>.
| |||