מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
אם
|
A
|
≤
|
B
|
{\displaystyle |A|\leq |B|}
|
A
|
≥
|
B
|
{\displaystyle |A|\geq |B|}
|
A
|
=
|
B
|
{\displaystyle |A|=|B|}
כלומר, אם קיימת פונקצייה חד-חד-ערכית מהקבוצה
A
{\displaystyle A}
B
{\displaystyle B}
B
{\displaystyle B}
A
{\displaystyle A}
A
{\displaystyle A}
B
{\displaystyle B}
הוכחה זו מסתמכת על למת נקודת השבת .
לפי הנתון קיימות
f
:
A
→
B
{\displaystyle f\colon A\to B}
g
:
B
→
A
{\displaystyle g\colon B\to A}
נגדיר פונקצייה חדשה
F
:
P
(
A
)
→
P
(
A
)
{\displaystyle F\colon P(A)\to P(A)}
F
(
X
)
=
A
∖
g
[
B
∖
f
[
X
]
]
{\displaystyle F(X)=A\setminus g[B\setminus f[X]]}
X
,
Y
∈
P
(
A
)
{\displaystyle X,Y\in P(A)}
X
⊆
Y
{\displaystyle X\subseteq Y}
f
[
X
]
⊆
f
[
Y
]
{\displaystyle f[X]\subseteq f[Y]}
f
{\displaystyle f}
B
∖
f
[
X
]
⊇
B
∖
f
[
Y
]
{\displaystyle B\setminus f[X]\supseteq B\setminus f[Y]}
g
[
B
∖
f
[
X
]
]
⊇
g
[
B
∖
f
[
Y
]
]
{\displaystyle g[B\setminus f[X]]\supseteq g[B\setminus f[Y]]}
g
{\displaystyle g}
F
(
X
)
=
A
∖
g
[
B
∖
f
[
X
]
]
⊆
A
∖
g
[
B
∖
f
[
Y
]
]
=
F
(
Y
)
{\displaystyle F(X)=A\setminus g[B\setminus f[X]]\subseteq A\setminus g[B\setminus f[Y]]=F(Y)}
לפי למת נקודת השבת קיימת
Z
∈
P
(
A
)
{\displaystyle Z\in P(A)}
Z
=
F
(
Z
)
=
A
∖
g
[
B
∖
f
[
Z
]
]
{\displaystyle Z=F(Z)=A\setminus g[B\setminus f[Z]]}
A
∖
Z
=
g
[
B
∖
f
[
Z
]
]
{\displaystyle A\setminus Z=g[B\setminus f[Z]]}
g
:
B
∖
f
[
Z
]
→
A
∖
Z
{\displaystyle g\colon B\setminus f[Z]\to A\setminus Z}
g
−
1
:
A
∖
Z
→
B
∖
f
[
Z
]
{\displaystyle g^{-1}\colon A\setminus Z\to B\setminus f[Z]}
כעת נוכל להגדיר את פונקציית השקילות
φ
:
A
→
B
{\displaystyle \varphi \colon A\to B}
φ
(
a
)
=
{
f
(
a
)
a
∈
Z
g
−
1
(
a
)
a
∈
A
∖
Z
{\displaystyle \varphi (a)={\begin{cases}f(a)&a\in Z\\g^{-1}(a)&a\in A\setminus Z\end{cases}}}
φ
[
Z
]
=
f
[
Z
]
{\displaystyle \varphi [Z]=f[Z]}
φ
[
A
∖
Z
]
=
g
−
1
[
A
∖
Z
]
=
B
∖
f
[
Z
]
{\displaystyle \varphi [A\setminus Z]=g^{-1}[A\setminus Z]=B\setminus f[Z]}
φ
[
A
]
=
f
[
Z
]
∪
(
B
∖
f
[
Z
]
)
=
B
{\displaystyle \varphi [A]=f[Z]\cup (B\setminus f[Z])=B}
φ
{\displaystyle \varphi }
Z
{\displaystyle Z}
f
{\displaystyle f}
A
∖
Z
{\displaystyle A\setminus Z}
g
−
1
{\displaystyle g^{-1}}
φ
{\displaystyle \varphi }
![{\displaystyle F(X)=A\setminus g[B\setminus f[X]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e135468a2e93b238a5340457f8b3110dc768c44)
![{\displaystyle f[X]\subseteq f[Y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95bcfa55001dac055dfa9f907b4c6399c0b8f40b)
![{\displaystyle B\setminus f[X]\supseteq B\setminus f[Y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddf96d9b85c3e63476ac7c3a4316050e92471a89)
![{\displaystyle g[B\setminus f[X]]\supseteq g[B\setminus f[Y]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e7335ef045a03a922558e41aebf38a5824bc775)
![{\displaystyle F(X)=A\setminus g[B\setminus f[X]]\subseteq A\setminus g[B\setminus f[Y]]=F(Y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/622f2aebef1a06dc3e2fe97341178be17808f68e)
![{\displaystyle Z=F(Z)=A\setminus g[B\setminus f[Z]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fff6d9bd359124290d04a2731fbda860aee1ab6)
![{\displaystyle A\setminus Z=g[B\setminus f[Z]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47099b5296a9fbebbb261d264ef539b7e98f737c)
![{\displaystyle g\colon B\setminus f[Z]\to A\setminus Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4f45a7c5322b4d8aeab133e8d86f8b459988aaa)
![{\displaystyle g^{-1}\colon A\setminus Z\to B\setminus f[Z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d193884f38af22c35117bdbf13d9b1b338e0c3d)
![{\displaystyle \varphi [Z]=f[Z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5504fec897531624e65ddfdc95218104eed3fd1f)
![{\displaystyle \varphi [A\setminus Z]=g^{-1}[A\setminus Z]=B\setminus f[Z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c9313b95fafaa3950cc5205969b906784f9022d)
![{\displaystyle \varphi [A]=f[Z]\cup (B\setminus f[Z])=B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6cb56b7e7ad53b5e842bbef50e360c993f8993d)
