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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

הוכחות של המשפט[עריכת קוד מקור | עריכה]

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

הוכחה באמצעות סיווג של האיברים[עריכת קוד מקור | עריכה]

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

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

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

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

בניה ישירה של ההתאמה[עריכת קוד מקור | עריכה]

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

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

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

הוכחה באמצעות למת נקודת השבת[עריכת קוד מקור | עריכה]

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

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

דוגמה לשימוש במשפט[עריכת קוד מקור | עריכה]

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

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

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

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

(כאשר היא אָלֶף אֶפֶס ו- היא עוצמת הרצף)

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]