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{align*} A\subset B&\Longrightarrow f(A)\subset f(B)\\ &\Longrightarrow Y\setminus f(A)\supset Y\setminus f(B)\\ &\Longrightarrow g(Y\setminus f(A))\supset g(Y\setminus f(B))\\ &\Longrightarrow X\setminus g(Y\setminus f(A))\subset X\setminus g(Y\setminus f(B)) \end{align*}
となるので良い．

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

まず$D\subset D^\ast$を示そう．任意に$x\in D$をとると，$D$の定義よりある$A\in\mathscr{D}$で$x\in A$となるものが存在する．このとき，$A\subset\bigcup_{A\in\mathscr{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\mathscr{D}$である．故に$D^\ast\subset\bigcup_{A\in\mathscr{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':Y\setminus f(D)\to X\setminus D$は全単射だから，その逆写像$(g')^{-1}$が考えられる．最後に写像$h:X\to Y$を，$x\in D$ならば$f(x)$に，$x\in X\setminus D$ならば$(g')^{-1}(x)$にうつす写像とすれば，$h:X\to Y$は全単射である．