Bernsteinの定理

AからBへの単射が存在し、BからAへの単射も存在すれば、

対等であることを、全単射な写像を具体的に用意しないでも示せる

証明

仮定

fをAからBへの単射

gをBからAへの単射とする

AからBへの全単射Fの存在を示す

fが全射なら、fが求めるFである

よって以下ではfが全射でないとする

次に、以下のようなA及びBの部分集合族を考える

$ g(B_0) = A_1, f(A_1) = B_1

$ g(B_1) = A_2, f(A_2) = B_2

...

$ g(B_{n-1}) = A_n, f(A_n) = B_n

部分集合族の和集合をA_*, B_*とする

$ \bigcup_{n=1}^{\infty} A_n = A_*

さらに、これらの補集合を考える

$ A - A_* = A^*, B - B_* = B^*

このとき、

$ f(A^*) = B^*

$ g(B_*) = A_*

であることを示す。

まず、fは単射なので

$ f(A^*) = f(A) - f(A_*)

$ = (B-B_0) - f(A_*)

$ = B- (B_0 \cup f(A_*) )

ここで、

$ f(A_*) = f(\bigcup_{n=1}^\infty A_n) = \bigcup_{n=1}^\infty f(A_n) = \bigcup_{n=1}^\infty B_n

よって

$ f(A^*)= B-B_* = B^*

残りの式においても

$ g(B_*) = g(\bigcup_{n=0}^{\infty} B_n) = g(\bigcup_{n=1}^{\infty} B_{n-1})

$ = \bigcup_{n=1}^{\infty} g(B_{n-1})

5.3より（あとでページ書く）（すでに上のfのとこでやってるが

$ = \bigcup_{n=1}^{\infty} A_n = A_*

より示された

$ F^* : A^* \rightarrow B^*

は全単射

$ G_* : B_* \rightarrow A_*

も全単射

これの逆写像である全単射を

$ F_* : A_* \rightarrow B_*

とする

このときAからBへの写像Fを

$ F(a) =

によってていぎすれば、Fは明らかに全単射となる。