【定理】（Bernsteinの定理）
集合\(A,B\)について、単射\(f:A\rightarrow B\)と単射\(g:B\rightarrow A\)が存在するとき、全単射\(h:A\rightarrow B\)が存在する。
（証明）以下、自然数全体の集合\(\mathbb{N}\)には\(0\)も属すとする。
\(\displaystyle C=\bigcup_{n\in\mathbb{N}}(g\circ f)^n[A\backslash g[B]]\)とおき、\(h(x)=\begin{cases}f(x)\quad(x\in C)\\g^{-1}(x)\quad(x\notin C)\end{cases}\)によって写像\(h:A\rightarrow B\)を定める。ただし\(g^{-1}\)は全単射\(B\rightarrow g[B],\ x\mapsto g(x)\)の逆写像\(g[B]\rightarrow B\)であり、いま\(A\backslash g[B]\subset C\)すなわち\(A\backslash C\subset g[B]\)が成り立っているので、上の\(h(x)\)はきちんと写像の定義になっている。この\(h\)が全単射であることを示す。
(1)単射性：\(h(x_1)=h(x_2)\)を満たす任意の\(x_1,x_2\in A\)をとり、\(x_1=x_2\)であることを導く。
\(x_1\in C\)かつ\(x_2\notin C\)と仮定すると、\(f(x_1)=g^{-1}(x_2)\)の両辺を\(g\)で移すことにより\((g\circ f)(x_1)=x_2\)が得られるが、\(x_1\in C\)と\(C\)の定義から左辺は\(C\)に属し、いっぽう右辺は\(C\)に属さない。同様の矛盾は\(x_1\)と\(x_2\)を入れ替えても生じるので、\(x_1,x_2\)はともに\(C\)に属すか、あるいはどちらも\(C\)に属さないことになる。いずれにせよ\(f\)や\(g^{-1}\)の単射性により\(x_1=x_2\)である。
(2)全射性：任意の\(b\in B\)をとり、\(h(a)=b\)を満たす\(a\in A\)が存在することを導く。
(ア)\(g(b)\notin C\)のとき：\(h(g(b) )=g^{-1}(g(b) )=b\)となる。
(イ)\(g(b)\in C\)のとき：\(g(b)\in(g\circ f)^m[A\backslash g[B]]\)なる\(m\in \mathbb{N}\)が存在するが、\(g(b)\notin A\backslash g[B]\)であるから、この\(m\)は\(1\)以上であり、\(m=n+1(n\in\mathbb{N})\)とおける。すると\(g(b)=(g\circ f)^{n+1}(p)\)なる\(p\in A\backslash g[B]\)が存在するので、そのひとつをとって\(a=(g\circ f)^n(p)\)とおけば\(g(b)=(g\circ f)(a)\)である。いま\(g\)は単射だから\(b=f(a)\)であり、いっぽう\(a\)の定め方から\(a\in C\)なので、この\(a\)が\(h(a)=f(a)=b\)を満たす。■
