コラム カントール・ベルンシュタインの定理
漸化式を用いて、コラム 集合の対等性で紹介したカントール・ベルンシュタインの定理を証明してみましょう。
| 定理1（カントール・ベルンシュタインの定理） |
| ２つの任意の集合\( 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 \)と置く。２項間漸化式の解の一意存在性より、２項間漸化式\( (S_0,\sigma) \)を満たす写像\( S_{\bullet} \colon \mathbb{N} \to \mathscr{P}(S), \ n \mapsto S_n \)がただ１つ存在する*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 \)がただ１つ存在する。写像\( f' \colon S \to T \)を
と定める。すなわち\( f' \)は３つ組\( (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 \)がただ１つ存在する。写像\( g' \colon T \to S \)を
と定める。すなわち\( g' \)は３つ組\( (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 ) ) \}) \)である。ここで、
であることから\( 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' \)を定めるところのみですが、そここそがカントール・ベルンシュタインの定理の「構成的な」証明の核になっています。
- 漸化式の定義へ戻る。