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

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

この$G$が$\mathscr{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\nat$が存在し$p_i\leq p$となる。よって今$p,q\in G$に対し$p_{i_p}\leq p,p_{i_q}\leq q$となる$i_p,i_q\in\nat$を取る。$i_p\leq i_q$か$i_q\leq i_p$のいずれかが成り立つことから$\{p_i\}_{i\in\nat}$の定義から、$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\mathbb{P})[p\leq q\to q\in G]$$であることを確かめる。$p\in G,q\in\mathbb{P}$とし$p\leq q$とする。$p\in G$に対しある$i\in\nat$が存在し$p_i\leq p$となることと推移性から$p_i\leq q$であり、よって$q\in G$である。次に$$(\forall D\in\mathscr{D})[G\cap D\neq \emptyset]$$であることを確かめる。まず任意の$i\in\nat$に対し$p_i\leq p_i$であるから、任意の$i\in\nat$に対し$p_i\in G$である。また$\{p_i\}_{i\in\nat}$の定義から任意の$i\in\nat$に対し$p_{i+1}\in D_i$である。よって$p_{i+1}\in D_i\cap G$であり空ではない。

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

• $D_i:=\{p\in\mathbb{C}\mid p\neq x_i\restriction\mathrm{dom}(p)\}$ 。
• $D_i^*:=\{p\in\mathbb{C}\mid i<\mathrm{dom}(p)\}$ 。

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

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