לדלג לתוכן

הוכחות מתמטיות/תורת הקבוצות/משפט קנטור-שרדר-ברנשטיין

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

אם וגם אזי .

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

הוכחה

[עריכה]

הוכחה זו מסתמכת על למת נקודת השבת.

לפי הנתון קיימות ו- שהינן חח"ע.

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

, כי פונקציה.
כנדרש.

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

כעת נוכל להגדיר את פונקציית השקילות באופן הבא:

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