コラム カントール・ベルンシュタインの定理

Last-modified: Thu, 12 Jan 2017 23:46:49 JST (1786d)
Top > コラム カントール・ベルンシュタインの定理
漸化式の定義へ戻る。

漸化式を用いて、コラム 集合の対等性で紹介したカントール・ベルンシュタインの定理を証明してみましょう。

定理1(カントール・ベルンシュタインの定理)
2つの任意の集合\( S \)\( T \)に対し、以下は同値である:
(1) \( S \approx T \)
(2) 「\( S \ll T \)でない」かつ「\( S \gg T \)でない」

証明

全単射な写像は単射であるため、(1)ならば(2)が成り立つ。従って(2)ならば(1)を示せば良い。「\( S \ll T \)でない」かつ「\( S \gg T \)でない」とする。\( S \gg T \)でないので、単射\( f \colon S \to T \)が存在する。\( S \ll T \)でないので、単射\( g \colon T \to S \)が存在する。

\( S_0 := S \setminus g(T) \)と置き、写像\( \mathscr{P}(S) \to \mathscr{P}(S), \ U \mapsto g(f(U) ) \)\( \sigma \)と置く。2項間漸化式の解の一意存在性より、2項間漸化式\( (S_0,\sigma) \)を満たす写像\( S_{\bullet} \colon \mathbb{N} \to \mathscr{P}(S), \ n \mapsto S_n \)がただ1つ存在する*1\( S' := \bigcup_{n \in \mathbb{N}} S_n \)と置くと、\( S \setminus S' \subset S \setminus S_0 = g(T) \)となる。\( g \)は単射なので像への制限\( g |^{g(T)} \)は全単射であり、逆写像の存在性に関する演習により逆写像\( (g |^{g(T)})^{-1} \colon g(T) \to T \)がただ1つ存在する。写像\( f' \colon S \to T \)

\[ f'(s) := \left\{ \begin{array}{ll} f(s) & (s \in S') \\ \left( g |^{g(T)} \right)^{-1}(s) & (s \in S \setminus S') \end{array} \right. \]

と定める。すなわち\( f' \)は3つ組\( (S,T,\{ (s,t) \in S \times T \mid ( (s \in S') \wedge ( (s,t) \in \Gamma_f) ) \vee ( (s \in S \setminus S') \wedge ( (t,s) \in \Gamma_g ) ) \}) \)である。

\( f' \)が全単射であることを示す。そのためには、逆写像の存在性に関する演習より\( f' \)の逆写像を構成すれば良い。\( f \)は単射なので像への制限\( f |^{f(S)} \)は全単射であり、逆写像の存在性に関する演習により逆写像\( (f |^{f(S)})^{-1} \colon f(S) \to S \)がただ1つ存在する。写像\( g' \colon T \to S \)

\[ g'(t) := \left\{ \begin{array}{ll} \left( f |^{f(S)} \right)^{-1}(t) & (t \in f(S') ) \\ g(t) & (t \in T \setminus f(S') ) \end{array} \right. \]

と定める。すなわち\( g' \)は3つ組\( (T,S,\{ (t,s) \in T \times S \mid ( (t \in f(S) ) \wedge ( (s,t) \in \Gamma_f) ) \vee ( (t \in T \setminus f(S') ) \wedge ( (s,t) \in \Gamma_g ) ) \}) \)である。ここで、

\begin{eqnarray*} f(S') & = & \bigcup_{n \in \mathbb{N}} f(S_n) = \bigcup_{n \in \mathbb{N}} g^{-1}(g(f(S_n) ) = \bigcup_{n \in \mathbb{N}} g^{-1}(S_{n+1}) = \bigcup_{n \in \mathbb{N} \setminus \{ 0 \}} g^{-1}(S_n) = g^{-1} \left( \bigcup_{n \in \mathbb{N} \setminus \{ 0 \}} S_n \right) = g^{-1}(S' \setminus S_0) \\ & = & g^{-1}(S') \setminus g^{-1}(S_0) = g^{-1}(S') \setminus \emptyset = g^{-1}(S') \end{eqnarray*}

であることから\( T \setminus f(S') = T \setminus g^{-1}(S') = g^{-1}(S \setminus S') \)となり、これは\( (g |^{g(T)})^{-1} \colon g(T) \to T \)による\( S \setminus S' \subset g(T) \)の像に他ならない。従って、\( f' \)\( g' \)の構成から\( f' \circ g' = \textrm{id}_T \)かつ\( g' \circ f' = \textrm{id}_S \)が成り立つ。

漸化式を用いたのは集合\( S' \)を定めるところのみですが、そここそがカントール・ベルンシュタインの定理の「構成的な」証明の核になっています。




*1 &mathjax{S};が集合であるという仮定はここで既に使われています。