Schoder-Bernstein Theorem

這個定理說明了兩件事

(a) 如果存在一個一對一函數$f$將$A$的元素對應到$B$且存在一對一函數$g$將$B$的元素對應到$A$，則存在一對一且映成函數$h$將$A$的元素對應到$B$。
(b) 對基數$\kappa$和$\lambda$，如果$\kappa\le\lambda$且$\lambda\le\kappa$，則$\kappa=\lambda$。

之中，(b)是(a)的應用。

(a) 的部份證明分成三個步驟：
(1) 造出這個函數$h$，
(2) 證明這個函數$h$是一對一，
(3) 證明這個函數$h$是映成。

(1)造出這個函數$h$：
令$C_{0} = A - ran g$ 與 $C_{n^{+}} = g[f[C_{n}]]$。
在$C_{0}$上的元素$x$透過一對一函數$f$對到$f(x)$，而那$f(x)$又會透過一對一函數$g$對到$g(f(x))$，我們稱呼這些$g(f(x))$為$C_{1}$，用同樣的手法，我們可以繼續獲得$C_{2}$、$C_{3}$等等。

接著我要說明當$m\not=n$時，$C_{m}\not=C_{n}$。
(i)$m$跟$n$相差1的情形：因為在$C_{0}$上的$x$都不屬於ran $g$，不可能$x=g(f(x))$。因此$C_{0}\not=C_{1}$。
因為$g$跟$f$都是一對一，$g[f[C_{0}]]\not=g[f[C_{1}]]$，因此$C_{1}\not=C_{2}$，類似的作法，當$m$跟$n$相差$1$時，$C_{m}\not=C_{n}$。

(ii)$m$跟$n$相差2的情形：因為在$C_{0}$上的$x$都不屬於ran $g$，不可能$x=g(f(g(f(x))))$。因此$C_{0}\not=C_{2}$。
因為$g$跟$f$都是一對一，$g[f[C_{0}]]\not=[g[f[C_{2}]]$，因此$C_{1}\not=C_{3}$，類似的作法，當$m$跟$n$相差$2$時，$C_{m}\not=C_{n}$。

(iii)類似的作法，無論$m$跟$n$相差多少，$C_{m}\not=C_{n}$。

令，
\[h(x) = \left\{\begin{array}{ll}
f(x), & \mbox{if $x\in C_{n}$ for some n}, \\
g^{-1}(x), & \mbox{otherwise.}
\end{array} \right.\]

接著要證明這個函數$h$符合我們的要求。

(2)證明這個函數$h$是一對一：
我們先定義$D_{n}=f[C_{n}]$，意思是$D_{n}$上的元素都是由限制$C_{n}$上的元素透過函數$f$對應來的，因為$C_{n^{+}} = g[f[C_{n}]]$，所以$C_{n^{+}}=g[D_{n}]$。

要證明$h$是一對一，根據定義：如果$x\not=x'$，那麼$h(x)\not=h(x')$。
關於$x\not=x'$又分成三種情形考慮：
(i)$x$與$x'$都屬於某個$C_{m}$
(ii)$x$與$x'$都不屬於某個$C_{m}$
(iii)$x$屬於某個$C_{m}$，但$x'$不屬於某個$C_{m}$。

對於(i)跟(ii)的情形因為$f$跟$g^{-1}$都是一對一所以顯而易見，不容易看出的只有(iii)的情形。在此情形下，因為$x$屬於某個$C_{m}$，所以$h(x)=f(x)\in D_{m}$，而$x'$不屬於某個$C_{m}$，所以$h(x')=g^{-1}(x')\not\in D_{m}$。既然一個屬於$D_{m}$而另一個不屬於$D_{m}$兩個當然不會相同。
當$x\not=x'$時，$f(x)\not=f(x')$，因此$h$是一對一函數。

(3)證明這個函數$h$是映成：這意思是說$B$上的所有元素都在$g$的值域裡面，
而$B$上的所有元素我們又可以區分成兩個部份：
(i)屬於某個$D_{m}$的
(ii)不屬於任何一個$D_{m}$的。

對於(i)假設元素$y$屬於某個$D_{m}$，因為$D_{m}=f[C_{m}]$，當$x$落在某個$C_{m}$時$f(x)=h(x)$，所以$x$也會落在$h$的值域上。
對於(ii)假設元素$y$不屬於任何一個$D_{m}$，那麼$g(y)$也不會屬於任何一個$C_{m}$，而既然$g(y)$不屬於任何一個$C_{m}$，$h(g(y))=g^{-1}(g(y))=y$，所以這個$y$還是落在$g$的值域上。
所有屬於$B$的元素都屬於ran$g$因此，$h$是映射。

根據(1)(2)(3)，我們可以證明出這個理論的(a)部份。

至於(b)部份是伴隨著(a)而來的，因為「存在一對一函數$f$將$A$的元素對應到$B$」等價於「$A$的基數小於或等於$B$的基數」，「存在一對一且映成函數$f$將$A$的元素對應到$B$」等價於「$A$的基數等於$B$的基數」