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

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

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

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

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

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

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

דוגמאות.

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

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

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

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

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

אם $\ A,B$ קבוצות, פונקציה $\ F:P(A)\rightarrow P(B)$ היא מונוטונית, אם לכל שתי תת-קבוצות $\ A_{0}\subseteq A_{1}$ של A, מתקיים $\ F(A_{0})\subseteq F(A_{1})$.

למה. תהי $\ F:P(A)\rightarrow 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|\leq |B|$ ו- $\ |B|\leq |A|$ אז $\ |A|=|B|$.

הוכחה.

1. לפי ההנחה, יש פונקציות חד-חד-ערכיות $\ f:A\rightarrow B$ ו- $\ g:B\rightarrow A$. נגדיר פונקציה $\ \Delta :P(A)\rightarrow P(A)$ לפי $\ \Delta (C)=A-g(B-f(C))$. קל לראות שהפונקציה הזו היא מונוטונית: אם $\ C\subseteq C'$ תת-קבוצות של A, אז $\ \Delta (C)\subseteq \Delta (C')$ מכיוון שהפעלת הפונקציות f ו-g שומרת על סדר ההכלה, ופעולת המשלים (המבוצעת כאן פעמיים) הופכת אותה.
2. נסמן ב- K את איחוד הקבוצות C המקיימות $\ C\subseteq \Delta (C)$. (תרגיל, שאינו נחוץ להמשך: $\ C\subseteq \Delta (C)$ אם לכל $\ x\not \in f(C)$ מתקיים $\ g(x)\not \in C$).
3. לפי הלמה, $\ K=\Delta (K)$.
4. השוויון $\ K=\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|$.

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

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

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