カントールの定理

どんな集合を思い浮かべても――有限でも無限でも、どれほど大きくても――その冪集合は必ず元の集合より真に大きい。これがカントールの定理だ。その証明は数学全体の中でも最も美しいもののひとつで、対角集合 (diagonal set) と呼ばれる自己言及的な構成が、あらゆる全射の候補を一撃で退ける。この結果はまた、数学者たちが存在すら知らなかった扉を開く――無限の大きさは無数に存在する。

カントールの定理が言うこと

カントールの定理。 任意の集合 $A$ に対して、$A$ から $\mathcal{P}(A)$ への全射は存在しない。同値な言い方をすれば、

$$|A| < |\mathcal{P}(A)|. \tag{1}$$

写像 で確認したように、$|A| < |B|$ とは $A \hookrightarrow B$ への単射は存在するが、全単射――したがって全射も――$A \twoheadrightarrow B$ は存在しないことを意味する。カントールの定理は $(1)$ を確立する二つのパートからなる。

• 簡単な方向: $A$ から $\mathcal{P}(A)$ への明示的な単射の構成（$|A| \leq |\mathcal{P}(A)|$ を与える）。
• 難しい方向: $A$ から $\mathcal{P}(A)$ への全射が存在しないことの証明（等号を排除する）。

簡単な方向：A を P(A) に埋め込む

一点集合写像 (singleton map) を次のように定義する。

$$\iota \colon A \to \mathcal{P}(A), \quad a \mapsto \{a\}.$$

これは各元をそれを含む一点集合に送る写像だ。$\iota(a_1) = \iota(a_2)$ なら $\{a_1\} = \{a_2\}$ となり、$a_1 = a_2$ が強制される。よって $\iota$ は単射であり、$|A| \leq |\mathcal{P}(A)|$ が成り立つ。

対角線論法

全射が存在しないことの証明には、対角線論法 (diagonal argument) と呼ばれる手法を使う。$A$ の部分集合 $D \subseteq A$ を、どんな全射の候補も必ず取りこぼすように構成する――特定の悪い $f$ だけでなく、考えうるすべての $f$ に対して。

証明。 $f \colon A \to \mathcal{P}(A)$ が全射であると仮定して矛盾を導く。対角集合を次のように定義する。

$$D \;\coloneqq\; \{x \in A \mid x \notin f(x)\}. \tag{2}$$

$D \subseteq A$ なので $D \in \mathcal{P}(A)$ だ。$f$ が全射と仮定したので、$A$ のある元が $D$ に写される。それを $d$ と呼ぶ。

$$f(d) = D.$$

では、$d$ は $D$ の元だろうか？

• $d \in D$ の場合： 定義 $(2)$ より $d \notin f(d)$ でなければならない。しかし $f(d) = D$ なので $d \notin D$ となる。矛盾。
• $d \notin D$ の場合： 定義 $(2)$ より $d \in f(d)$ でなければならない。しかし $f(d) = D$ なので $d \in D$ となる。矛盾。

どちらの場合も矛盾が生じる。$f$ が全射であるという仮定は偽でなければならない。$\square$

対角集合がうまく機能する理由

$D = \{x \in A \mid x \notin f(x)\}$ という定義は、すべての $x \in A$ に対して、$D$ が $x$ の帰属について $f(x)$ と食い違うように巧妙に作られている。

$$x \in D \;\iff\; x \notin f(x). \tag{3}$$

これはつまり、どんな $x$ についても $D \neq f(x)$ ということだ――二つの集合は $x$ が属するかどうかで異なる。$D$ は $f$ の値域にあるどの集合とも異なるので、値域に含まれることができない。全射はすべての $\mathcal{P}(A)$ の元を「打たなければ」ならないのに、$D$ はそこから逃げ出してしまう。

行列の視覚化

$A$ の元を $a_0, a_1, a_2, \ldots$ と並べられるとしたら、$f$ を無限の帰属表として描ける。セル $(i, j)$ は $a_j \in f(a_i)$ かどうかを記録する。

	$a_0$	$a_1$	$a_2$	$\cdots$
$f(a_0)$	?
$f(a_1)$		?
$f(a_2)$			?
$\vdots$				$\ddots$

太字の対角成分は各 $i$ について「$a_i \in f(a_i)$？」への答えだ。対角集合 $D$ はすべての対角成分を反転して作られる――$i$ 番目の対角成分が「no」のとき、$a_i$ を $D$ に含める。できた行は、すべての $i$ について $a_i$ の列で $i$ 行目と異なるので、$D$ は表のどの行にも一致しない。

この論法は可算でも非可算でも、どんな集合 $A$ に対しても成り立つ。行列はあくまで視覚化の道具であり、前の節の形式的な証明には元の列挙は一切必要ない。

濃度の無限の塔

有限集合に対しては、$(1)$ は $n < 2^n$（$n \geq 0$ のすべてで成立）に帰着される。この定理は無限集合に適用したとき、はるかに驚くべき様相を帯びる。

$(1)$ を $\mathbb{N}$ に適用し、次に $\mathcal{P}(\mathbb{N})$ に適用し、さらに続けると、

$$|\mathbb{N}| \;<\; |\mathcal{P}(\mathbb{N})| \;<\; \bigl|\mathcal{P}(\mathcal{P}(\mathbb{N}))\bigr| \;<\; \cdots$$

これは決して終わらない、無限濃度の狭義単調増加な列だ。「最大の」無限は存在しない――冪集合操作は常に真に大きな集合を生み出す。無限は実に、多くの異なる大きさで存在するのだ。

特筆すべき特別なケースとして、解析学へのつながりがある。$|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$ が成り立つ。つまり実数は自然数より真に大きい。これの直接証明は 非可算集合 のチェックポイントで見ることができる。

まとめ

• カントールの定理 $(1)$ は、任意の集合 $A$ に対して $A$ から $\mathcal{P}(A)$ への全射は存在せず、$|A| < |\mathcal{P}(A)|$ であると述べている。
• 簡単な方向は一点集合への単射 $a \mapsto \{a\}$ であり、$|A| \leq |\mathcal{P}(A)|$ を示す。
• 対角線論法は $D = \{x \in A \mid x \notin f(x)\}$ を定義する。これは $A$ の部分集合であり、$f \colon A \to \mathcal{P}(A)$ なるあらゆる全射の候補の値域の外にある。
• $D$ が $f$ の値域から逃げ出すのは、すべての $x \in A$ に対して $x$ の帰属について $f(x)$ と食い違うからだ。
• この定理を繰り返し適用すると、狭義単調増加な無限の塔 $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < \cdots$ が得られる――無限の大きさは無数に存在する。
• 特に $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$ が成り立つので、実数は自然数より真に大きな無限を形成する。