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

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

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

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

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

נניח ש-<math>f</math> היא פונקציה חד-חד-ערכית מ-<math>A</math> ל-<math>B</math>, וש-<math>g</math> היא פונקציה חד-חד-ערכית מ-<math>B</math> ל-<math>A</math>. נציג כמה הוכחות של המשפט, המבוססות כולן, בדרכים שונות, על חלוקה של אחת הקבוצות לשני חלקים ושימוש ב-<math>f</math> עבור אחד מהחלקים וב-<math>g</math> עבור השני כדי להגדיר את הבייקציה בין הקבוצות.

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

נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל <math>h</math> מ־<math>A</math> ל־<math>B</math>.

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

<math> \cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots </math>

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

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

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

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

כעת אפשר להניח ש-<math>B \subseteq A</math> ונתונה פונקציה חד-חד-ערכית <math>f : A \rightarrow B</math>; עלינו לבנות פונקציה כזו שהיא חד-חד-ערכית ועל. נסמן ב-<math>f^n</math> את ההרכבה של <math>f</math> על עצמה <math>n</math> פעמים (כאשר <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> אחרת. כעת נוכיח כמה טענות קלות:

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

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

מסמנים ב-<math>P(A)</math> את קבוצת החזקה של <math>A</math>. נשתמש בלמה הבאה:

למה: תהי <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>. (זהו אוסף לא ריק כי הקבוצה הריקה מקיימת את התנאי). נסמן ב-<math>C</math> את איחוד כל הקבוצות באוסף. לכל <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>. מכיוון ש-<math>F</math> שומרת הכלה, מתקיים <math>F(C) \subseteq F(F(C))</math>, כלומר <math>F(C) \in \mathcal{L}</math>, ולפי ההגדרה של <math>C </math> כאיחוד, <math>F(C) \subseteq C</math>. לכן <math>C </math> היא נקודת שבת.

כעת נבחר <math>F(X) = A \setminus g(B \setminus f(X))</math>. ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-<math>C </math>. מכיוון ש-<math>g(B \setminus f(C)) = A \setminus C</math>, קיבלנו ש-<math>|A \setminus C| = |g(B \setminus f(C)) | = |B \setminus f(C)|</math>, ולכן <math>|A| = |A \setminus C| + |C| = |B \setminus f(C)|+|f(C)| = |B|</math>.

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

נחשב את <math>|\{f \mid f \colon \mathbb {N} \to \mathbb {N}\}|</math> (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם, שמסומנת גם <math>\mathbb{N}^\mathbb{N}</math>):

ראשית נשים לב שמתקיים <math>\{f|f: \mathbb {N} \to \{1,0\}\} \subset \{f|f: \mathbb {N} \to \mathbb {N}\} \subset \{f|f: \mathbb {N} \to \mathbb {R}\}</math> כי כל פונקציה מהטבעיים לקבוצה <math>\{0,1\} </math> היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.

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

<math>|\{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}\}|</math>

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

<math>2^{\aleph_0} \le \aleph_0 ^ {\aleph_0} \le \aleph^{\aleph_0}</math> (כאשר <math>\aleph_0</math> היא אָלֶף אֶפֶס ו-<math>\aleph</math> היא עוצמת הרצף)

אבל מתקיים <math>|2^{\aleph_0}|=\aleph</math> וכמו כן, על פי חוקי החזקות: <math>\aleph ^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0}=\aleph</math> (להוכחת השוויון <math>\aleph_0 \cdot \aleph_0 = \aleph_0</math>, ראו כאן)

לכן <math>\aleph \le \aleph_0^{\aleph_0} \le \aleph</math>, ועל פי משפט קנטור-שרדר ברנשטיין נקבל <math>\aleph_0^{\aleph_0} = \aleph</math>, משמע קיבלנו <math>|\mathbb{N}^\mathbb{N}| = \aleph</math>.

ראו גם

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

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

ויקישיתוף מדיה וקבצים בנושא [[commons:Category:{{#property:P373}}|משפט קנטור-שרדר-ברנשטיין]] בוויקישיתוף

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