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

שעור ששה-עשר: משפט קנטור-ברנשטיין

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

טענה. יש פונקציה חד-חד-ערכית $A\to B$ אם ורק אם יש פונקציה על $B\to A$.

הוכחה. נזכיר שפונקציה היא אוסף של זוגות סדורים. אם $f:A\to B$ חד-חד-ערכית, אז "הפונקציה ההפוכה" מ-B ל-A אמנם אינה בהכרח פונקציה (היא אינה מוגדרת בכל הנקודות של B), אבל אפשר להשלים אותה לפונקציה על-ידי הגדרה $f(b)=a_0$ לכל הנקודות שאינן בטווח של f, עבור $a_0\in A$ קבוע. הפונקציה המתקבלת היא על (תרגיל). ולהיפך, אם $g:B\to A$ על, אז הפונקציה ההפוכה מ-A ל-B אמנם אינה בהכרח פונקציה (היא עשויה לקבל יותר מערך אחד בנקודות מסויימות של A), אבל אם מדללים אותה על-ידי השמטה, לכל a, של כל הזוגות מהצורה $(a,*)$ פרט לאחד, מתקבלת פונקציה חד-חד-ערכית מ-A ל-B.

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

הגדרה. נאמר ש-$|A|\le |B|$ אם A שוות-עוצמה לתת-קבוצה של B.

דוגמאות.

1. אם $|A|=|B|$ אז בוודאי $|A|\le |B|$.
2. לכל תת-קבוצה $A\subseteq B$ מתקיים $|A|\le |B|$.
3. בעבר הוכחנו שאם A אינסופית, אז ${\mathrm{\aleph }}_0\le |A|$.

לסימן אי-השוויון "$\le$" יש כמה תכונות מתבקשות. ראשית היינו רוצים שיתקיים $|A|\le |A|$ ("רפלקסיביות"). שנית, טרנזיטיביות --

הערה. אם $|A|\le |B|$ ו- $|B|\le |C|$ אז $|A|\le |C|$.

הוכחה. לפי ההנחה יש פונקציות חד-חד-ערכיות מ-A ל-B ומ-B ל-C; ההרכבה היא פונקציה חד-חד-ערכית מ-A ל-C.

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

אם $A,B$ קבוצות, פונקציה $F:P(A)\to P(B)$ היא מונוטונית, אם לכל שתי תת-קבוצות $A_0\subseteq A_1$ של A, מתקיים $F(A_0)\subseteq F(A_1)$.

למה. תהי $F:P(A)\to P(B)$ פונקציה מונוטונית. נסמן ב-K את האיחוד של כל הקבוצות C המקיימות את התנאי $C\subseteq F(C)$ (כלומר, איבר $a\in A$ שייך ל-K אם ורק אם יש תת-קבוצה C של A המקיימת $a\in C\subseteq F(C)$). אז $K=F(K)$.

הוכחה. נסמן ב- (*) את התנאי $C\subseteq F(C)$. נראה ש-K עצמה מקיימת את התנאי. אכן, כל נקודה $x\in K$ שייכת לקבוצה $C$ המקיימת את התנאי (*), ולכן מוכלת ב-K; אבל אז $x\in F(C)\subseteq F(K)$. לפי המונוטוניות, מ- $K\subseteq F(K)$ נובע שגם $F(K)\subseteq F(F(K))$; אבל אז הקבוצה $F(K)$ עצמה מקיימת את התנאי (*), ולפי הגדרת K (שהיא איחוד כל הקבוצות האלה) היא מוכלת ב-K. לכן $K=F(K)$.

משפט קנטור-ברנשטיין. אם $|A|\le |B|$ ו- $|B|\le |A|$ אז $|A|=|B|$.

הוכחה.

1. לפי ההנחה, יש פונקציות חד-חד-ערכיות $f:A\to B$ ו- $g:B\to A$. נגדיר פונקציה $\mathrm{\Delta }:P(A)\to P(A)$ לפי $\mathrm{\Delta }(C)=A-g(B-f(C))$. קל לראות שהפונקציה הזו היא מונוטונית: אם $C\subseteq C^{\prime }$ תת-קבוצות של A, אז $\mathrm{\Delta }(C)\subseteq \mathrm{\Delta }(C^{\prime })$ מכיוון שהפעלת הפונקציות f ו-g שומרת על סדר ההכלה, ופעולת המשלים (המבוצעת כאן פעמיים) הופכת אותה.
2. נסמן ב- K את איחוד הקבוצות C המקיימות $C\subseteq \mathrm{\Delta }(C)$. (תרגיל, שאינו נחוץ להמשך: $C\subseteq \mathrm{\Delta }(C)$ אם לכל $x\in ̸f(C)$ מתקיים $g(x)\in ̸C$).
3. לפי הלמה, $K=\mathrm{\Delta }(K)$.
4. השוויון $K=\mathrm{\Delta }(K)=A-g(B-f(K))$ נותן $A-K=g(B-f(K))$, ומכיוון ש-g חד-חד-ערכית, יוצא ש- $|A-K|=|B-f(K)|$. והרי גם $|K|=|f(K)|$, ולכן $|A|=|A-K|+|K|=|B-f(K)|+|f(K)|=|B|$.

<< השיעור הקודם - קבוצות בנות מנייה

דף הקורס - תורת הקבוצות

השיעור הבא - משפט קנטור >>