可算集合と非可算集合 - Cantorの対角線論法

無限集合にも「大きさ」の違いがあるという発見は、19 世紀末に Georg Cantor が成し遂げた革命的な成果です。自然数の集合と実数の集合はどちらも無限ですが、同じ種類の無限ではありません。この区別を厳密に与えるのが可算・非可算の概念であり、その証明の核心が対角線論法です。

集合の濃度と全単射

2 つの集合の「大きさ」を比較するために、濃度（cardinality）という概念を用います。集合 $A$ と $B$ の間に全単射 $f:A\to B$ が存在するとき、$A$ と $B$ は同じ濃度を持つといい、$|A|=|B|$ と書きます。

有限集合の場合、これは単に元の個数が等しいことを意味します。しかし無限集合では、直観に反する現象が起こります。たとえば自然数全体 $\mathbb{N}=\{0,1,2,3,\dots \}$ と偶数全体 $2\mathbb{N}=\{0,2,4,6,\dots \}$ の間には $n\mapsto 2n$ という全単射が存在するので、$|\mathbb{N}|=|2\mathbb{N}|$ です。部分集合なのに全体と同じ濃度を持つ――これは無限集合に特有の性質であり、Dedekind はこの性質を無限集合の定義に用いました。

可算集合の定義

集合 $A$ が可算（countable）であるとは、$A$ が有限集合であるか、または $\mathbb{N}$ との全単射が存在することをいいます。$\mathbb{N}$ と全単射が存在する無限集合を特に可算無限と呼びます。可算無限集合の元は $a_0,a_1,a_2,\dots$ と番号付けできるということです。

整数 $\mathbb{Z}$ が可算であることは、$0,1,-1,2,-2,3,-3,\dots$ と並べれば自然数との全単射が構成できることからわかります。有理数 $\mathbb{Q}$ の可算性はもう少し工夫が必要で、次に述べる対角線的な手法の原型が現れます。

有理数の可算性

正の有理数を格子状に並べる方法を考えます。$p/q$（$p,q\in \mathbb{N}$, $q\ge 1$）を座標 $(p,q)$ に配置すると、すべての正の有理数（の重複を含む表現）が $\mathbb{N}\times \mathbb{N}$ の格子点に対応します。この格子を対角線に沿ってジグザグに走査すれば、すべての格子点を漏れなく列挙できます。

この論法により $|\mathbb{Q}|=|\mathbb{N}|$ が示されます。有理数は稠密で、任意の 2 つの実数の間に有理数が存在するにもかかわらず、自然数と「同じ個数」しかありません。

Cantor の対角線論法

では実数 $\mathbb{R}$ はどうでしょうか。Cantor は 1891 年に、$\mathbb{R}$ が可算でないことを対角線論法により証明しました。ここでは区間 $(0,1)$ の実数が可算でないことを示します。$(0,1)$ と $\mathbb{R}$ の間には全単射が存在する（たとえば $\tan$ を用いて構成できる）ので、$(0,1)$ の非可算性から $\mathbb{R}$ の非可算性が従います。

証明　背理法を用います。$(0,1)$ が可算だと仮定すると、$(0,1)$ の元を

$$r_0,r_1,r_2,r_3,\dots$$

と列挙できます。各 $r_n$ を 10 進小数展開で表します（曖昧さを避けるため、末尾に $9$ が無限に続く表現は用いません）。

$$\begin{array}{rl}{r}_0& =0.d_{00}{d}_{01}{d}_{02}{d}_{03}\cdots \\ r_1& =0.d_{10}{d}_{11}{d}_{12}{d}_{13}\cdots \\ r_2& =0.d_{20}{d}_{21}{d}_{22}{d}_{23}\cdots \\ r_3& =0.d_{30}{d}_{31}{d}_{32}{d}_{33}\cdots \\ & ⋮\end{array}$$

ここで $d_{ij}\in \{0,1,\dots ,9\}$ は $r_i$ の小数第 $j+1$ 位の数字です。

新しい実数 $s=0.s_0{s}_1{s}_2{s}_3\cdots$ を次のように定義します。

