濃度と無限：全単射で測る「無限の大小」

0. この記事の要点

• 集合の「大きさ」は、要素を数えるのではなく 全単射があるかどうか で比べます。この定義なら、要素を数え終えられない無限集合どうしも比較できます。
• 整数全体 $\mathbb{Z}$ も有理数全体 $\mathbb{Q}$ も、自然数全体 $\mathbb{N}$ と同じ濃度をもちます。$\mathbb{Q}$ は数直線に隙間なく詰まっているのに、番号を振って一列に並べられます。
• 実数全体 $\mathbb{R}$ は $\mathbb{N}$ と同じ濃度をもちません（カントールの対角線論法）。ここで「無限は 1 種類ではない」ことが確定します。
• カントールの定理により、どんな集合 $A$ についても $|A| < |\mathcal{P}(A)|$ です。最大の濃度は存在せず、無限の階層は無限に続きます。
• 「$\mathbb{N}$ と $\mathbb{R}$ の中間の濃度はあるか」という連続体仮説は、ZFC 公理系からは証明も反証もできないことが証明されています（ゲーデル 1938、コーエン 1963）。

1. 動機 — 「同じだけある」を数えずに言う

2 つの集合のどちらが大きいかを判定する最も素朴な方法は、両方の要素を数えて個数を比べることです。しかしこの方法は、要素を数え終えられない集合には使えません。無限集合どうしを比べるには、「数える」以外の道具が要ります。

ガリレオ・ガリレイは『新科学対話』（1638）で次の困惑を書き残しています。自然数 $1, 2, 3, \ldots$ と平方数 $1, 4, 9, \ldots$ を比べます。平方数は自然数のごく一部でしかなく、しかも大きい方へ行くほど疎になります。それなのに $n \mapsto n^2$ という対応によって、両者は漏れも重複もなくぴったり対応してしまいます。ここで 2 つの直観が正面衝突します。

直観	主張	ガリレオの例では
ユークリッド的な直観	全体は部分より大きい	自然数の方が平方数より多い
対応による直観	一対一に対応するものは同じだけある	自然数と平方数は同じだけある

ガリレオはこの衝突から、「等しい・より大きい・より小さいという言葉は無限量には適用できない」と結論しました。19 世紀に入ってボルツァーノが『無限の逆説』（1851、没後出版）で一対一対応そのものを研究対象に据え、最終的にゲオルク・カントールが決着をつけます。彼は矛盾する 2 つの直観のうち、一対一対応の方を残し、「全体は部分より大きい」を捨てました。

捨てた方の直観は失われたわけではありません。デデキントは『数とは何かそして何であるべきか』（1888）で、「自分自身の真部分集合と一対一に対応する」ことを無限集合の定義に採用しました。つまり「全体は部分より大きい」は、有限集合だけで成り立つ性質へと格下げされ、有限と無限を分ける目印になったのです。

この取引の見返りは大きなものでした。もし「無限はすべて同じ大きさ」なら理論は貧しいままですが、カントールは 1874 年に、実数全体が自然数全体と一対一に対応しないことを証明します。無限には少なくとも 2 つの段階がある。この記事では、その発見を定義から最後まで追いかけ、さらに「無限の階層に果てはない」ことと、「$\mathbb{N}$ と $\mathbb{R}$ の間に何があるか」という問いが現代でも決着していない意味を見ます。

2. 準備 — 写像と記号

記号を確認します。$\mathbb{N} = \{1, 2, 3, \ldots\}$ とし、$0$ は含めません。$0$ を込めた集合が必要なときは $\mathbb{N}_0 = \{0\} \cup \mathbb{N}$ と書きます。$\mathbb{Z}, \mathbb{Q}, \mathbb{R}$ はそれぞれ整数・有理数・実数の全体です。$\mathcal{P}(A)$ は $A$ の部分集合全体からなる集合（冪集合）、$B^{A}$ は $A$ から $B$ への写像全体からなる集合を表します。また $n \in \mathbb{N}$ に対し $[n] = \{1, 2, \ldots, n\}$、$[0] = \emptyset$ と書きます。

写像 $f : A \to B$ について、

• $f(x) = f(y) \implies x = y$ が成り立つとき $f$ は単射、
• 任意の $b \in B$ に対し $f(a) = b$ なる $a \in A$ が存在するとき $f$ は全射、
• 単射かつ全射のとき $f$ は全単射

といいます。次の事実を後で繰り返し使います。いずれも定義から直接従います。

1. $f : A \to B$ が全単射であることは、$g \circ f = \mathrm{id}_{A}$ かつ $f \circ g = \mathrm{id}_{B}$ を満たす $g : B \to A$ が存在することと同値です。この $g$ は一意で、$f^{-1}$ と書きます。
2. 単射どうしの合成は単射です（$g(f(x)) = g(f(y))$ から $g$ の単射性で $f(x) = f(y)$、$f$ の単射性で $x = y$）。
3. 単射 $f : A \to B$ は、像への制限 $f : A \to f(A)$ と見れば全単射です。

有限集合の「個数」もここで確認しておきます。集合 $A$ が有限であるとは、ある $n \in \mathbb{N}_0$ について $A$ と $[n]$ の間に全単射が存在することです。このとき $n$ は一意に定まります。$m \ne n$ ならば $[m]$ と $[n]$ の間に全単射は存在しない、という事実（鳩の巣原理）があるからで、これは $n$ についての帰納法で証明できます。この一意性があってはじめて「$A$ の個数は $n$ である」という言い方が意味をもちます。「対象を作る手続きが複数あっても答えが 1 つに定まる」ことを確かめる作業一般については 関係と同値関係、とくに well-defined でない「定義」の例（Example 5.6）［関係と同値関係］ を参照してください。

3. 対等と濃度

Definition 3.1（対等（等濃））

集合 $A$, $B$ に対し、全単射 $f : A \to B$ が少なくとも 1 つ存在するとき、$A$ と $B$ は対等である、あるいは同じ濃度をもつといい、$A \sim B$ または $|A| = |B|$ と書く。

この定義には「数える」という操作が一切現れません。羊の群れと石ころを 1 個ずつ対応させれば、どちらの個数も知らないまま「同じだけある」と言えます。カントールがしたのは、この原始的な比較法を無限集合にそのまま適用することでした。

なお、$|A| = |B|$ という記法は「$|A|$ という量と $|B|$ という量が等しい」ように見えますが、いまの段階では $|A|$ 単独には意味を与えていません。$|A| = |B|$ 全体で「$A \sim B$」の言い換えだと読んでください。この点は後で補足します。

Proposition 3.2（対等の基本性質）

任意の集合 $A$, $B$, $C$ について次が成り立つ。

1. $A \sim A$。
2. $A \sim B$ ならば $B \sim A$。
3. $A \sim B$ かつ $B \sim C$ ならば $A \sim C$。

Proof（Proposition 3.2）

(1) 恒等写像 $\mathrm{id}_{A} : A \to A$ は自分自身を両側逆写像にもつので、準備の事実 1 より全単射です。

(2) $f : A \to B$ を全単射とすると、準備の事実 1 より $g \circ f = \mathrm{id}_{A}$, $f \circ g = \mathrm{id}_{B}$ なる $g = f^{-1} : B \to A$ があります。この 2 式は「$f$ が $g$ の両側逆写像である」とも読めるので、同じ事実 1 を $g$ に適用して $g$ は全単射です。よって $B \sim A$。

(3) $f : A \to B$, $g : B \to C$ を全単射とします。$g \circ f : A \to C$ に対し $f^{-1} \circ g^{-1}$ を考えると、

