ベルンシュタインの定理 - 機械学習基礎理論独習

ベルンシュタインの定理とは

ベルンシュタインの定理は集合の濃度に関する定理で、とても重要です。

ベルンシュタインの定理

任意の集合 $X,Y$ に対し、 $X$ から $Y$ への単射と $Y$ から $X$ への単射が存在するならば、 $X\sim Y$ が成立する。
(ここでは $\sim$ は対等の記号を表す。)

ベルンシュタインの定理は以下のように言い換えもできます。

ベルンシュタインの定理の言いかえ

$\begin{eqnarray} | X | \leq | Y | , | Y | \leq | X | \Rightarrow | X | = | Y | \end{eqnarray}$

証明

単射 $f:X\rightarrow Y$ と $g:Y\rightarrow X$ が存在したとする。任意の $A\subseteq X$ に対して、 $X$ の部分集合 $A^*$ を

$\begin{eqnarray} A^*=X-g(Y-f(A))\tag{1} \end{eqnarray}$

によって定めます。このとき、任意の $A,B\subseteq X$ に対して、

$\begin{eqnarray} A\subseteq B&\Rightarrow& f(A)\subseteq f(B)\\ &\Rightarrow& Y-f(A)\supseteq Y-f(B)\ (\because 補集合)\\ &\Rightarrow& g(Y-f(A))\supseteq g(Y-f(B))\\ &\Rightarrow& X-g(Y-f(A))\subseteq X-g(Y-f(B))\ (\because 補集合)\\ &\Rightarrow& A^*\subseteq B^*\tag{2} \end{eqnarray}$

が成り立ちます。

$A^*$ のイメージを図1に記しておきます。
図1
f:id:olj611:20220225041959p:plain:w800

次に、 $A\subseteq A^*$ を満たす $X$ の部分集合 $A$ 全体からなる集合族を $\mathcal D$ とします。

$\begin{eqnarray} {\mathcal D}=\{A\subseteq X:A\subseteq A^*\}\tag{3} \end{eqnarray}$

${\mathcal D}$ については、図1などでしっかりイメージしてください。
要は、 $X$ の部分集合のうち、 $A\subseteq A^*$ を満たす集合の集合が $\mathcal D$ ってことです。

ここで、

$\begin{eqnarray} D=\cup{\mathcal D}(=\cup\{A:A\in{\mathcal D}\})\tag{4} \end{eqnarray}$

とおきます。(※フォントの異なる D です。また部分集合族の和集合になっていることに注意しましょう。)
このとき、等式

$\begin{eqnarray} D=D^*\tag{5} \end{eqnarray}$

が成り立つことを示します。
$(5)$ を示すには、 $D\subseteq D^*$ かつ $D^*\subseteq D$ を示せばよいです。

まず、 $D\subseteq D^*$ を示します。
任意の $A\in{\mathcal D}$ に対して、 $A\subseteq\cup{\mathcal D}=D$ であり、また、 $D\subseteq D$ なので、 $(2)$ より

$\begin{eqnarray} A^*\subseteq D^*\tag{6} \end{eqnarray}$

が成り立ちます。
また、 $(3)$ の ${\mathcal D}$ の定義より、

$\begin{eqnarray} A\subseteq A^*\tag{7} \end{eqnarray}$

が成り立ちます。
$(6),(7)$ より、 $A\subseteq D^*$ なので、

$\begin{eqnarray} D=\cup{\mathcal D}\subseteq D^*\tag{8} \end{eqnarray}$

が成り立ちます。
$(8)$ ですが、部分集合の和集合は部分集合であることを使っています。

次に、 $D^*\subseteq D$ を示します。
$D^*\subseteq D^*$ であり、 $(8)$ より、 $D\subseteq D^*$ なので、
$(2)$ より、 $D^*\subseteq (D^*)^*$ が成り立つので、 $D^*\in{\mathcal D}$ 。( ${\mathcal D}$ の定義を確認してください。)
ゆえに、

$\begin{eqnarray} D^*\subseteq\cup{\mathcal D}=D\tag{9} \end{eqnarray}$

が成り立ちます。

以上より、 $(5)$ が成り立つことが示せました。
よって、 $D=X-g(Y-f(D))$ が成り立つから、

$\begin{eqnarray} X-D=g(Y-f(D))\tag{10} \end{eqnarray}$

が成り立ちます。
$(10)$ より、集合 $Y-f(D)$ は単射 $g$ によって $X-D$ に写されます。(図2参照)
図2
f:id:olj611:20220225054227p:plain:w500

このとき、 $g$ の定義域を $Y-f(D)$ に制限し、終域を $X-D$ に変えた写像 $g':(Y-f(D))\rightarrow(X-D)$ は全単射だから、
その逆写像 $(g')^{-1}$ が定義されます。最後に、写像 $h$ を

$\begin{eqnarray} h:X\longrightarrow Y;x\longmapsto \left\{ \begin{array}{l} (g')^{-1}(x)\ \ (x\in X-D のとき)\\ f(x),\ \ (X\in D のとき) \end{array}\tag{11} \right. \end{eqnarray}$