$$s_n=\{\begin{array}{ll}3& (d_{nn}\ne 3)\\ 7& (d_{nn}=3)\end{array}$$

$s$ は $(0,1)$ の元ですが、すべての $n$ に対して $s\ne r_n$ です。なぜなら $s$ と $r_n$ は少なくとも小数第 $n+1$ 位で異なるからです。これは $(0,1)$ のすべての元が $r_0,r_1,r_2,\dots$ に列挙されているという仮定に矛盾します。したがって $(0,1)$ は可算ではありません。$\square$

非可算集合と連続体の濃度

$(0,1)$（したがって $\mathbb{R}$）の濃度は ${\aleph }_0$（アレフ・ゼロ、可算無限の濃度）より真に大きく、$\mathfrak{c}$（連続体の濃度）と書かれます。Cantor は集合 $A$ に対してそのべき集合 $\mathcal{P}(A)$ が常に $A$ より大きい濃度を持つことも証明しました。

Cantor の定理 　任意の集合 $A$ に対して、$|A|<|\mathcal{P}(A)|$ が成り立つ。

この証明にも対角線論法が使われます。$f:A\to \mathcal{P}(A)$ が全射だと仮定し、

$$B=\{a\in A:a\notin f(a)\}$$

を考えると、$B\in \mathcal{P}(A)$ ですが、$B=f(b)$ となる $b\in A$ が存在しないことが示せます。もし $b\in B$ なら定義により $b\notin f(b)=B$ で矛盾し、$b\notin B$ なら $b\notin f(b)$ だから $b\in B$ で矛盾です。これは Russell のパラドックスとも深く関連する構造を持っています。

2 つの論法は形式は異なりますが、本質的な構造は同一です。列挙や写像が与えられたとき、対角成分を反転させることで「漏れ」を構成する――これが対角線論法の核心にあるアイデアです。

$|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|$ の直観

実数の濃度 $\mathfrak{c}$ は $|\mathcal{P}(\mathbb{N})|=2^{{\aleph }_0}$ に等しいことが知られています。直観的には、$(0,1)$ の実数の 2 進小数展開 $0.b_0{b}_1{b}_2\cdots$（$b_i\in \{0,1\}$）は、$\mathbb{N}$ から $\{0,1\}$ への関数、すなわち $\mathbb{N}$ の部分集合の特性関数と自然に対応するからです。

Cantor の定理を繰り返し適用すれば ${\aleph }_0<2^{{\aleph }_0}<2^{2^{{\aleph }_0}}<\cdots$ と無限に大きな濃度が存在することがわかります。無限には果てしない階層構造があるのです。

連続体仮説

${\aleph }_0$ と $\mathfrak{c}=2^{{\aleph }_0}$ の間に別の濃度は存在するのか――これが連続体仮説（Continuum Hypothesis, CH）です。連続体仮説は「${\aleph }_0<|S|<2^{{\aleph }_0}$ を満たす集合 $S$ は存在しない」、すなわち $2^{{\aleph }_0}={\aleph }_1$ であると主張します。

Gödel（1940）は ZFC と連続体仮説が無矛盾であることを示し、Cohen（1963）は ZFC と連続体仮説の否定が無矛盾であることを示しました。したがって連続体仮説は ZFC から独立であり、現在の標準的な公理系のもとでは証明も反証もできません。これは選択公理の ZF からの独立性と並ぶ、集合論の深い独立性結果です。

位相空間論との接点

可算・非可算の区別は位相空間論の至るところに現れます。第二可算空間（可算な基底を持つ位相空間）は可分であり、可算個の開集合で位相の構造が決まります。距離空間では第二可算性と可分性が同値になるという重要な結果も、可算性の概念を前提としています。

また、Cantor 集合は非可算集合でありながら Lebesgue 測度が $0$ であるという特異な性質を持ち、測度論と位相空間論の両方で重要な反例を提供します。可算と非可算の境界を理解することは、集合論にとどまらず、解析学や位相空間論の深い結果に触れるための土台となっています。