$$(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ f = \mathrm{id}_{A},$$$$(g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = g \circ g^{-1} = \mathrm{id}_{C}$$

となるので、事実 1 より $g \circ f$ は全単射です。よって $A \sim C$。

∎

Remark 3.3（「濃度」そのものを定義しようとすると）

Proposition 3.2 の 3 条件は 同値関係（Definition 3.1）［関係と同値関係］ の反射律・対称律・推移律そのものです。同値関係があれば同値類が作れるので、「$A$ の濃度」を「$A$ と対等な集合すべての集まり」と定義したくなります。ところが $A \ne \emptyset$ のとき、$A$ と対等な集合はいくらでも大きく作れるため、この集まりは集合になりません（真のクラスです）。素朴に「〜であるものすべての集まり」を集合と呼ぶと破綻することについては 数学の国語 - 集合と論理 の 素朴集合論の限界（Remark 6.4）［The Grammar of Mathematics］ を見てください。

ZFC では、整列可能定理（選択公理と同値）を使って「$A$ と対等な順序数のうち最小のもの」を $|A|$ と定義します。ただし本記事で必要になるのは $|A| = |B|$ と $|A| \le |B|$ という関係の意味だけで、$|A|$ 単独の正体は使いません。「$|A|$ が何であるかを決めないまま $|A| = |B|$ を定義する」のは奇妙に見えますが、比較の規則さえ整合的なら不都合は起きません。

Definition 3.4（濃度の大小）

$A$ から $B$ への単射が存在するとき $|A| \le |B|$ と書く。$|A| \le |B|$ かつ $A \not\sim B$ であるとき $|A| < |B|$ と書く。

$\le$ が反射的であること（恒等写像は単射）と推移的であること（準備の事実 2）はすぐわかります。問題は反対称性、すなわち「$|A| \le |B|$ かつ $|B| \le |A|$ ならば $|A| = |B|$」です。両向きの単射から全単射を作らねばならず、これは自明ではありません。この一点を保証するのが次の定理です。

Theorem 3.5（カントール–シュレーダー–ベルンシュタインの定理）

集合 $A$, $B$ について、単射 $f : A \to B$ と単射 $g : B \to A$ がともに存在するならば、全単射 $h : A \to B$ が存在する。すなわち $|A| \le |B|$ かつ $|B| \le |A|$ ならば $|A| = |B|$ である。

証明は初等的ですが少し長いので、本記事末尾の Appendix に置きました。カントールが 1895 年に主張し、ベルンシュタインが 1897 年に証明を与えました（デデキントは 1887 年に独立に証明していましたが公表していません）。選択公理を使わずに証明できる点が重要です。

この定理の実用上の価値は絶大です。「$A$ と $B$ の間に全単射を具体的に作る」という難しい仕事が、「$A \to B$ の単射」と「$B \to A$ の単射」という易しい仕事 2 つに分解されます。以下ではこの分解を何度も使います。

4. 有限と無限

Definition 4.1（無限集合・デデキント無限）

有限でない集合を無限集合という。また、集合 $A$ が自分自身のある真部分集合と対等であるとき、$A$ はデデキント無限であるという。

Example 4.2（ヒルベルトのホテル）

$\mathbb{N}$ はデデキント無限です。実際、真部分集合 $\mathbb{N} \setminus \{1\} = \{2, 3, 4, \ldots\}$ に対し $f(n) = n + 1$ と定めると、$g(k) = k - 1$ が両側逆写像になります。$g(f(n)) = (n+1) - 1 = n$、$f(g(k)) = (k-1) + 1 = k$ なので、準備の事実 1 より $f$ は全単射です。

これがヒルベルトのホテルの話です。可算無限の客室があり全室が埋まったホテルに新しい客が 1 人来たとき、$n$ 号室の客を $n+1$ 号室へ移せば、誰も追い出さずに 1 号室が空きます。

ガリレオの例も同じ現象です。平方数の集合 $S = \{n^{2} : n \in \mathbb{N}\}$ に対し $\sigma(n) = n^{2}$ は $\mathbb{N} \to S$ の全単射です（$\tau(k) = \sqrt{k}$ が両側逆写像で、$k \in S$ なら $\sqrt{k} \in \mathbb{N}$）。よって $|\mathbb{N}| = |S|$ で、$S \subsetneq \mathbb{N}$ であることと矛盾しません。

デデキント無限な集合は無限集合です。対偶を示します。$A$ が有限、すなわち全単射 $\varphi : [n] \to A$ があるとします。もし $A$ が真部分集合 $S \subsetneq A$ と対等なら、$\varphi^{-1}$ を通して $[n]$ もその真部分集合 $\varphi^{-1}(S) \subsetneq [n]$ と対等になります（Proposition 3.2 の (2)(3) で合成すればよい）。しかし有限集合 $[n]$ が自分の真部分集合と対等になれないことは、$n$ についての帰納法で証明できる基本事実（鳩の巣原理）です。よって $A$ はデデキント無限ではありません。

逆に「無限ならばデデキント無限」も成り立ちますが、こちらは可算選択公理を必要とします（無限集合から要素を 1 個ずつ無限回選び続ける操作が要ります）。ZFC の中では両者は同値なので、以後は区別せず「無限集合」と呼びます。

5. 可算集合 — 整数も有理数も「番号が振れる」

Definition 5.1（可算・高々可算・非可算）

$A \sim \mathbb{N}$ であるとき、$A$ は可算無限であるという。$|A| \le |\mathbb{N}|$、すなわち $A$ から $\mathbb{N}$ への単射が存在するとき、$A$ は高々可算であるという。高々可算でない集合を非可算という。

「高々可算」は「有限または可算無限」と同値です（Exercise 9.2 で証明します）。文献によっては「可算」を「高々可算」の意味で使いますが、本記事では「可算」は常に「可算無限」を指します。

$A$ が可算無限であることは、$A$ の要素に漏れなく重複なく $a_{1}, a_{2}, a_{3}, \ldots$ と番号を振れることと同じです。全単射 $f : \mathbb{N} \to A$ を $a_{n} = f(n)$ と読み替えるだけで、単射性が「重複なく」、全射性が「漏れなく」に対応します。

Example 5.2（整数全体は可算無限）

$f : \mathbb{N} \to \mathbb{Z}$ を

$$f(n) = \begin{cases} \dfrac{n}{2} & (n \text{ が偶数}) \\[6pt] -\dfrac{n-1}{2} & (n \text{ が奇数}) \end{cases}$$

と定めます。並べると $f(1) = 0,\ f(2) = 1,\ f(3) = -1,\ f(4) = 2,\ f(5) = -2, \ldots$ となり、$0$ を起点に左右へ交互に進みます。

これが全単射であることを、両側逆写像を作って確かめます。$g : \mathbb{Z} \to \mathbb{N}$ を $g(k) = 2k$（$k \ge 1$）、$g(k) = -2k+1$（$k \le 0$）と定めます。まず値が $\mathbb{N}$ に入ることを見ます。$k \ge 1$ なら $2k \ge 2$、$k \le 0$ なら $-2k + 1 \ge 1$ です。

$f \circ g = \mathrm{id}_{\mathbb{Z}}$ の確認。$k \ge 1$ のとき $g(k) = 2k$ は偶数なので $f(2k) = 2k/2 = k$。$k \le 0$ のとき $g(k) = -2k+1$ は奇数なので

$$f(-2k+1) = -\frac{(-2k+1)-1}{2} = -\frac{-2k}{2} = k.$$

$g \circ f = \mathrm{id}_{\mathbb{N}}$ の確認。$n$ が偶数のとき $f(n) = n/2 \ge 1$ なので $g(n/2) = 2 \cdot (n/2) = n$。$n$ が奇数のとき $f(n) = -(n-1)/2 \le 0$ なので

$$g\!\left(-\frac{n-1}{2}\right) = -2 \cdot \left(-\frac{n-1}{2}\right) + 1 = (n-1) + 1 = n.$$

準備の事実 1 より $f$ は全単射で、$|\mathbb{Z}| = |\mathbb{N}|$ です。$\mathbb{N} \subsetneq \mathbb{Z}$ なのに濃度が等しい、という Example 4.2 と同じ現象がここでも起きています。

Lemma 5.3（自然数の対の全体は可算）

$\mathbb{N} \times \mathbb{N} \sim \mathbb{N}$ である。

Proof（Lemma 5.3）

両向きの単射を作って Theorem 3.5 を使います。

$\iota : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ を $\iota(n) = (n, 1)$ と定めると、$\iota(n) = \iota(n')$ の第 1 成分を比べて $n = n'$ なので $\iota$ は単射です。よって $|\mathbb{N}| \le |\mathbb{N} \times \mathbb{N}|$。

逆向きは $\gamma : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, $\gamma(m, n) = 2^{m} 3^{n}$ とします。$2^{m} 3^{n} = 2^{m'} 3^{n'}$ とすると、素因数分解の一意性より両辺に現れる素因数 $2$ の指数が等しく $m = m'$、素因数 $3$ の指数が等しく $n = n'$ です。よって $\gamma$ は単射で $|\mathbb{N} \times \mathbb{N}| \le |\mathbb{N}|$。

Theorem 3.5 より全単射が存在します。

∎

$\gamma(m,n) = 2^{m}3^{n}$ は「ゲーデル数」の最も簡単な形です。有限列 $(a_{1}, a_{2}, \ldots, a_{k})$ を $2^{a_{1}} 3^{a_{2}} 5^{a_{3}} \cdots$ という 1 個の自然数に符号化するこの技法は、「証明」や「論理式」といった構文的対象を自然数として算術の中で語るための道具でもあり、不完全性定理の証明の中心にあります。詳しくは 数学基礎論への招待 の ゲーデル数の定義（Definition 4.1）［ゲーデルの不完全性定理］ を参照してください。

Example 5.4（具体的な全単射（カントールの対関数））

Theorem 3.5 は全単射の存在を保証しますが、具体形は教えてくれません。実は $\mathbb{N}_{0} \times \mathbb{N}_{0} \to \mathbb{N}_{0}$ の全単射は明示的に書けます。

$$\pi(m, n) = \frac{(m+n)(m+n+1)}{2} + n.$$

これが全単射である理由を確かめます。$s = m + n$ とおき、$T(s) = s(s+1)/2$ と書きます。和が $s$ である組は

$$(s, 0),\ (s-1, 1),\ \ldots,\ (0, s)$$

の $s+1$ 個で、$\pi$ はこれらを順に $T(s),\ T(s)+1,\ \ldots,\ T(s)+s$ へ写します。ここで

$$T(s) + s = \frac{s(s+1)}{2} + s = \frac{s^{2}+3s}{2}, \qquad T(s+1) - 1 = \frac{(s+1)(s+2)}{2} - 1 = \frac{s^{2}+3s}{2}$$

なので $T(s)+s = T(s+1)-1$ です。つまり $\pi$ は「和が $s$ の対角線」を整数区間 $\{T(s), T(s)+1, \ldots, T(s+1)-1\}$ の上へ全単射的に写します。$T(0) = 0$ であり $T$ は狭義単調増加で $T(s) \to \infty$ なので、これらの整数区間は $\mathbb{N}_{0}$ を重なりなく覆い尽くします。ゆえに $\pi$ は全単射です。

実際に計算すると

$$\pi(0,0) = 0,\quad \pi(1,0) = 1,\quad \pi(0,1) = 2,\quad \pi(2,0) = 3,\quad \pi(1,1) = 4,\quad \pi(0,2) = 5, \ldots$$

となり、対角線を順に舐めていく数え上げになっています。

ℕ₀ × ℕ₀ を対角線に沿って数え上げる。各点に書かれた数が π(m, n) の値。

Theorem 5.5（有理数全体は可算無限）

$\mathbb{Q} \sim \mathbb{N}$ である。

Proof（Theorem 5.5）

ここでも両向きの単射を作ります。

$\mathbb{N} \subseteq \mathbb{Q}$ なので包含写像 $\mathbb{N} \to \mathbb{Q}$ は単射であり、$|\mathbb{N}| \le |\mathbb{Q}|$ です。

逆向きを作ります。任意の $r \in \mathbb{Q}$ は

$$r = \frac{p}{q}, \qquad p \in \mathbb{Z},\ q \in \mathbb{N},\ \gcd(|p|, q) = 1$$

の形にただ一通りに表せます（$r = 0$ のときは $p = 0$, $q = 1$）。この一意性があるおかげで、$r \mapsto (p, q)$ という対応が写像として well-defined になります。約分せずに $2/4$ と $1/2$ を別扱いしてしまうと写像が定まらないので、既約分数表示の一意性は省けない前提です。こうして単射 $\mathbb{Q} \to \mathbb{Z} \times \mathbb{N}$ が得られます。

次に $\mathbb{Z} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ を作ります。Example 5.2 の全単射 $f : \mathbb{N} \to \mathbb{Z}$ の逆写像 $f^{-1} : \mathbb{Z} \to \mathbb{N}$ を使って $(p, q) \mapsto (f^{-1}(p), q)$ と定めれば、これは全単射です（$(m, q) \mapsto (f(m), q)$ が両側逆写像）。

さらに Lemma 5.3 の全単射 $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ を合成します。以上 3 つを合成すると単射 $\mathbb{Q} \to \mathbb{N}$ が得られる（準備の事実 2）ので、$|\mathbb{Q}| \le |\mathbb{N}|$ です。

Theorem 3.5 より $\mathbb{Q} \sim \mathbb{N}$ が従います。

∎

Remark 5.6（稠密なのに数え上げられる）

$\mathbb{Q}$ は数直線上に稠密です。どんな 2 つの実数の間にも有理数があり、有理数どうしの「すぐ隣」は存在しません。それでも Theorem 5.5 により番号を振れます。矛盾ではありません。番号順と大小順が一致しないだけです。実際、$\mathbb{Q}$ を大小順に並べようとすると「次の有理数」がないので最初の一歩で行き詰まりますが、Lemma 5.3 経由の並べ方は大小をまったく無視しています。

「並べられる」は「大小順に並べられる」ではない、という区別は重要です。関連して、可算集合のルベーグ測度は $0$ です。要素を $a_{1}, a_{2}, \ldots$ と並べ、$a_{n}$ を長さ $\varepsilon / 2^{n}$ の区間で覆えば全体の長さは $\varepsilon$ 以下になり、$\varepsilon > 0$ は任意だからです。$\mathbb{Q}$ は数直線に隙間なく分布していながら、長さとしては $0$ しか占めていません。

Proposition 5.7（高々可算集合の可算和）

$A_{1}, A_{2}, A_{3}, \ldots$ をいずれも高々可算な集合とすると、$\bigcup_{n \in \mathbb{N}} A_{n}$ も高々可算である。

Proof（Proposition 5.7）

各 $n$ について $A_{n}$ は高々可算なので、単射 $u_{n} : A_{n} \to \mathbb{N}$ が存在します。各 $n$ に対してそのような $u_{n}$ を 1 つずつ選んで固定します。

$X = \bigcup_{n \in \mathbb{N}} A_{n}$ とおきます。$x \in X$ に対し、$x$ が属する $A_{n}$ の添字のうち最小のものを

$$n(x) = \min \{ n \in \mathbb{N} : x \in A_{n} \}$$

と定めます。この集合は空でなく（$x \in X$ だからどれかの $A_{n}$ に属する）、$\mathbb{N}$ の 整列性（Axiom 3.1）［Techniques of Proof］ より最小元が存在するので、$n(x)$ は定まります。「最小のものを取る」という規約を置くことで、$x$ ごとの選択を避けている点に注意してください。

写像 $U : X \to \mathbb{N} \times \mathbb{N}$ を $U(x) = \bigl(n(x),\, u_{n(x)}(x)\bigr)$ と定めます。$U(x) = U(y)$ とすると、第 1 成分から $n(x) = n(y) =: m$、第 2 成分から $u_{m}(x) = u_{m}(y)$ となり、$u_{m}$ が単射なので $x = y$ です。よって $U$ は単射です。

最後に Lemma 5.3 の全単射 $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ と合成すれば単射 $X \to \mathbb{N}$ が得られ、$X$ は高々可算です。

∎

Caution

上の証明で「各 $n$ に対して単射 $u_{n}$ を 1 つずつ選ぶ」ところは、無限回の選択をしています。$A_{n}$ が具体的に与えられていて単射も具体的に書ける場合は問題ありませんが、一般には可算選択公理が必要です。「可算集合の可算和は可算」という一見当たり前の命題が、実は選択公理なしの ZF では証明できないことが知られています。どの命題がどの公理を使うかを意識するのは、基礎論的な作法として大切です。

Example 5.8（代数的数全体は可算）

実数 $\alpha$ が代数的であるとは、$\alpha$ を根にもつ $0$ でない整数係数多項式が存在することをいいます。$\sqrt{2}$（$x^{2}-2$ の根）や $\sqrt[3]{5} + 1$ などはすべて代数的です。実代数的数の全体を $\mathcal{A}$ と書きます。

まず、$0$ でない整数係数多項式の全体 $P$ が可算であることを見ます。$\mathbb{Z} \sim \mathbb{N}$（Example 5.2）と Lemma 5.3 から、帰納的に $\mathbb{N}^{k} \sim \mathbb{N}$ が従います。実際 $\mathbb{N}^{k+1} \sim \mathbb{N}^{k} \times \mathbb{N} \sim \mathbb{N} \times \mathbb{N} \sim \mathbb{N}$ です。$\mathbb{Z} \sim \mathbb{N}$ と合わせれば $\mathbb{Z}^{d+1} \sim \mathbb{N}^{d+1} \sim \mathbb{N}$ です。よって次数 $d$ 以下の整数係数多項式の全体は $\mathbb{Z}^{d+1}$ の部分集合と 1 対 1 に対応し、高々可算です。$P$ はそれらの $d = 1, 2, 3, \ldots$ にわたる和集合なので、Proposition 5.7 より高々可算です。$P$ は無限集合（$x - n$ が全部入っている）なので、可算無限です。

そこで $P = \{p_{1}, p_{2}, p_{3}, \ldots\}$ と番号を振ります。$p_{n}$ の実根全体を $R_{n}$ と書くと、$0$ でない多項式の根は高々 $\deg p_{n}$ 個しかない（因数定理を繰り返し使う）ので $R_{n}$ は有限集合、とくに高々可算です。定義から

$$\mathcal{A} = \bigcup_{n \in \mathbb{N}} R_{n}$$

なので、Proposition 5.7 より $\mathcal{A}$ は高々可算です。さらに $\mathbb{Q} \subseteq \mathcal{A}$（$r = p/q$ は $qx - p$ の根）で $\mathbb{Q}$ は無限なので、$\mathcal{A}$ は可算無限です。

6. 実数は非可算 — カントールの対角線論法

ここまでに見た無限集合はすべて $\mathbb{N}$ と対等でした。$\mathbb{Z}$ も $\mathbb{Q}$ も、$\mathbb{Q}$ よりはるかに広そうな代数的数全体さえもそうです。ここで「結局のところ無限は 1 種類なのでは」と思いたくなります。カントールが 1874 年に示したのは、そうではないということでした。1891 年に彼が与えた 2 つ目の証明は対角線論法と呼ばれ、初等的で応用範囲が広く、いまでは計算可能性理論や不完全性定理の証明の骨格としても使われています。

証明の前に、小数展開についての事実を整理します。ここを曖昧にしたまま対角線論法を書くと、証明に穴が空きます。

Lemma 6.1（小数展開の存在と、桁を制限したときの一意性）

1. 任意の $x \in [0, 1)$ に対し、$a_{k} \in \{0, 1, \ldots, 9\}$（$k \in \mathbb{N}$）からなる列で $x = \sum_{k=1}^{\infty} a_{k} 10^{-k}$ を満たすものが存在する。
2. $(b_{k})_{k \in \mathbb{N}}$, $(c_{k})_{k \in \mathbb{N}}$ をともに $\{0, 1, \ldots, 9\}$ に値をとる列とし、$\sum_{k=1}^{\infty} b_{k} 10^{-k} = \sum_{k=1}^{\infty} c_{k} 10^{-k}$ が成り立つとする。さらにすべての $k$ で $1 \le b_{k} \le 8$ ならば、すべての $k$ で $b_{k} = c_{k}$ である。

Proof（Lemma 6.1）

(1) $a_{k} = \lfloor 10^{k} x \rfloor - 10 \lfloor 10^{k-1} x \rfloor$ とおきます。$t = 10^{k-1}x$ と書くと

$$a_{k} = \lfloor 10 t \rfloor - 10 \lfloor t \rfloor = \lfloor 10 (t - \lfloor t \rfloor) \rfloor$$

であり、$0 \le t - \lfloor t \rfloor < 1$ から $0 \le 10(t - \lfloor t\rfloor) < 10$、したがって $a_{k} \in \{0, 1, \ldots, 9\}$ です。

部分和は望遠鏡和になります。

$$\sum_{k=1}^{n} a_{k} 10^{-k} = \sum_{k=1}^{n} \left( \frac{\lfloor 10^{k} x \rfloor}{10^{k}} - \frac{\lfloor 10^{k-1} x \rfloor}{10^{k-1}} \right) = \frac{\lfloor 10^{n} x \rfloor}{10^{n}} - \lfloor x \rfloor = \frac{\lfloor 10^{n} x \rfloor}{10^{n}}$$

（最後で $x \in [0,1)$ より $\lfloor x \rfloor = 0$ を使いました）。床関数の定義から $10^{n} x - 1 < \lfloor 10^{n} x \rfloor \le 10^{n} x$ なので

$$\left| x - \frac{\lfloor 10^{n} x \rfloor}{10^{n}} \right| < 10^{-n} \xrightarrow{n \to \infty} 0$$

となり、級数は $x$ に収束します。

(2) $x = \sum b_{k} 10^{-k}$, $y = \sum c_{k}10^{-k}$ とおくと仮定より $x = y$ です。$(b_{k}) \ne (c_{k})$ と仮定して矛盾を導きます。$b_{n} \ne c_{n}$ となる $n$ のうち最小のものを取ると、$k < n$ では $b_{k} = c_{k}$ なので

$$x - y = (b_{n} - c_{n}) 10^{-n} + \sum_{k > n} (b_{k} - c_{k}) 10^{-k}.$$

ここで仮定 $1 \le b_{k} \le 8$ と $0 \le c_{k} \le 9$ から、すべての $k$ で

$$b_{k} - c_{k} \ge 1 - 9 = -8, \qquad b_{k} - c_{k} \le 8 - 0 = 8$$

すなわち $|b_{k} - c_{k}| \le 8$ です。$\sum_{k > n} 10^{-k} = 10^{-n}/9$ なので

$$\left| \sum_{k > n} (b_{k} - c_{k}) 10^{-k} \right| \le 8 \sum_{k>n} 10^{-k} = \frac{8}{9} \cdot 10^{-n}.$$

一方 $b_{n} \ne c_{n}$ はどちらも整数なので $|b_{n} - c_{n}| \ge 1$ です。三角不等式より

$$|x - y| \ge 10^{-n} - \frac{8}{9} \cdot 10^{-n} = \frac{1}{9} \cdot 10^{-n} > 0$$

となり、$x = y$ に反します。よって $(b_{k}) = (c_{k})$ です。

∎

Remark 6.2（小数展開は一意ではない）

(2) で「$1 \le b_{k} \le 8$」という条件が要るのは、小数展開が一般には一意でないからです。実際

$$\sum_{k \ge 2} 9 \cdot 10^{-k} = 9 \cdot \frac{10^{-1}}{9} = \frac{1}{10}$$

なので $0.0999\cdots$ と $0.1000\cdots$ は同じ実数を表します。有名な $0.999\cdots = 1$ と同じ現象です。Lemma 6.1 の (2) は「桁に $0$ と $9$ を使わなければ一意になる」と主張しています。この一手間を省くと、次の定理の証明は「作った数が本当にリストのどれとも違う」と言い切れなくなります。$1 = 0.999\cdots$ が等式として何を意味するかについては 数とは何か？ (1=0.999…？) の Theorem 6.3［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］ を参照してください。

Theorem 6.3（実数全体は非可算（カントールの対角線論法））

区間 $[0, 1)$ は非可算である。したがって $\mathbb{R}$ も非可算である。より詳しくは、どんな写像 $F : \mathbb{N} \to [0, 1)$ も全射ではない。

対角線論法。n 番目の数の第 n 桁を必ずずらすことで、リストのどれとも異なる数を作る。

Proof（Theorem 6.3）

$F : \mathbb{N} \to [0,1)$ を任意の写像とし、$x_{n} = F(n)$ とおきます。

第 1 段階（桁を取り出す）。 各 $n$ に対し、Lemma 6.1 の (1) の構成

$$a_{nk} = \lfloor 10^{k} x_{n} \rfloor - 10 \lfloor 10^{k-1} x_{n} \rfloor \in \{0, 1, \ldots, 9\}$$

を使って $x_{n} = \sum_{k=1}^{\infty} a_{nk} 10^{-k}$ と展開します。展開を「選ぶ」のではなく明示式で一斉に定めているので、選択公理は要りません。

第 2 段階（対角線をずらす）。

$$b_{n} = \begin{cases} 5 & (a_{nn} \ne 5) \\ 4 & (a_{nn} = 5) \end{cases}$$

と定め、$y = \sum_{n=1}^{\infty} b_{n} 10^{-n}$ とおきます。$b_{n} \in \{4, 5\}$ なので級数は収束し、$\sum_{n \ge 1} 10^{-n} = 1/9$ より

$$\frac{4}{9} \le y \le \frac{5}{9} < 1$$

となって $y \in [0, 1)$ です。

第 3 段階（リストに載っていないことの確認）。 ある $m \in \mathbb{N}$ で $y = x_{m}$ になったと仮定します。すると

$$\sum_{k=1}^{\infty} b_{k} 10^{-k} = \sum_{k=1}^{\infty} a_{mk} 10^{-k}$$

であり、$b_{k} \in \{4, 5\} \subseteq \{1, \ldots, 8\}$ なので Lemma 6.1 の (2) が適用できて、すべての $k$ で $b_{k} = a_{mk}$ です。とくに $k = m$ として $b_{m} = a_{mm}$。ところが $b_{m}$ の定め方から、$a_{mm} = 5$ のときは $b_{m} = 4 \ne 5 = a_{mm}$、$a_{mm} \ne 5$ のときは $b_{m} = 5 \ne a_{mm}$ で、いずれにせよ $b_{m} \ne a_{mm}$ です。矛盾しました。

よって $y$ は $F$ の像に属さず、$F$ は全射ではありません。

第 4 段階（非可算性への翻訳）。 $[0,1)$ が高々可算だと仮定すると、単射 $u : [0,1) \to \mathbb{N}$ が存在します。$x_{0} = 0 \in [0,1)$ を固定し、$G : \mathbb{N} \to [0,1)$ を、$n$ が $u$ の像に属するときは（$u$ の単射性から一意に定まる）その原像、属さないときは $x_{0}$、と定めます。すると任意の $x \in [0,1)$ に対し $G(u(x)) = x$ なので $G$ は全射で、これは上で示したことに反します。ゆえに $[0,1)$ は非可算です。

最後に $\mathbb{R}$ について。もし $\mathbb{R}$ が高々可算なら単射 $v : \mathbb{R} \to \mathbb{N}$ があり、その $[0,1)$ への制限も単射なので $[0,1)$ が高々可算になってしまいます。よって $\mathbb{R}$ も非可算です。

∎

Corollary 6.4（超越数の存在）

代数的でない実数（超越数）が存在する。それどころか、超越数全体は非可算である。

Proof（Corollary 6.4）

実代数的数の全体 $\mathcal{A}$ は Example 5.8 より高々可算です。$\mathbb{R} \setminus \mathcal{A}$ が高々可算だと仮定すると、$A_{1} = \mathcal{A}$, $A_{2} = \mathbb{R} \setminus \mathcal{A}$, $A_{3} = A_{4} = \cdots = \emptyset$ として Proposition 5.7 を適用でき（$\emptyset$ は高々可算です。空写像 $\emptyset \to \mathbb{N}$ は単射だからです）、$\mathbb{R} = A_{1} \cup A_{2}$ が高々可算になります。これは Theorem 6.3 に矛盾します。よって $\mathbb{R} \setminus \mathcal{A}$ は非可算で、とくに空ではありません。

∎

これが 1874 年のカントールの論文の主目的でした。リウヴィルは 1844 年に超越数の具体例を構成していましたが、カントールの議論は「代数的数は数え上げられるが実数は数え上げられない、だから隙間がある」というだけで、超越数を 1 個も具体的に作らずにその存在を、しかも「圧倒的多数である」ことまで示します。存在証明と構成的証明の違いを示す古典的な例です。証明の型については 証明の技術 - 数学的帰納法と背理法 を参照してください。

Definition 6.5（連続体濃度）

$\mathbb{R}$ の濃度を連続体濃度といい $\mathfrak{c} = |\mathbb{R}|$ と書く。また $\aleph_{0} = |\mathbb{N}|$ と書く。

Theorem 6.3 は $\aleph_{0} < \mathfrak{c}$ を意味します。包含写像 $\mathbb{N} \to \mathbb{R}$ は単射なので $\aleph_{0} \le \mathfrak{c}$ であり、対等でないことが示されたので Definition 3.4 の意味で狭義の不等号が成り立ちます。

Proposition 6.6（連続体濃度は自然数の冪集合の濃度）

$|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$ である。

Proof（Proposition 6.6）

両向きの単射を作り Theorem 3.5 を使います。

$|\mathcal{P}(\mathbb{N})| \le |\mathbb{R}|$ を示します。$S \subseteq \mathbb{N}$ に対し、桁を

$$b^{S}_{k} = \begin{cases} 2 & (k \in S) \\ 1 & (k \notin S) \end{cases}$$

と定め、$\Phi(S) = \sum_{k=1}^{\infty} b^{S}_{k} 10^{-k}$ とおきます。$S \ne T$ ならば一方にだけ属する $k$ があり、そこで $b^{S}_{k} \ne b^{T}_{k}$ です。すべての $k$ で $1 \le b^{S}_{k} \le 8$ なので、もし $\Phi(S) = \Phi(T)$ なら Lemma 6.1 の (2) からすべての $k$ で $b^{S}_{k} = b^{T}_{k}$ となって矛盾します。よって $\Phi$ は単射です。

$|\mathbb{R}| \le |\mathcal{P}(\mathbb{N})|$ を示します。$x \in \mathbb{R}$ に対し

$$L(x) = \{ q \in \mathbb{Q} : q < x \} \in \mathcal{P}(\mathbb{Q})$$

を対応させます。$x \ne y$、たとえば $x < y$ とすると、有理数の稠密性（Proposition 5.5）［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］ より $x < q < y$ なる $q \in \mathbb{Q}$ があり、この $q$ は $L(y)$ に属して $L(x)$ に属さないので $L(x) \ne L(y)$ です。よって $L$ は単射で $|\mathbb{R}| \le |\mathcal{P}(\mathbb{Q})|$ です。

さらに Theorem 5.5 の全単射 $\varphi : \mathbb{N} \to \mathbb{Q}$ を使うと、$\mathcal{P}(\mathbb{Q}) \to \mathcal{P}(\mathbb{N})$, $S \mapsto \varphi^{-1}(S)$ は全単射です（$T \mapsto \varphi(T)$ が両側逆写像。$\varphi$ が全単射なので $\varphi^{-1}(\varphi(T)) = T$ と $\varphi(\varphi^{-1}(S)) = S$ がともに成り立ちます）。したがって $|\mathcal{P}(\mathbb{Q})| = |\mathcal{P}(\mathbb{N})|$ で、$|\mathbb{R}| \le |\mathcal{P}(\mathbb{N})|$ を得ます。

Theorem 3.5 より $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|$ です。

∎

部分集合 $S \subseteq \mathbb{N}$ にその特性関数 $\chi_{S} : \mathbb{N} \to \{0, 1\}$ を対応させる写像は $\mathcal{P}(\mathbb{N}) \to \{0,1\}^{\mathbb{N}}$ の全単射です（逆は $\chi \mapsto \chi^{-1}(\{1\})$）。そこで $|\{0,1\}^{\mathbb{N}}|$ を $2^{\aleph_{0}}$ と書く習慣があり、Proposition 6.6 は

$$\mathfrak{c} = 2^{\aleph_{0}}$$

と表せます。この記法は次節と連続体仮説の定式化で使います。

7. カントールの定理 — 無限に最大はない

$\aleph_{0} < \mathfrak{c}$ がわかりました。では、この 2 つで打ち止めでしょうか。答えは「いいえ」で、しかも決定的な形で「いいえ」です。

Theorem 7.1（カントールの定理）

任意の集合 $A$ について $|A| < |\mathcal{P}(A)|$ である。すなわち、$A$ から $\mathcal{P}(A)$ への単射は存在するが、$A$ から $\mathcal{P}(A)$ への全射は存在しない。

Proof（Theorem 7.1）

まず $\sigma(a) = \{a\}$ で定まる $\sigma : A \to \mathcal{P}(A)$ は単射です。$\{a\} = \{a'\}$ なら $a \in \{a\} = \{a'\}$ より $a = a'$ だからです。よって $|A| \le |\mathcal{P}(A)|$。

次に、任意の写像 $f : A \to \mathcal{P}(A)$ が全射でないことを示します。

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

とおきます。$D \subseteq A$ なので $D \in \mathcal{P}(A)$ です。もし $D = f(a_{0})$ なる $a_{0} \in A$ が存在したとします。

• $a_{0} \in D$ の場合。$D$ の定義より $a_{0} \notin f(a_{0})$ です。しかし $f(a_{0}) = D$ なので $a_{0} \notin D$ となり、$a_{0} \in D$ に矛盾します。
• $a_{0} \notin D$ の場合。$D$ の定義より「$a_{0} \notin f(a_{0})$」が成り立たない、つまり $a_{0} \in f(a_{0}) = D$ です。これは $a_{0} \notin D$ に矛盾します。

$a_{0} \in D$ か $a_{0} \notin D$ のどちらかは必ず成り立つのに、どちらも矛盾を導きました。よってそのような $a_{0}$ は存在せず、$D$ は $f$ の像に属しません。ゆえに $f$ は全射ではありません。

全単射は全射でもあるので、$A$ から $\mathcal{P}(A)$ への全単射も存在せず、$A \not\sim \mathcal{P}(A)$ です。Definition 3.4 より $|A| < |\mathcal{P}(A)|$ が従います。

∎

Remark 7.2（濃度に最大はなく、「すべての集合の集合」もない）

Theorem 7.1 を繰り返し適用すると

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

という、いくらでも大きくなる濃度の列が得られます。最大の濃度は存在しません。無限は 2 種類どころか、無限に多くの段階をもちます。

このことは「すべての集合からなる集合」$V$ が存在しないことも導きます。もし $V$ が集合なら、$\mathcal{P}(V)$ の元はどれも集合なので $\mathcal{P}(V) \subseteq V$ となり、包含写像が単射を与えて $|\mathcal{P}(V)| \le |V|$。これは Theorem 7.1 に反します（カントールのパラドックス、1899）。素朴集合論がなぜ公理化を必要としたかについては 数学の国語 - 集合と論理 を見てください。

なお Theorem 7.1 の証明で使った $D = \{a : a \notin f(a)\}$ という作り方は、ラッセルのパラドックスの $\{x : x \notin x\}$ と同じ骨格をしています。同じ骨格は、不完全性定理の証明で「自分自身の証明不可能性を述べる文」を作る 対角化補題（Lemma 4.3）［ゲーデルの不完全性定理］ にも現れます（数学基礎論への招待）。対角線論法は、パラドックスを定理に変える技法だと言えます。

8. 連続体仮説 — 中間の無限はあるか

$\aleph_{0} < \mathfrak{c}$ が確定しました。次に自然に浮かぶ問いは、その間に何かあるかです。

連続体仮説 (CH): $\aleph_{0} < \kappa < \mathfrak{c}$ を満たす濃度 $\kappa$ は存在しない。

ZFC の中では、これは次の言い換えと同値です。「$\mathbb{R}$ の任意の部分集合 $S$ は、高々可算であるか、さもなければ $\mathbb{R}$ と対等である。」中途半端な大きさの実数の集合は作れない、という主張です。

カントールは 1878 年にこの予想を提出し、生涯かけて証明を試みましたが果たせませんでした。ヒルベルトは 1900 年のパリ国際数学者会議で 23 の問題を掲げた際、その第 1 問題に連続体仮説を置いています。

決着は 2 段階でつきました。

年	誰が	何を示したか	帰結
1938–1940	ゲーデル	ZF の内部に「構成可能集合」の宇宙 $L$ を作り、$L$ が ZFC と一般連続体仮説を満たすことを示した	ZF が無矛盾なら ZFC + CH も無矛盾。CH は反証できない
1963	コーエン	強制法 (forcing) を発明し、ZFC のモデルから $\mathfrak{c} = \aleph_{2}$ となる新しいモデルを作った	ZFC が無矛盾なら ZFC + ¬CH も無矛盾。CH は証明できない

両者を合わせると、連続体仮説は ZFC から独立です。コーエンはこの仕事により 1966 年にフィールズ賞を受賞しました。数理論理学の業績に対してフィールズ賞が贈られたのは、いまのところこの 1 例だけです。

Note

「独立」は「真か偽か分からない」という意味ではありません。「ZFC という公理の集まりからは、CH も ¬CH も導けない」ことが定理として証明された、という意味です。ユークリッド幾何の平行線公理が他の公理から独立で、それを認めても否定しても無矛盾な幾何学が得られたのと、同じ構図です。

ゲーデルの第 1 不完全性定理は「十分強い無矛盾な体系には決定不能な命題が存在する」ことを一般的に述べますが、その証明で作られる命題は自己言及的で人工的です。連続体仮説は、数学者が自然な動機から提出した命題が実際に独立だと示された最初の例であり、独立性が「例外的な病理」ではないことを知らせました。詳しくは 数学基礎論への招待 を参照してください。

では連続体仮説は無意味な問いなのでしょうか。そうではありません。2 つの方向で研究が続いています。

第 1 に、「単純な」集合に限れば連続体仮説は定理です。カントールとベンディクソンは、$\mathbb{R}$ の閉集合が完全集合と可算集合の和に分解できることを示しました。この結果から、非可算な閉集合は必ず完全集合を含み、したがって濃度 $\mathfrak{c}$ をもちます。閉集合の世界には中間の濃度が現れないのです。この性質は後にボレル集合へ、さらにスースリン（1917）によって解析集合へと拡張されました。中間の濃度をもつ集合があるとしても、それは相当に「記述しにくい」集合でなければなりません。

第 2 に、新しい公理を足す立場があります。ゲーデル自身は 1947 年の論説「カントールの連続体問題とは何か」で、CH は偽だろうと述べています。現代の集合論では、強制公理と呼ばれる一群の公理が研究されており、たとえば固有強制公理 (PFA) からは $\mathfrak{c} = \aleph_{2}$ が従うことが知られています。どの公理を採用すべきかという問いは、集合論の宇宙をどう思い描くかという問題と結びついていて、いまも決着していません。

独立という結果に落胆する必要はありません。第 5 公準の独立性が非ユークリッド幾何という豊かな世界を開いたように、連続体仮説の独立性は「集合論の宇宙は 1 つに定まらない」という視点を数学にもたらしました。ガリレオが放棄した無限の比較は、カントールによって理論になり、さらに「その理論だけでは答えの決まらない問い」を生むところまで来たのです。

9. 演習

Exercise 9.1易

無理数全体 $\mathbb{R} \setminus \mathbb{Q}$ が非可算であることを示してください。

Solution

$\mathbb{R} \setminus \mathbb{Q}$ が高々可算だと仮定します。$\mathbb{Q}$ は Theorem 5.5 より可算無限、とくに高々可算です。そこで $A_{1} = \mathbb{Q}$, $A_{2} = \mathbb{R} \setminus \mathbb{Q}$, $A_{3} = A_{4} = \cdots = \emptyset$ とおくと（$\emptyset$ は高々可算です。空写像 $\emptyset \to \mathbb{N}$ が単射だからです）、Proposition 5.7 より

$$\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q}) = \bigcup_{n \in \mathbb{N}} A_{n}$$

は高々可算になります。これは Theorem 6.3 に矛盾します。よって $\mathbb{R} \setminus \mathbb{Q}$ は非可算です。

「有理数は可算、実数は非可算」なので、実数の非可算性はすべて無理数側が担っていることになります。

Exercise 9.2標準

$S \subseteq \mathbb{N}$ が無限集合ならば $S \sim \mathbb{N}$ であることを示してください。またこれを使って、「高々可算」（$\mathbb{N}$ への単射が存在する）が「有限または可算無限」と同値であることを示してください。

Solution

前半。 $s_{1} = \min S$ とし、$s_{k+1} = \min \bigl( S \setminus \{s_{1}, \ldots, s_{k}\} \bigr)$ と再帰的に定めます。$S$ は無限なので $S \setminus \{s_{1}, \ldots, s_{k}\}$ は空でなく、$\mathbb{N}$ の整列性より最小元が存在するので、この定義は各段階で意味をもちます。

まず $s_{k} < s_{k+1}$ です。実際 $s_{k+1} \in S \setminus \{s_{1}, \ldots, s_{k}\} \subseteq S \setminus \{s_{1}, \ldots, s_{k-1}\}$ であり、$s_{k}$ は後者の最小元なので $s_{k} \le s_{k+1}$。さらに $s_{k+1} \ne s_{k}$（$s_{k}$ は取り除かれている）なので $s_{k} < s_{k+1}$ です。よって写像 $\psi(k) = s_{k}$ は狭義単調増加、とくに単射です。

次に全射性を示します。まず帰納法で $s_{k} \ge k$ が言えます（$s_{1} \ge 1$、$s_{k+1} > s_{k} \ge k$ より $s_{k+1} \ge k+1$）。$s \in S$ を任意に取ると $s_{s+1} \ge s+1 > s$ なので、集合 $K = \{k \in \mathbb{N} : s_{k} \ge s\}$ は空でなく、最小元 $k_{0}$ をもちます。

• $k_{0} = 1$ のとき。$s_{1} = \min S \le s$ で、かつ $s_{1} \ge s$ なので $s_{1} = s$。
• $k_{0} > 1$ のとき。$k_{0}$ の最小性より $s_{k_{0}-1} < s$、したがって $s_{1} < \cdots < s_{k_{0}-1} < s$ なので $s \notin \{s_{1}, \ldots, s_{k_{0}-1}\}$、すなわち $s \in S \setminus \{s_{1}, \ldots, s_{k_{0}-1}\}$。$s_{k_{0}}$ はこの集合の最小元なので $s_{k_{0}} \le s$。$s_{k_{0}} \ge s$ と合わせて $s_{k_{0}} = s$。

いずれの場合も $s$ は $\psi$ の像に入るので $\psi$ は全射です。よって $\psi$ は全単射で $S \sim \mathbb{N}$。

後半。 $A$ を高々可算とし、単射 $u : A \to \mathbb{N}$ を取ります。準備の事実 3 より $A \sim u(A)$ で、$u(A) \subseteq \mathbb{N}$ です。$u(A)$ が有限なら $A$ も有限です。$u(A)$ が無限なら前半より $u(A) \sim \mathbb{N}$ なので、Proposition 3.2 の (3) から $A \sim \mathbb{N}$、すなわち可算無限です。

逆に、$A$ が有限なら $A \sim [n]$ で、$[n] \subseteq \mathbb{N}$ の包含と合成して単射 $A \to \mathbb{N}$ が作れます。$A$ が可算無限なら全単射 $A \to \mathbb{N}$ 自身が単射です。どちらの場合も $A$ は高々可算です。

Exercise 9.3標準

閉区間 $[0, 1]$ と $\mathbb{R}$ が対等であることを示してください。

Solution

包含写像 $[0,1] \to \mathbb{R}$ は単射なので $|[0,1]| \le |\mathbb{R}|$ です。

逆向きの単射を作ります。$\psi(x) = \dfrac{1}{2} + \dfrac{1}{\pi} \arctan x$ とおきます。$\arctan : \mathbb{R} \to (-\pi/2, \pi/2)$ は狭義単調増加なので $\psi$ も狭義単調増加で、とくに単射です。値域については $-\pi/2 < \arctan x < \pi/2$ から

$$0 = \frac{1}{2} - \frac{1}{2} < \psi(x) < \frac{1}{2} + \frac{1}{2} = 1$$

なので $\psi(\mathbb{R}) \subseteq (0,1) \subseteq [0,1]$ です。よって $\psi$ は $\mathbb{R} \to [0,1]$ の単射で $|\mathbb{R}| \le |[0,1]|$。

Theorem 3.5 より全単射が存在し、$[0,1] \sim \mathbb{R}$ です。

$[0,1]$ と $\mathbb{R}$ の間の全単射を具体的に書くこともできます（端点をずらすために可算個の点を動かす必要があります）が、CSB を使えばその工夫は要りません。これがこの定理の典型的な使い方です。

Exercise 9.4難

$C(\mathbb{R}) = \{ f : \mathbb{R} \to \mathbb{R} \mid f \text{ は連続} \}$ の濃度が $\mathfrak{c}$ であることを示してください。

Solution

$\mathfrak{c} \le |C(\mathbb{R})|$。 実数 $c$ に定数関数 $x \mapsto c$ を対応させる写像は $\mathbb{R} \to C(\mathbb{R})$ の単射です（$c \ne c'$ なら値が違うので関数として異なります）。

$|C(\mathbb{R})| \le \mathfrak{c}$。 制限写像 $R : C(\mathbb{R}) \to \mathbb{R}^{\mathbb{Q}}$, $R(f) = f|_{\mathbb{Q}}$ が単射であることを示します。$f|_{\mathbb{Q}} = g|_{\mathbb{Q}}$ とし、$x \in \mathbb{R}$ を任意に取ります。$\mathbb{Q}$ の稠密性より $q_{n} \to x$ なる有理数列が取れ、$f$, $g$ の連続性から

$$f(x) = \lim_{n \to \infty} f(q_{n}) = \lim_{n \to \infty} g(q_{n}) = g(x)$$

です。$x$ は任意なので $f = g$ で、$R$ は単射です。連続関数は稠密集合上の値だけで完全に決まる、という事実がここでの要点です。

あとは $|\mathbb{R}^{\mathbb{Q}}| = \mathfrak{c}$ を見れば十分です。Theorem 5.5 の全単射 $\varphi : \mathbb{N} \to \mathbb{Q}$ により $F \mapsto F \circ \varphi$ は $\mathbb{R}^{\mathbb{Q}} \to \mathbb{R}^{\mathbb{N}}$ の全単射です（$G \mapsto G \circ \varphi^{-1}$ が両側逆写像）。また Proposition 6.6 と特性関数による全単射から $\mathbb{R} \sim \{0,1\}^{\mathbb{N}}$ です。全単射 $\beta : \mathbb{R} \to \{0,1\}^{\mathbb{N}}$ は $F \mapsto \beta \circ F$ という全単射 $\mathbb{R}^{\mathbb{N}} \to (\{0,1\}^{\mathbb{N}})^{\mathbb{N}}$ を誘導します。したがって

$$\mathbb{R}^{\mathbb{Q}} \sim \mathbb{R}^{\mathbb{N}} \sim (\{0,1\}^{\mathbb{N}})^{\mathbb{N}} \sim \{0,1\}^{\mathbb{N} \times \mathbb{N}} \sim \{0,1\}^{\mathbb{N}} \sim \mathbb{R}.$$

3 つ目の対等は「カリー化」で、$H \in (\{0,1\}^{\mathbb{N}})^{\mathbb{N}}$ に $\Lambda(H)(n, m) = H(n)(m)$ で定まる $\Lambda(H) : \mathbb{N} \times \mathbb{N} \to \{0,1\}$ を対応させる写像が全単射です（$K \mapsto \bigl( n \mapsto (m \mapsto K(n,m)) \bigr)$ が両側逆写像）。4 つ目は Lemma 5.3 の全単射 $\theta : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ による $K \mapsto K \circ \theta$ です。

以上と Proposition 3.2 の推移性から $|C(\mathbb{R})| \le |\mathbb{R}^{\mathbb{Q}}| = \mathfrak{c}$ です。Theorem 3.5 より $|C(\mathbb{R})| = \mathfrak{c}$。

念のため補足すると、連続とは限らない関数全体 $\mathbb{R}^{\mathbb{R}}$ の濃度は $\mathfrak{c}$ より真に大きくなります。連続性という条件が、関数の「個数」を実数と同じ水準まで抑え込んでいるわけです。

参考文献

• 松坂和夫『集合・位相入門』岩波書店、1968 — 濃度、可算集合、カントール–ベルンシュタインの定理を丁寧に扱っています。
• 内田伏一『集合と位相』裳華房、1986 — 濃度の基本事項を簡潔にまとめています。
• R. Dedekind, Was sind und was sollen die Zahlen?, Vieweg, 1888（邦訳: 渕野昌 訳・解説『数とは何かそして何であるべきか』ちくま学芸文庫、2013）— 無限集合を「真部分集合と対等な集合」と定義した原典。
• G. Cantor, “Über eine elementare Frage der Mannigfaltigkeitslehre”, Jahresbericht der Deutschen Mathematiker-Vereinigung 1 (1891), 75–78 — 対角線論法が初めて現れた論文。
• K. Gödel, The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory, Annals of Mathematics Studies 3, Princeton University Press, 1940 — 構成可能集合による無矛盾性証明。
• P. J. Cohen, “The independence of the continuum hypothesis”, Proceedings of the National Academy of Sciences USA 50 (1963), 1143–1148; 同 II, 51 (1964), 105–110 — 強制法の原論文。
• T. Jech, Set Theory, 3rd millennium edition, Springer, 2003 — 基数・強制法・連続体仮説の現代的な標準教科書。

Appendix: カントール–シュレーダー–ベルンシュタインの定理の証明

Proof（Theorem 3.5）

単射 $f : A \to B$ と単射 $g : B \to A$ が与えられているとします。

$A$ の部分集合の列を

$$C_{0} = A \setminus g(B), \qquad C_{n+1} = g\bigl(f(C_{n})\bigr) \quad (n \in \mathbb{N}_{0})$$

と定め、$C = \bigcup_{n \in \mathbb{N}_{0}} C_{n}$ とおきます。$C_{0}$ は「$g$ の像に入っていない $A$ の元」の集まりで、$C_{n+1}$ はそれを $g \circ f$ で $n+1$ 回送った先です。

写像 $h : A \to B$ を

$$h(a) = \begin{cases} f(a) & (a \in C) \\ g^{-1}(a) & (a \notin C) \end{cases}$$

と定めます。まずこれが well-defined であることを確認します。$a \notin C$ ならば、とくに $a \notin C_{0} = A \setminus g(B)$ なので $a \in g(B)$、つまり $a = g(b)$ なる $b \in B$ が存在します。$g$ は単射なのでこの $b$ は一意に定まり、それを $g^{-1}(a)$ と書いています。

$h$ は単射である。 $h(a) = h(a')$ とします。

• $a, a' \in C$ のとき。$f(a) = f(a')$ で $f$ は単射なので $a = a'$。
• $a, a' \notin C$ のとき。$g^{-1}(a) = g^{-1}(a')$ の両辺に $g$ を施すと $a = a'$。
• $a \in C$ かつ $a' \notin C$ のとき。$f(a) = g^{-1}(a')$ の両辺に $g$ を施すと $g(f(a)) = a'$ です。$a \in C$ なのである $n \in \mathbb{N}_{0}$ で $a \in C_{n}$ であり、したがって $$a' = g(f(a)) \in g\bigl(f(C_{n})\bigr) = C_{n+1} \subseteq C$$ となります。これは $a' \notin C$ に反するので、この場合は起こりません。
• $a \notin C$ かつ $a' \in C$ のときも、$a$ と $a'$ の役割を入れ替えれば同じ議論で起こり得ません。

以上より $h$ は単射です。

$h$ は全射である。 $b \in B$ を任意に取り、$a = g(b) \in A$ とおきます。

• $a \in C$ のとき。ある $n \in \mathbb{N}_{0}$ で $a \in C_{n}$ です。$n = 0$ はあり得ません。$C_{0} = A \setminus g(B)$ ですが $a = g(b) \in g(B)$ だからです。よって $n = m+1$ と書けて $a \in C_{m+1} = g(f(C_{m}))$、つまり $a = g(f(c))$ なる $c \in C_{m}$ が存在します。$g$ は単射で $g(b) = a = g(f(c))$ なので $b = f(c)$ です。$c \in C_{m} \subseteq C$ なので $h(c) = f(c) = b$ となり、$b$ は $h$ の像に入ります。
• $a \notin C$ のとき。$h(a) = g^{-1}(a) = g^{-1}(g(b)) = b$ なので、$b$ は $h$ の像に入ります。

いずれの場合も $b \in h(A)$ なので、$h$ は全射です。

したがって $h : A \to B$ は全単射で、$|A| = |B|$ が示されました。この証明では選択公理を一切使っていません。$C_{n}$ の定義も $h$ の定義も、与えられた $f$, $g$ から一意に決まる構成だからです。

∎