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

אם <math>|A|\le|B|</math> וגם <math>|A|\ge|B|</math> אזי <math>|A|=|B|</math>.

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

== הוכחה ==
הוכחה זו מסתמכת על [[הוכחות_מתמטיות/תורת הקבוצות/למת נקודת השבת|למת נקודת השבת]].

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

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

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

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