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

אם $|A|\le |B|$ וגם $|A|\ge |B|$ אזי $|A|=|B|$.

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

הוכחה

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

לפי הנתון קיימות $f:A\to B$ ו-$g:B\to A$ שהינן חח"ע.

נגדיר פונקצייה חדשה $F:P(A)\to P(A)$ באופן הבא: $F(X)=A\setminus g[B\setminus f[X]]$.
נוכיח שהיא שומרת הכלה:
תהיינה $X,Y\in P(A)$ כך ש-$X\subseteq Y$.
$f[X]\subseteq f[Y]$, כי $f$ פונקציה.
$B\setminus f[X]\supseteq B\setminus f[Y]$
$g[B\setminus f[X]]\supseteq g[B\setminus f[Y]]$, כי $g$ פונקציה.
$F(X)=A\setminus g[B\setminus f[X]]\subseteq A\setminus g[B\setminus f[Y]]=F(Y)$ כנדרש.

לפי למת נקודת השבת קיימת $Z\in P(A)$ עבורה $Z=F(Z)=A\setminus g[B\setminus f[Z]]$, ולכן מתקיים $A\setminus Z=g[B\setminus f[Z]]$.
מכאן נובע ש-$g:B\setminus f[Z]\to A\setminus Z$ חח"ע ועל, ולכן קיימת ההופכית $g^{-1}:A\setminus Z\to B\setminus f[Z]$ שהינה חח"ע ועל גם כן.

כעת נוכל להגדיר את פונקציית השקילות $\phi :A\to B$ באופן הבא:
$\phi (a)=\{\begin{array}{cc}f(a)& a\in Z\\ g^{-1}(a)& a\in A\setminus Z\end{array}$
נשים לב כי $\phi [Z]=f[Z]$ וכמו כן $\phi [A\setminus Z]=g^{-1}[A\setminus Z]=B\setminus f[Z]$, ולכן היא על: $\phi [A]=f[Z]\cup (B\setminus f[Z])=B$.
בנוסף $\phi$ חח"ע, כי הינה חח"ע בתחום $Z$ (כי $f$ חח"ע) ובתחום $A\setminus Z$ (כי $g^{-1}$ חח"ע), והטווחים של שני התחומים הללו זרים.
בסך הכל קיבלנו כי $\phi$ הינה פונקציית שקילות כנדרש.