Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
משפט קנטור-שרדר-ברנשטיין בתורת הקבוצות אומר שאם קיימת פונקציה חד-חד-ערכית מקבוצה לקבוצה , וקיימת פונקציה חד-חד-ערכית מהקבוצה לקבוצה , אז קיימת פונקציה שהיא גם חד-חד-ערכית וגם על מהקבוצה לקבוצה , כלומר שתי הקבוצות שקולות – עוצמתן זהה. המשפט נקרא על שם גאורג קנטור, ארנסט שרדר ופליקס ברנשטיין.
בכתיב עוצמות ניתן לנסח את המשפט כך: אם וגם אז . המשפט מכונה גם "למת הסנדוויץ'" (משום שהוא מסיק מאי-השוויונות את שוויון העוצמות).
חשיבותו הרבה של המשפט היא בכך שהוא מראה שהיחס " אם יש פונקציה חד-חד-ערכית מ- ל-" הוא יחס יחס אנטי-סימטרי. ברור שהיחס הזה טרנזיטיבי, ואם כך הוא מהווה יחס סדר חלש. כדי להוכיח שהיחס הוא יחס סדר מלא, כלומר שלכל שתי עוצמות מתקיים או , דרושה אקסיומת הבחירה.
נניח ש- היא פונקציה חד-חד-ערכית מ- ל-, וש- היא פונקציה חד-חד-ערכית מ- ל-. נציג כמה הוכחות של המשפט, המבוססות כולן, בדרכים שונות, על חלוקה של אחת הקבוצות לשני חלקים ושימוש ב- עבור אחד מהחלקים וב- עבור השני כדי להגדיר את הבייקציה בין הקבוצות.
נוכיח את המשפט על ידי בניית פונקציה חד-חד-ערכית ועל מ־ ל־.
נניח, ללא הגבלת הכלליות שהקבוצות ו- זרות. נראה שקיימת התאמה חד-חד-ערכית ועל בין שתי הקבוצות. נבנה עבור כל איבר של הקבוצה , וכל איבר של הקבוצה , סדרת איברים מ- ומ- לסירוגין, כך שכל איבר מתקבל על ידי החלת הפונקציה החד-חד-ערכית המתאימה על האיבר שקודם לו:
נשים לב שניתן להמשיך את הסדרה ימינה ללא סוף, אך מאחר ש- ו- לא מוגדרות לכל איברי ו- בהתאמה, לא בהכרח ניתן להמשיך את הסדרה שמאלה עד אינסוף. הסדרות יכולות להסתיים משמאל באיבר של , להסתיים משמאל באיבר של , או להיות אינסופיות (או מעגליות) לשני הכיוונים. נסווג את הסדרות כסדרות קצה-, סדרות קצה- או סדרות ללא קצה בהתאמה. מכיוון ש- ו- הן פונקציות חד-חד-ערכיות, לכל איבר בכל אחת מהקבוצות קיימת רק סדרה אחת כזו עד כדי זהות: אם איבר מופיע בשתי סדרות, כל האיברים מימינו ומשמאלו חייבים להיות זהים בשתיהן. הסדרות יוצרות חלוקה של האיחוד של ו-. לכן מספיק לבנות פונקציה חד-חד-ערכית ועל מ- ל- בכל אחת מהסדרות בנפרד.
כעת, נבנה את הפונקציה החד-חד-ערכית ועל מ- ל-: עבור איברי ששייכים לסדרת קצה-, נגדיר את כ- (כלומר, נלך צעד אחד ימינה בסדרה המתאימה לאיבר). עבור איברי ששייכים לסדרת קצה-, נגדיר את כ- (כלומר, נלך צעד אחד שמאלה בסדרה המתאימה לאיבר), ובאותו אופן נגדיר גם את עבור איברי ששייכים לסדרה ללא קצה. קל לראות שהפונקציה היא אכן חד-חד-ערכית ועל.
נחליף את הקבוצה בתמונה שלה , שהיא ממילא שוות עוצמה ל- משום ש- חד-חד-ערכית.
כעת אפשר להניח ש- ונתונה פונקציה חד-חד-ערכית ; עלינו לבנות פונקציה כזו שהיא חד-חד-ערכית ועל. נסמן ב- את ההרכבה של על עצמה פעמים (כאשר היא פונקציית הזהות). נאמר שאיבר הוא מסוג ראשון אם קיימים ו- כך ש-, ומסוג שני אחרת. נגדיר פונקציה באופן הבא: אם מסוג ראשון, ו- אחרת. כעת נוכיח כמה טענות קלות:
מסמנים ב- את קבוצת החזקה של . נשתמש בלמה הבאה:
למה: תהי פונקציה שומרת הכלה (כלומר, אם אז ). אז יש לה נקודת שבת (כלומר קבוצה כך ש-).
הוכחה |
---|
נתבונן באוסף של כל הקבוצות כך ש- . (זהו אוסף לא ריק כי הקבוצה הריקה מקיימת את התנאי). נסמן ב- את איחוד כל הקבוצות באוסף. לכל יש כך ש- ואז , כלומר . הוכחנו, אם כך, ש-. מכיוון ש- שומרת הכלה, מתקיים , כלומר , ולפי ההגדרה של כאיחוד, . לכן היא נקודת שבת. |
כעת נבחר . ברור שהפונקציה הזו שומרת הכלה, ולפי הלמה יש לה נקודת שבת, שנסמן ב-. מכיוון ש-, קיבלנו ש-, ולכן .
נחשב את (כלומר עוצמת קבוצת הפונקציות מהטבעיים לעצמם, שמסומנת גם ):
ראשית נשים לב שמתקיים כי כל פונקציה מהטבעיים לקבוצה היא בפרט פונקציה מהטבעיים לטבעיים, וכל פונקציה מהטבעיים לטבעיים היא בפרט פונקציה מהטבעיים לממשיים.
פונקציית הזהות היא תמיד חד-חד-ערכית, ולכן אם קבוצה מוכלת בקבוצה אחרת אז עוצמתה לא גדולה ממנה. מכאן:
לפי ההגדרה המוכללת לחזקה, האי שוויון הנ"ל שקול ל:
(כאשר היא אָלֶף אֶפֶס ו- היא עוצמת הרצף)
אבל מתקיים וכמו כן, על פי חוקי החזקות: (להוכחת השוויון , ראו כאן)
לכן , ועל פי משפט קנטור-שרדר ברנשטיין נקבל , משמע קיבלנו .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.