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

From Wikiversity

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

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

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

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

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

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

דוגמאות.

  1. אם אז בוודאי .
  2. לכל תת-קבוצה מתקיים .
  3. בעבר הוכחנו שאם A אינסופית, אז .

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

הערה. אם ו- אז .

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

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

אם קבוצות, פונקציה היא מונוטונית, אם לכל שתי תת-קבוצות של A, מתקיים .

למה. תהי פונקציה מונוטונית. נסמן ב-K את האיחוד של כל הקבוצות C המקיימות את התנאי (כלומר, איבר שייך ל-K אם ורק אם יש תת-קבוצה C של A המקיימת ). אז .

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

משפט קנטור-ברנשטיין. אם ו- אז .

הוכחה.

  1. לפי ההנחה, יש פונקציות חד-חד-ערכיות ו- . נגדיר פונקציה לפי . קל לראות שהפונקציה הזו היא מונוטונית: אם תת-קבוצות של A, אז מכיוון שהפעלת הפונקציות f ו-g שומרת על סדר ההכלה, ופעולת המשלים (המבוצעת כאן פעמיים) הופכת אותה.
  2. נסמן ב- K את איחוד הקבוצות C המקיימות . (תרגיל, שאינו נחוץ להמשך: אם לכל מתקיים ).
  3. לפי הלמה, .
  4. השוויון נותן , ומכיוון ש-g חד-חד-ערכית, יוצא ש- . והרי גם , ולכן .






<< השיעור הקודם - קבוצות בנות מנייה דף הקורס - תורת הקבוצות השיעור הבא - משפט קנטור >>