Bernsteinの定理(改)

前エントリの証明を、\(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^*\)が全単射であることを示す。
(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\)と仮定すると、\((g\circ f)(x_1)=x_2\)となるが、\(x_1\in C\)と\(C\)の定義から左辺は\(C\)に属し、いっぽう右辺は\(C\)に属さない。同様の矛盾は\(x_1\)と\(x_2\)を入れ替えても生じるので、\(x_1,x_2\)はともに\(C\)に属すか、あるいはどちらも\(C\)に属さないことになる。したがって\((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\)を満たす。■