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

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

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

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

הוכחות של המשפט

עריכה

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

הוכחה באמצעות סיווג של האיברים

עריכה

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

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

 

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

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

בניה ישירה של ההתאמה

עריכה

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

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

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

הוכחה באמצעות למת נקודת השבת

עריכה

מסמנים ב-  את קבוצת החזקה של  . נשתמש בלמה הבאה:

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

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

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

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

עריכה

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

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

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

 

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

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

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

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

ראו גם

עריכה

קישורים חיצוניים

עריכה