前エントリの証明を、\(A\rightarrow B\)でなく\(A\rightarrow g[B]\)の全単射を構成する方法に変えただけの証明。\(g^{-1}\)が登場しないのでちょっとだけ簡明かもしれない。
【定理】（Bernsteinの定理）
集合\(A,B\)について、単射\(f:A\rightarrow B\)と単射\(g:B\rightarrow A\)が存在するとき、全単射\(h:A\rightarrow B\)が存在する。
（証明）以下、自然数全体の集合\(\mathbb{N}\)には\(0\)も属すとする。
\(g\)の単射性から、\(B\)と\(g[B]\)の間には全単射が存在する。そこで、\(A\)から\(g[B]\)への全単射が存在することを示せばよい。
\(\displaystyle C=\bigcup_{n\in\mathbb{N}}(g\circ f)^n[A\backslash g[B]]\)とおき、\(h^*(x)=\begin{cases}(g\circ f)(x)\quad(x\in C)\\x\quad(x\notin C)\end{cases}\)とする。\(A\backslash g[B]\subset C\)すなわち\(A\backslash C\subset g[B]\)が成り立っているので、\(x\in C\)か否かにかかわらず\(h^*(x)\in g[B]\)となり、\(h^*\)は\(A\)から\(g[B]\)への写像になっている。この\(h^*\)が全単射であることを示す。なお\(h^*\)および\(C\)の定義から、\(A\)のいかなる元も、\(h^*\)でうつされることによって「\(C\)に属すか否か」が変わることはない。以下ではこの性質が重要となる。
(1)単射性：\(h^*(x_1)=h^*(x_2)\)を満たす任意の\(x_1,x_2\in A\)をとると、上記の性質から\((g\circ f)(x_1)=(g\circ f)(x_2)\)あるいは\(x_1=x_2\)が成り立つが、\(f,g\)は単射だから\(g\circ f\)も単射であり、いずれにせよ\(x_1=x_2\)となる。
(2)全射性：任意の\(d\in g[B]\)をとり、\(h^*(a)=d\)を満たす\(a\in A\)が存在することを導く。
(ア)\(d\notin C\)のとき：\(h^*(d)=d\)となる。
(イ)\(d\in C\)のとき：\(d\in(g\circ f)^m[A\backslash g[B]]\)なる\(m\in \mathbb{N}\)が存在するが、\(d\notin A\backslash g[B]\)であるから、この\(m\)は\(1\)以上であり、\(m=n+1(n\in\mathbb{N})\)とおける。すると\(d=(g\circ f)^{n+1}(p)\)なる\(p\in A\backslash g[B]\)が存在するので、そのひとつをとって\(a=(g\circ f)^n(p)\)とおけば\(d=(g\circ f)(a)\)である。\(a\)の定め方から\(a\in C\)なので、この\(a\)が\(h^*(a)=(g\circ f)(a)=d\)を満たす。■
