PR

ベルンシュタインの定理とその証明【双方単射があれば全単射がある】

集合と位相
記事内に広告が含まれています。

ベルンシュタインの定理とは,2つの集合それぞれを定義域・終域とする双方向の単射があれば,全単射があるという定理です。ベルンシュタインの定理について,イメージ図を交えて証明していきましょう。

ベルンシュタインの定理とその証明

ベルンシュタインの定理(Schröder–Bernstein theorem)

A,B を空でない集合とする。単射 f\colon A\to B単射 g\colon B\to A が存在するならば,全単射 F\colon A\to B が存在する。

言い換えれば, A,B の間に双方向の単射がそれぞれ存在すれば, A B濃度は等しい,ということになります。全単射の存在が示せなくても,濃度が等しいといえる定理なんですね。

証明しましょう。

証明

f 全単射なら証明が終わるので,全射でないとする。

A_0=A\setminus g(B) とし,以下 A_n = g(f(A_{n-1})) \; (n=1,2,\dots) と定める。 A^*=\bigcup_{n=0}^\infty A_n とし,

F(x)= \begin{cases} f(x) & x\in A^*, \\ g^{-1} (x) & x\in A\setminus A^* \end{cases}


と定めると, F\colon A\to B全単射になることを示そう。

ベルンシュタインの定理の証明のイメージ

まず, A\setminus A^*\subset A\setminus A_0=g(B) であるから, x\in A\setminus A^* に対して, g^{-1}(x)\in B はただ一つ定まるため, F写像としてwell-definedである。

F全射性について,像・逆像の演算より,

\begin{aligned}F(A\setminus A^*)&=g^{-1}(A\setminus A^*) \\ &= g^{-1}(A)\setminus g^{-1}(A^*)\\&=B\setminus g^{-1}(A^*),\\ g^{-1}(A^*)&= \bigcup_{n=0}^\infty g^{-1}(A_n) \\ &=\bigcup_{n=1}^\infty g^{-1}( g(f(A_{n-1}))) \\ &= \bigcup_{n=1}^\infty f(A_{n-1}) = f(A^*) \end{aligned}


である。ただし,下から2行目の = g^{-1}(A_0)=\emptyset を用いた。これより,

F(A\setminus A^*)=B\setminus g^{-1}(A^*)=B\setminus f(A^*)


であり,これは F全射であることを示している。

F単射性について, f, g^{-1}|_{A\setminus A^*} はともに単射であるから, x\in A^*,\, y\in A\setminus A^* として, F(x)\ne F(y) すなわち f(x)\ne g^{-1}(y) を示せばよい。

f(x)=g^{-1}(y) と仮定する。 x\in A_n とすると, g(f(x))=y より, y\in A_{n+1}\subset A^* となって矛盾する。よって f(x)\ne g^{-1}(y) であり, F単射である。

証明終

関連する記事