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

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

בכתיב עוצמות ניתן לנסח את המשפט כך: אם $|A|\leq |B|$ וגם $|B|\leq |A|$ אז $|A|=|B|$. המשפט מכונה גם "למת הסנדוויץ'" (משום שהוא מסיק מאי-השוויונות $|A|\leq |B|\leq |A|$ את שוויון העוצמות).

חשיבותו הרבה של המשפט היא בכך שהוא מראה שהיחס "$|A|\leq |B|$ אם יש פונקציה חד-חד-ערכית מ-$A$ ל-$B$" הוא יחס יחס אנטי-סימטרי. ברור שהיחס הזה טרנזיטיבי, ואם כך הוא מהווה יחס סדר חלש. כדי להוכיח שהיחס הוא יחס סדר מלא, כלומר שלכל שתי עוצמות $a,b$ מתקיים $a\leq b$ או $b\leq a$, דרושה אקסיומת הבחירה.

הוכחות של המשפט

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

הוכחה באמצעות סיווג של האיברים

נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל $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$ או סדרות ללא קצה בהתאמה. מכיוון ש-$f$ ו-$g$ הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן. הסדרות יוצרות חלוקה של האיחוד של $A$ ו-$B$. לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ-$A$ ל-$B$ בכל אחת מהסדרות בנפרד.

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

בניה ישירה של ההתאמה

נחליף את הקבוצה $B$ בתמונה שלה $g(B)\subseteq A$, שהיא ממילא שוות עוצמה ל-$B$ משום ש-$g$ חד-חד-ערכית.

כעת אפשר להניח ש-$B\subseteq A$ ונתונה פונקציה חד-חד-ערכית $f:A\rightarrow B$; עלינו לבנות פונקציה כזו שהיא חד-חד-ערכית ועל. נסמן ב-$f^{n}$ את ההרכבה של $f$ על עצמה $n$ פעמים (כאשר $f^{0}$ היא פונקציית הזהות). נאמר שאיבר $x\in A$ הוא מסוג ראשון אם קיימים $a\in A\setminus B$ ו-$n\geq 0$ כך ש-$x=f^{n}(a)$, ומסוג שני אחרת. נגדיר פונקציה $h:A\rightarrow B$ באופן הבא: $h(x)=f(x)$ אם $x$ מסוג ראשון, ו-$h(x)=x$ אחרת. כעת נוכיח כמה טענות קלות:

1. $h$ מוגדרת לתוך $B$. אכן, כל איבר של $A\setminus B$ הוא מסוג ראשון, ולכן $h(A)\subseteq f(A\setminus B)\cup B=B$.
2. $h$ חד-חד-ערכית. נניח ש-$h(x)=h(y)$. אם $x,y$ שניהם מסוג ראשון הם שווים כי $f$ חד-חד-ערכית; ואם שניהם מסוג שני הם שווים לפי ההנחה. נניח, אם כך, ש-$x$ מסוג ראשון ו-$y$ מסוג שני. מכיוון ש-$x$ מסוג ראשון אפשר לכתוב $x=f^{n}(a)$ עבור $a\in A\setminus B$, ומכיוון ש-$y$ מסוג שני, $y=h(y)=h(x)=f(x)=f^{n+1}(a)$, כלומר גם $y$ מסוג ראשון, בסתירה להנחה שהאברים מסוגים שונים.
3. $h$ על: אם $b\in B$ הוא מסוג שני, אז הוא שווה לתמונת $h$ של עצמו; ואם הוא מסוג ראשון אז $b=f^{n}(a)$ ובהכרח $n>0$, ולכן $b'=f^{n-1}(a)$ גם הוא מסוג ראשון, ואז $h(b')=f(b')=f^{n}(a)=b$, כך ש-$b$ בתמונת $h$ בכל מקרה.

הוכחה באמצעות למת נקודת השבת

מסמנים ב-$P(A)$ את קבוצת החזקה של $A$. ראשית, נוכיח למה: תהי $F:P(A)\rightarrow P(A)$ פונקציה שומרת הכלה (כלומר, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \subseteq Y} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(X) \subseteq F(Y)} ). אז יש לה נקודת שבת (כלומר קבוצה $C\subseteq A$ כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(C) = C} ). הוכחה: נתבונן באוסף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}} של כל הקבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \subseteq A} כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \subseteq F(X)} . (זהו אוסף לא ריק כי הקבוצה הריקה מקיימת את התנאי). נסמן ב-C את איחוד כל הקבוצות באוסף. לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \in C} יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \in \mathcal{L}} כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \in X} ואז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \in X \subseteq F(X) \subseteq F(C)} , כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \in F(C)} . הוכחנו, אם כך, ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C \subseteq F(C)} . מכיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} שומרת הכלה, מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(C) \subseteq F(F(C))} , כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(C) \in \mathcal{L}} , ולפי ההגדרה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C } כאיחוד, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(C) \subseteq C} . לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C } היא נקודת שבת.

כעת נבחר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(X) = A \setminus f(B \setminus g(X))} . ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C } . מכיוון ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(B \setminus g(C)) = A \setminus C} , קיבלנו ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A \setminus C| = |f(B \setminus g(C)) | = |B \setminus g(C)|} , ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |A| = |A \setminus C| + |C| = |B \setminus g(C)|+|g(C)| = |B|} .

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

נחשב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\{f \mid f \colon \mathbb {N} \to \mathbb {N}\}|} (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם, שמסומנת גם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}^\mathbb{N}} ):

ראשית נשים לב שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{f|f: \mathbb {N} \to \{1,0\}\} \subset \{f|f: \mathbb {N} \to \mathbb {N}\} \subset \{f|f: \mathbb {N} \to \mathbb {R}\}} כי כל פונקציה מהטבעיים לקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1\} } היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\{f \mid f \colon \mathbb {N} \to \{1,0\}\}| \le |\{f \mid f \colon \mathbb {N} \to \mathbb {N}\}| \le |\{f \mid f \colon \mathbb {N} \to \mathbb {R}\}|}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\aleph_0} \le \aleph_0 ^ {\aleph_0} \le \aleph^{\aleph_0}} (כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0} היא אָלֶף אֶפֶס ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph} היא עוצמת הרצף)

אבל מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |2^{\aleph_0}|=\aleph} וכמו כן, על פי חוקי החזקות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph ^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0}=\aleph} (להוכחת השוויון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0 \cdot \aleph_0 = \aleph_0} , ראו כאן)

לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph \le \aleph_0^{\aleph_0} \le \aleph} , ועל פי משפט קנטור-שרדר ברנשטיין נקבל $\aleph _{0}^{\aleph _{0}}=\aleph$, משמע קיבלנו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\mathbb{N}^\mathbb{N}| = \aleph} .

ראו גם

• פונקציית הזיווג של קנטור

קישורים חיצוניים

מדיה וקבצים בנושא משפט קנטור-שרדר-ברנשטיין בוויקישיתוף

• משפט קנטור-שרדר-ברנשטיין, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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