カントールの定理！べき集合はいつでも元の集合より大きくなる

$3$ 個の要素を持つ集合の部分集合は $8$ 個。$10$ 個なら $1024$ 個です。$2^n>n$ はどの $n$ でも成り立ちます。

無限集合でも同じことが起こります^[1]。それがカントールの定理で、証明は有限のときの数え上げとはまるで別の形になります。

主張

どんな集合 $A$ についても、べき集合 $\mathcal{P}(A)$ の濃度は $A$ より真に大きくなります^[1,3]。

$$|A|<|\mathcal{P}(A)|$$

$\le$ のほうは簡単。$x\mapsto \{x\}$ が単射なので、$|A|\le |\mathcal{P}(A)|$ です。

問題は等号のほうです。$A$ から $\mathcal{P}(A)$ への全射が $1$ つも作れない。証明の中身はここにあります。

有限なら数えれば済む

$A=\{a,b,c\}$ で確かめます。各要素を入れるか入れないかで $2$ 通りずつ、合わせて $2^3=8$ 個。

$2^n>n$ は帰納法で片づきます。$n=0$ なら $1>0$、$2^{n+1}=2\cdot 2^n\ge 2^n+1>n+1$。

無限集合ではこの計算が使えません。$2^{{\aleph }_0}>{\aleph }_0$ を、数え上げ以外の方法で示す必要がある。

対角集合

$f:A\to \mathcal{P}(A)$ を任意の写像とします。全射でないことを示す^[1,4]。

そのために、次の集合を作ります。カントールの対角集合と呼ばれるものです。

$$D=\{x\in A\mid x\notin f(x)\}$$

各 $x$ について $f(x)$ は $A$ の部分集合なので、$x\in f(x)$ かどうかを問えます。答えが「いいえ」の $x$ だけを集めた、というだけの定義です。

証明

$D$ が $f$ の像に入らないことを見ます^[4]。$f(a)=D$ となる $a\in A$ があったとしましょう。

$a\in D$ だとすると、$D$ の定義から $a\notin f(a)=D$ になります。矛盾。

$a\notin D$ だとすると、$a\notin f(a)$ なので定義から $a\in D$ です。こちらも矛盾。

どちらの場合も破れるので、そんな $a$ はありません。$f$ は全射になりえない。

$f$ は任意だったので、$A$ から $\mathcal{P}(A)$ への全射は $1$ つも存在しません。単射はあるので、$|A|<|\mathcal{P}(A)|$ が出ます。

例：自然数のべき集合

$A=\mathbb{N}$ にすると、$\mathcal{P}(\mathbb{N})$ は非可算だと分かります^[2]。

$\mathbb{N}$ から $\mathcal{P}(\mathbb{N})$ への全単射があれば全射でもあるので、定理に反する。可算集合のべき集合は必ず非可算になります。

$\mathcal{P}(\mathbb{N})$ の濃度は $2^{{\aleph }_0}$ で、実数の濃度と一致します。実数が非可算なことも、この形で出せる。

特性関数で見なおす

$A$ の部分集合と、$A$ から $\{0,1\}$ への関数は $1$ 対 $1$ に対応します。

部分集合 $S$ に、$S$ の要素で $1$、それ以外で $0$ をとる関数を対応させる。この対応が全単射です。

だから $\mathcal{P}(A)$ を $2^A$ と書きます。$|\mathcal{P}(A)|=2^{|A|}$ という記法は、この対応から来ている。

カントールが $1891$ 年の論文で扱ったのも、部分集合ではなく $\{0,1\}$ 値の関数のほうでした^[1]。

小数の対角線論法と同じ形

$(0,1)$ が非可算であることの証明も、同じ骨組みを持ちます^[4]。

実数を縦に並べ、$n$ 番目の実数の $n$ 桁目を変えて新しい実数を作る。作った実数は、どの行とも $1$ 桁で食い違います。

べき集合のほうは、$n$ 番目の集合が $n$ を含むかどうかを反転させる。桁が「含む・含まない」に置きかわっただけです。

無限の階梯

定理を繰り返し当てると、濃度がいくらでも大きくなります^[2,3]。

$${\aleph }_0<2^{{\aleph }_0}<2^{2^{{\aleph }_0}}<2^{2^{2^{{\aleph }_0}}}<\cdots$$

無限の大きさに種類がある、というだけでなく、その種類が果てしなく続く。

最大の濃度はありません。「いちばん大きい無限」を考えようとすると、そのべき集合がもっと大きくなる。

カントールのパラドックス

すべての集合を集めた $V$ があると仮定します^[1,3]。

$\mathcal{P}(V)$ の要素はどれも集合なので、$V$ に属します。つまり $\mathcal{P}(V)\subseteq V$ で、$|\mathcal{P}(V)|\le |V|$ になる。

ところがカントールの定理は $|V|<|\mathcal{P}(V)|$ を言います。矛盾です。

すべての集合の集合は存在しない、と結論できます。素朴集合論が破れる場面の $1$ つになる。

ラッセルのパラドックスとの関係

対角集合の作り方は、ラッセルの構成とよく似ています^[1]。

$$R_A=\{x\in A\mid x\notin x\}$$

$f$ を恒等的な対応と見ると、$D$ がちょうどこの形になる。$A$ を「すべての集合」にすると、$R\in R$ と $R\notin R$ が同値になって破れます。

似ているのは書き方で、中身は独立だという指摘もあります。チャーチは、ラッセルのパラドックスが濃度の議論を必要としないことを強調しました^[1]。

歴史

連続体仮説へ

定理は $2^{{\aleph }_0}>{\aleph }_0$ を言いますが、$2^{{\aleph }_0}$ がどの基数かまでは決めません^[2]。

${\aleph }_1=2^{{\aleph }_0}$ かどうかが連続体仮説です。ZFC からは証明も反証もできない。

定理が言うのは「必ず上がる」ことだけ。どこまで上がるかは、公理の外側の問題になります。

上がることは定理が保証し、どこまで上がるかは公理が決める。この分かれ方が、集合論のその後の展開をつくりました。

よくある誤り

対角集合はどの行とも $1$ か所で食い違う。この $1$ 行だけで、無限の階梯がすべて出てきます。

参考文献

^[1] が対角集合による証明とパラドックスへのつながり、^[2] が無限の階梯と連続体仮説への位置づけ、^[3] が有限の場合と歴史的経緯、^[4] が小数の対角線論法との対応と詳しい証明です。