Bernsteinの定理の証明：単射単射があれば全単射

単射$f:X\to Y$と単射$g:Y\to X$が存在したとする．$X$の部分集合$A\subset X$に対して，$A^{\ast }=X\setminus g(Y\setminus f(A))$と定義する．このとき，$A\subset B\Rightarrow A^{\ast }\subset B^{\ast }$の成り立つことを示す．実際，
$$\begin{array}{rl}A\subset B& ⟹f(A)\subset f(B)\\ & ⟹Y\setminus f(A)\supset Y\setminus f(B)\\ & ⟹g(Y\setminus f(A))\supset g(Y\setminus f(B))\\ & ⟹X\setminus g(Y\setminus f(A))\subset X\setminus g(Y\setminus f(B))\end{array}$$
となるので良い．

$\mathcal{D}=\{A\subset X\mid A\subset A^{\ast }\}$と定める．明らかに$\varnothing \in \mathcal{D}$だから$\mathcal{D}\ne \varnothing$である．そこで，$D=\bigcup _{A\in \mathcal{D}}A$とおく．このとき$D=D^{\ast }$の成り立つことを示す．

まず$D\subset D^{\ast }$を示そう．任意に$x\in D$をとると，$D$の定義よりある$A\in \mathcal{D}$で$x\in A$となるものが存在する．このとき，$A\subset \bigcup _{A\in \mathcal{D}}A=D$だから$A\subset A^{\ast }\subset D^{\ast }$となる．よって，$x\in D^{\ast }$である．これより$D\subset D^{\ast }$が示せた．

逆の包含を示そう．$D\subset D^{\ast }$は上で示した．これより$D^{\ast }\subset (D^{\ast }{)}^{\ast }$となるから，$D^{\ast }\in \mathcal{D}$である．故に$D^{\ast }\subset \bigcup _{A\in \mathcal{D}}A=D$．これで逆の包含$D^{\ast }\subset D$が示せた．

以上の議論より$D=D^{\ast }$だったから$D=X\setminus (g(Y\setminus f(D)))$が成り立つ．よって，両辺の$X$における補集合をとって$X\setminus D=g(Y\setminus f(D))$．すなわち集合$Y\setminus f(D)$は$g$によって集合$X\setminus D$にうつされる．このとき，$g$の定義域を$Y\setminus f(D)$に制限して終域を$X\setminus D$に変えた写像$g^{\prime }:Y\setminus f(D)\to X\setminus D$は全単射だから，その逆写像$(g^{\prime }{)}^{-1}$が考えられる．最後に写像$h:X\to Y$を，$x\in D$ならば$f(x)$に，$x\in X\setminus D$ならば$(g^{\prime }{)}^{-1}(x)$にうつす写像とすれば，$h:X\to Y$は全単射である．