強制法によるCantorの定理の証明

1672

Cantorの定理 (Cantor's theorem) は「 $N$ から $N^{N}$ への全射が存在しない」という定理である。この定理の証明は一般的に対角線論法 (diagonal argument) によって示されるが以下では現代集合論の基本的な道具である強制法 (forcing argument) を用いた証明を紹介する。

半順序、強制概念

集合 $P$ と $P$ 上の二項関係 $\leq$ の組 $⟨ P, \leq ⟩$ が半順序 (partial order) であるとは以下の条件を満たすことである。

反射性 $(\forall x \in P) [x \leq x]$ 。
対称性 $(\forall x \in P) (\forall y \in P) [x \leq y \land y \leq x \to x = y]$ 。
推移性 $(\forall x \in P) (\forall y \in P) (\forall z \in P) [x \leq y \land y \leq z \to x \leq z]$ 。

また半順序 $⟨ P, \leq ⟩$ が与えられたとき $<$ を $x < y \Leftrightarrow x \leq y \land x \neq y$ で与えられる $P$ 上の二項関係とする。以下では半順序のことを強制概念 (forcing notion) といい $x \leq y$ が成り立つとき $x$ は $y$ より強いという。

稠密性

$⟨ P, \leq ⟩$ を強制概念とする。集合 $D \subseteq P$ が $⟨ P, \leq ⟩$ に於いて稠密 (dense) であるとは $(\forall p \in P) (\exists q \in D) [q \leq p]$ が成り立つことである。

フィルター

$⟨ P, \leq ⟩$ を強制概念とする。集合 $G \subseteq P$ が $⟨ P, \leq ⟩$ に於いてフィルター (filter) であるとは以下の条件を満たすことである。

$(\forall p \in G) (\forall q \in G) (\exists r \in G) [r \leq p \land r \leq q]$ 。
$(\forall p \in G) (\forall q \in P) [p \leq q \to q \in G]$

ジェネリックフィルター

$⟨ P, \leq ⟩$ を強制概念とし、 $D$ を $⟨ P, \leq ⟩$ 上の稠密集合による族とする。このとき $⟨ P, \leq ⟩$ 上のフィルター $G$ が $D$ -ジェネリック ( $D$ -generic) であるとは $(\forall D \in D) [G \cap D \neq \emptyset]$ が成り立つことである。

ジェネリックフィルターの存在

$⟨ P, \leq ⟩$ を強制概念とし、 $D$ を稠密集合からなるたかだか可算な族とする。このとき任意の $p \in P$ に対して、 $p \in G$ となる $D$ -ジェネリックフィルター $G$ が存在する。

$D$ を可算とし、 $D = {D_{i}}_{i \in N}$ とする。 $P$ の元の可算列 ${p_{i}}_{i \in N}$ を以下のように再帰的に定義する。 $p_{0} := p$ とし $p_{i + 1}$ を $q \leq p_{i}$ かつ $q \in D_{i}$ となる $q$ としよう。このような元は $D_{i}$ が稠密であることから存在する事が分かる。そして $G := {r \in P ∣ (\exists i \in N) [p_{i} \leq r]}$ とする。

この $G$ が $D$ -ジェネリックフィルターになっていることを確かめる。まず
$(\forall p \in G) (\forall q \in G) (\exists r \in G) [r \leq p \land r \leq q]$ となっていることは、 $G$ の定義から任意の $p \in G$ に対し、ある $i \in N$ が存在し $p_{i} \leq p$ となる。よって今 $p, q \in G$ に対し $p_{i_{p}} \leq p, p_{i_{q}} \leq q$ となる $i_{p}, i_{q} \in N$ を取る。 $i_{p} \leq i_{q}$ か $i_{q} \leq i_{p}$ のいずれかが成り立つことから ${p_{i}}_{i \in N}$ の定義から、 $p_{i_{p}} \leq p_{i_{q}}$ か $p_{i_{q}} \leq p_{i_{p}}$ のいずれかが成り立つ。よって $p_{i_{p}}, p_{i_{q}}$ の小さい方を $r$ としよう。定義から明らかに $r \in G$ かつ $r \leq p_{i_{p}}$ かつ $r \leq p_{i_{q}}$ である。よって $p_{i_{p}}, p_{i_{q}}$ の定義と推移性から $r \leq p$ かつ $r \leq q$ である。次に $(\forall p \in G) (\forall q \in P) [p \leq q \to q \in G]$ であることを確かめる。 $p \in G, q \in P$ とし $p \leq q$ とする。 $p \in G$ に対しある $i \in N$ が存在し $p_{i} \leq p$ となることと推移性から $p_{i} \leq q$ であり、よって $q \in G$ である。次に $(\forall D \in D) [G \cap D \neq \emptyset]$ であることを確かめる。まず任意の $i \in N$ に対し $p_{i} \leq p_{i}$ であるから、任意の $i \in N$ に対し $p_{i} \in G$ である。また ${p_{i}}_{i \in N}$ の定義から任意の $i \in N$ に対し $p_{i + 1} \in D_{i}$ である。よって $p_{i + 1} \in D_{i} \cap G$ であり空ではない。

Cohen強制

$N^{< ω}$ を自然数の有限列全体からなる集合とし、 $N^{< ω}$ 上の二項関係 $p \leq q$ を $q$ が $p$ の部分列であることとする。このとき $⟨ N^{< ω}, \leq ⟩$ は半順序を成し、これをCohen強制 (Cohen forcing) といい、 $C$ と表す。

Cantorの定理

$N$ から $N^{N}$ の全射は存在しない。

$X \subseteq N^{N}$ を自然数の無限列からなる可算集合とする。 $X$ を整列させて ${x_{i}}_{i \in N}$ とする。各 $i \in N$ に対し $D_{i}, D_{i}^{*}$ を以下のように定める。

$D_{i} := {p \in C ∣ p \neq x_{i} ↾ dom (p)}$ 。
$D_{i}^{*} := {p \in C ∣ i < dom (p)}$ 。

すなわち $D_{i}$ は $x_{i}$ の部分列とならないような $p \in C$ からなる集合で $D_{i}^{*}$ は $i$ より長い自然数の有限列の集合となる。まず $D_{i}$ が $C$ に於いて稠密であることを確かめる。すなわち、 $(\forall p \in C) (\exists q \in D_{i}) [q \leq p]$ であることを見る。 $C$ の定義から $q \leq p$ が成り立つのは $p$ が $q$ の部分列であることであったので、任意の $p \in C$ に対して、ある $p$ の拡大列で $x_{i}$ の部分列にならないものが存在すれば良い。今 $p$ の長さが $n$ であるとしたら $x_{i}$ の $n + 1$ 番目の元と異なる自然数を $m$ として $p$ と列 $⟨ m ⟩$ の連結 $p^{⌢} ⟨ m ⟩$ は $x_{i}$ の部分列とならないため良い。次に $D_{i}^{*}$ が $C$ に於いて稠密であることを確かめる。すなわち、 $(\forall p \in C) (\exists q \in D_{i}^{*}) [q \leq p]$ であることを見る。これは $p$ の拡大列で長さが $i$ より大きいものが存在するので明らかである。

今 $D_{i}, D_{i}^{*}$ は $C$ に於いて稠密であることが分かったので $D := {D_{i} ∣ i \in N} \cup {D_{i}^{*} ∣ i \in N}$ とすれば、命題1から $D$ -ジェネリックフィルター $G$ が存在する。任意の $i \in N$ に対し $D_{i}^{*} \cap G \neq \emptyset$ であるから、任意の $i \in N$ に対し、 $i$ より長い有限列 $p \in G$ が存在し、 $G$ はフィルターであることから貼り合わせ $⋃ G$ は $N^{N}$ の元である。また同様に任意の $i \in N$ に対し $D_{i} \cap G \neq \emptyset$ であるから、任意の $i \in N$ に対し、 $x_{i}$ の部分列にならないような $p \in G$ が存在し、 $G$ はフィルターであることから貼り合わせ $⋃ G$ は $x_{i}$ ではない。よって $⋃ G \in N^{N} ∖ X$ つまり $N^{N} ∖ X \neq \emptyset$ であり、 $X$ は $N^{N}$ の任意の可算部分集合であったことから $N^{N}$ は可算集合ではない、すなわち $N$ から $N^{N}$ への全射が存在しないことが分かる。