משפט קנטור-שרדר-ברנשטיין
בתורת הקבוצות, משפט קנטור-שרדר-ברנשטיין אומר כך:
תהיינה קבוצות. אם קיימת פונקציה חד-חד-ערכית וקיימת פונקציה חד-חד-ערכית , אז קיימת פונקציה חד-חד-ערכית ועל , כלומר שתי הקבוצות שקולות – עוצמתן זהה.
ניתן לנסח את המשפט בכתיב עוצמות כך: אם וגם אז .
חשיבותו הרבה של המשפט היא בכך שהוא מראה כי בין העוצמות השונות קיים יחס סדר (המשפט מראה כי היחס אנטי-סימטרי), המוגדר על ידי קיום התאמות חד-חד-ערכיות.
לעומת עוצמות סופיות (המספרים הטבעיים), שם יחס הסדר הוא גם ברור ומובן אינטואיטיבית, יחס הסדר בעוצמות אינסופיות לא תמיד ברור (למשל: עוצמת הרציונלים שווה לעוצמת השלמים, השווה לעוצמת הטבעיים, זאת למרות ההכלה ממש) ומשפט זה מוכיח שאכן קיים יחס סדר שכזה. המשפט מוכיח כי היחס הוא סדר חלקי. בעזרת אקסיומת הבחירה ניתן להוכיח שהיחס הוא גם סדר מלא, כלומר לכל שתי עוצמות מתקיים או .
המשפט מכונה גם "למת הסנדוויץ'". כינוי זה בא מניסוח שקול: "אם וגם אז " בדומה לכלל הסנדוויץ'.
הוכחת המשפט
נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל .
נניח כי פונקציה חד-חד-ערכית, ו- פונקציה חד-חד-ערכית. כמו כן נניח, ללא הגבלת הכלליות שהקבוצות זרות.
נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר וכל איבר סדרת איברים מ- לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר הקודם לו:
נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר שהפונקציות לא מוגדרות לכל איברי בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף.
הסדרות יכולות להסתיים משמאל באיבר של , להסתיים משמאל באיבר של , או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כסדרות קצה- , סדרות קצה- או סדרות ללא קצה בהתאמה. כמו כן, נשים לב שלכל איבר מכל אחת מהקבוצות קיימת רק סדרה אחת מתאימה מצורה זו.
כעת, נבנה את הפונקציה החד-חד-ערכית ועל :
- עבור איברי השייכים לסדרת קצה- , נגדיר (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר).
- עבור איברי השייכים לסדרת קצה- , נגדיר את (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר)
- ובאותו אופן נגדיר גם את עבור איברי השייכים לסדרה ללא קצה.
קל לראות שהפונקציה היא אכן חד-חד-ערכית ועל.
דוגמה לשימוש במשפט
נחשב את (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם):
ראשית נשים לב שמתקיים
כי כל פונקציה מהטבעיים לקבוצה היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.
פונקציית הזהות היא תמיד חד-חד-ערכית, ולכן אם קבוצה מוכלת בקבוצה אחרת אז עוצמתה לא גדולה ממנה. מכאן:
לפי ההגדרה המוכללת לחזקה, אי-השוויון הנ"ל שקול:
כאשר: אלף 0, עוצמת הרצף.
אבל מתקיים וכמו כן, על פי חוקי החזקות:
(להוכחת השוויון ראה כאן)
לכן , ועל פי משפט קנטור-שרדר-ברנשטיין נקבל .
ראו גם
נושאים בתורת הקבוצות | ||
---|---|---|
מושגי יסוד | תורת הקבוצות הנאיבית • תורת הקבוצות האקסיומטית • קבוצה • יחידון • הקבוצה הריקה • קבוצת החזקה | |
עוצמות | עוצמה • קבוצה בת מנייה • קבוצה שאינה בת מנייה • עוצמת הרצף | |
פעולות | איחוד • חיתוך • משלים • הפרש סימטרי • מכפלה קרטזית | |
אקסיומות | אקסיומת ההיקפיות • אקסיומת האיחוד • אקסיומת הקבוצה האינסופית • אקסיומת ההחלפה • אקסיומת קבוצת החזקה • אקסיומת היסוד • אקסיומת הבחירה • השערת הרצף | |
משפטים | האלכסון של קנטור • משפט קנטור-שרדר-ברנשטיין • הלמה של צורן • משפט הסדר הטוב | |
פונקציות | פונקציה • פונקציה חד-חד-ערכית • פונקציה על • פונקציה חד-חד-ערכית ועל • פונקציית הזיווג של קנטור | |
יחסים | יחס • יחס רפלקסיבי • יחס סימטרי • יחס טרנזיטיבי • יחס שקילות • סדר חלקי • יחס הופכי • יחס אנטי-סימטרי | |
סדר | סדר מלא • סדר טוב • סדר חלקי • טיפוס סדר • מספר סודר | |
שונות | הפרדוקס של ראסל |