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

אם $|A|\leq |B|$ וגם $|A|\geq |B|$ אזי $|A|=|B|$.

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

הוכחה

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

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

נגדיר פונקצייה חדשה $F\colon 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\colon B\setminus f[Z]\to A\setminus Z$ חח"ע ועל, ולכן קיימת ההופכית $g^{-1}\colon A\setminus Z\to B\setminus f[Z]$ שהינה חח"ע ועל גם כן.

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