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

מתוך המכלול
קפיצה אל: ניווט, חיפוש

בתורת הקבוצות, משפט קנטור-שרדר-ברנשטיין אומר כך:

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

ניתן לנסח את המשפט בכתיב עוצמות כך: אם וגם אז .

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

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

המשפט מכונה גם "למת הסנדוויץ'". כינוי זה בא מניסוח שקול: "אם וגם אז " בדומה לכלל הסנדוויץ'.

הוכחת המשפט

Cantor-Bernstein.png

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

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

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

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

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

כעת, נבנה את הפונקציה החד-חד-ערכית ועל  :

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

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

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

נחשב את (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם):

ראשית נשים לב שמתקיים

כי כל פונקציה מהטבעיים לקבוצה היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.

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

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

כאשר: אלף 0, עוצמת הרצף.

אבל מתקיים וכמו כן, על פי חוקי החזקות:

(להוכחת השוויון ראה כאן)

לכן , ועל פי משפט קנטור-שרדר-ברנשטיין נקבל .

ראו גם