Bernsteinの定理
AからBへの単射が存在し、BからAへの単射も存在すれば、
この定理のいいとこmiyamonz.icon
対等であることを、全単射な写像を具体的に用意しないでも示せる
証明
仮定
fをAからBへの単射
gをBからAへの単射とする
AからBへの全単射Fの存在を示す
fが全射なら、fが求めるFである
よって以下ではfが全射でないとする
すなわち、$ f(A) = V(f)はBに等しくない
$ f(A)のBに対する補集合を$ B - f(A) = B_0とする
次に、以下のような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_*
$ \bigcup_{n=0}^{\infty} B_n = B_* (こっちはn=0から)
さらに、これらの補集合を考える
$ 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
より、$ B_0 \cup f(A_*) = \bigcup_{n=0}^\infty B_n = B_*
よって
$ 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は単射で$ f(A^*) = B^*なので、
終集合を$ B^*に制限した写像を$ F^*とすると
$ F^* : A^* \rightarrow B^*
は全単射
同様に、gが単射で$ g(B_*) = A_*なので、
定義域を$ B_*に制限し、終集合を$ A_*に制限した写像を$ G_*とすれば
$ G_* : B_* \rightarrow A_*
も全単射
これの逆写像である全単射を
$ F_* : A_* \rightarrow B_*
とする
このときAからBへの写像Fを
$ F(a) =
$ F^*(a) ($ a\in A^*のとき)
$ F_*(a) ($ a\in A_*のとき)
によってていぎすれば、Fは明らかに全単射となる。
あとでもう少し全体の見通しが良い感じに変えたいmiyamonz.icon