濃度

この章の目標

• 全単射によって集合の「大きさ」を比べる考え方（対等・濃度）を理解する
• 鳩の巣原理を証明し、有限集合の元の個数が矛盾なく定まることを説明できる
• $\mathbb{Z}$、$\mathbb{N} \times \mathbb{N}$、$\mathbb{Q}$ が可算であること、可算集合の可算和が（選択公理のもとで）可算であることを証明できる
• 対角線論法により $\mathbb{R}$ の非可算性とカントールの定理を証明できる
• ベルンシュタインの定理を証明し、$\lvert \mathbb{R} \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert = \lvert \mathbb{R}^2 \rvert$ を導ける

前提：第3章（特に全単射・逆写像・定理 3.32）、第4章

有限集合の大きさは元の個数で測れる。では $\mathbb{N}$ と $\mathbb{Z}$、$\mathbb{Q}$ と $\mathbb{R}$ ではどちらが「多い」のだろうか。無限集合では「数える」ことができないので、代わりに一対一に対応させられるかで大きさを比べる。この単純な考え方から、無限にも大小があること、$\mathbb{Q}$ は $\mathbb{N}$ と同じ大きさだが $\mathbb{R}$ はそれより真に大きいこと、しかも最大の無限は存在しないことが導かれる。19 世紀後半にカントール (G. Cantor) が切り開いたこの理論は、解析学（ルベーグ測度）や位相空間論で繰り返し使われる。

5.1 対等と濃度

定義 5.1（対等・濃度の比較）集合 $X, Y$ の間に全単射 $X \to Y$ が存在するとき、$X$ と $Y$ は対等 (equinumerous) である、または濃度 (cardinality) が等しいといい、$X \sim Y$ あるいは $\lvert X \rvert = \lvert Y \rvert$ と書く。単射 $X \to Y$ が存在するとき $\lvert X \rvert \leq \lvert Y \rvert$ と書き、$\lvert X \rvert \leq \lvert Y \rvert$ かつ $\lvert X \rvert \neq \lvert Y \rvert$ のとき $\lvert X \rvert < \lvert Y \rvert$ と書く。

本教材では $\lvert X \rvert$ そのものを数学的対象として定義することはせず、「$\lvert X \rvert = \lvert Y \rvert$」「$\lvert X \rvert \leq \lvert Y \rvert$」を上の関係の記号として使う。濃度は基数 (cardinal number) とも呼ばれる。

定理 5.2 集合 $X, Y, Z$ について次が成り立つ。

1. $X \sim X$。$X \sim Y$ ならば $Y \sim X$。$X \sim Y$ かつ $Y \sim Z$ ならば $X \sim Z$。
2. $\lvert X \rvert \leq \lvert Y \rvert$ かつ $\lvert Y \rvert \leq \lvert Z \rvert$ ならば $\lvert X \rvert \leq \lvert Z \rvert$。$X \subset Y$ ならば $\lvert X \rvert \leq \lvert Y \rvert$。

証明. (1) 恒等写像、逆写像（定理 3.18）、全単射の合成（定理 3.18 (3)）による。(2) 単射の合成は単射であり（定理 3.16）、包含写像は単射である。$\square$

(1) は $\sim$ が同値関係の性質をもつことを示しているが、「すべての集合の集まり」は集合でないので（系 2.26）、厳密には第4章の意味での同値関係ではない。

例 5.3

1. 正の偶数全体 $E = \lbrace 2, 4, 6, \dots \rbrace$ について、$n \mapsto 2n$ は全単射 $\mathbb{N} \to E$ なので $\mathbb{N} \sim E$ である。全体とその真部分集合が対等になりうるのが無限集合の特徴である。
2. $a < b$ のとき $t \mapsto a + (b - a)t$ は全単射 $(0, 1) \to (a, b)$ なので、開区間はどれも対等である。
3. $g\colon (-1, 1) \to \mathbb{R}$、$g(x) = x/(1 - \lvert x \rvert)$ は全単射である。実際 $h\colon \mathbb{R} \to (-1, 1)$、$h(y) = y/(1 + \lvert y \rvert)$ とおくと（$\lvert h(y) \rvert < 1$ に注意）、

となり、定理 3.18 (2) より $g$ は全単射である。よって $\mathbb{R}$ はどの開区間とも対等である。

5.2 有限集合

有限集合の「元の個数」が矛盾なく定まることは、当たり前に見えて証明を要する。

定義 5.4（有限集合）$n \in \mathbb{N}$ に対し $[n] := \lbrace 1, 2, \dots, n \rbrace$、また $[0] := \emptyset$ とおく。ある整数 $n \geq 0$ について $X \sim [n]$ となるとき、$X$ は有限集合 (finite set) であるといい、$n$ を $X$ の元の個数といって $\lvert X \rvert = n$ と書く。有限集合でない集合を無限集合 (infinite set) という。

定理 5.5（鳩の巣原理, pigeonhole principle）整数 $m, n \geq 0$ について、単射 $[m] \to [n]$ が存在するならば $m \leq n$ である。

証明. $n$ についての帰納法で示す。$n = 0$ のとき、写像 $[m] \to \emptyset$ が存在するのは $[m] = \emptyset$、すなわち $m = 0$ のときだけである（例 3.4）。

$n$ で正しいと仮定し、$f\colon [m] \to [n + 1]$ を単射とする。$m = 0$ なら明らかなので $m \geq 1$ とする。単射 $g\colon [m - 1] \to [n]$ を次のように作る。

• $n + 1$ が $f([m - 1])$ に属さないとき：$g := f\vert_{[m-1]}$ とすれば、値は $[n]$ に入り、単射である。
• $f(k) = n + 1$ となる $k \leq m - 1$ があるとき：$g(k) := f(m)$、$i \neq k$ では $g(i) := f(i)$ とおく。$f$ は単射で $m \neq k$ なので $f(m) \neq f(k) = n + 1$、同様に $i \neq k$ なら $f(i) \neq n + 1$ であり、$g$ の値は $[n]$ に入る。$g$ の値は $[m]$ の相異なる点（$k$ 以外の $i \leq m - 1$ と、$m$）での $f$ の値なので、互いに異なる。よって $g$ は単射である。

帰納法の仮定より $m - 1 \leq n$、すなわち $m \leq n + 1$。$\square$

$n$ 個の巣に $n + 1$ 羽の鳩を入れれば、どこかの巣に 2 羽以上入る──この素朴な原理が、定理 5.5 の対偶である。

系 5.6

1. $[m] \sim [n]$ ならば $m = n$。したがって有限集合の元の個数は一意に定まる。
2. $\mathbb{N}$ から単射が存在する集合は有限集合でない。特に $\mathbb{N}$ は無限集合である。
3. 有限集合の部分集合は有限集合である。

証明. (1) 全単射とその逆写像は単射なので、定理 5.5 より $m \leq n$ かつ $n \leq m$。$X \sim [m]$ かつ $X \sim [n]$ なら定理 5.2 より $[m] \sim [n]$ となるので、個数は一意である。

(2) 単射 $\mathbb{N} \to X$ と全単射 $X \to [n]$ があれば、合成を $[n + 1] \subset \mathbb{N}$ に制限して単射 $[n + 1] \to [n]$ が得られ、定理 5.5 に反する。

(3) 全単射で移せば、$[n]$ の部分集合が有限であることを示せばよい。$n$ についての帰納法による。$n = 0$ なら部分集合は $\emptyset$ だけである。$A \subset [n + 1]$ とする。$n + 1 \notin A$ なら $A \subset [n]$ なので仮定より有限。$n + 1 \in A$ なら $A' := A \setminus \lbrace n + 1 \rbrace \subset [n]$ は有限で、全単射 $\varphi\colon [k] \to A'$ を $\varphi(k + 1) := n + 1$ で拡張すれば $[k + 1] \sim A$ となる。$\square$

5.3 可算集合

定義 5.7（可算集合）$\mathbb{N}$ と対等な集合を可算集合 (countable set) という。有限集合または可算集合であるものを高々可算 (at most countable) といい、高々可算でない集合を非可算 (uncountable) であるという。$\mathbb{N}$ の濃度を $\aleph_0$（アレフ・ゼロ）と書く。

$X$ が可算であることは、$X$ の元を重複なく $x_1, x_2, x_3, \dots$ と一列に並べられること（全単射 $n \mapsto x_n$ があること）にほかならない。

注意 5.8 「可算」を本教材の「高々可算」の意味で使う本も多い。可算無限 (countably infinite) という言い方もある。文献を読むときは定義を確認すること。

例 5.9 $\mathbb{Z}$ は可算である。$f\colon \mathbb{N} \to \mathbb{Z}$ を、$n$ が偶数なら $f(n) = n/2$、奇数なら $f(n) = -(n - 1)/2$ と定めると、$f(1), f(2), f(3), \dots = 0, 1, -1, 2, -2, \dots$ である。$g\colon \mathbb{Z} \to \mathbb{N}$ を $k > 0$ なら $g(k) = 2k$、$k \leq 0$ なら $g(k) = 1 - 2k$ と定めると、$g \circ f = \mathrm{id}_{\mathbb{N}}$、$f \circ g = \mathrm{id}_{\mathbb{Z}}$ が場合分けで確かめられるので、$f$ は全単射である。

定理 5.10 $\mathbb{N}$ の無限部分集合は可算である。

証明. $A \subset \mathbb{N}$ を無限集合とする。$A$ は上に有界でない。実際、ある $x$ で $A \subset [x]$ なら、系 5.6 (3) より $A$ は有限になってしまう。よって各 $x \in \mathbb{N}$ に対し $\lbrace a \in A \mid a > x \rbrace$ は空でなく、その最小元を $\varphi(x)$ とおける（$\mathbb{N}$ の整列性）。$a_1 := \min A$、$a_{k+1} := \varphi(a_k)$ で数列 $(a_k)$ を定める（帰納的定義。第7章 7.2 節）。

作り方から $a_1 < a_2 < a_3 < \cdots$ なので、$k \mapsto a_k$ は単射 $\mathbb{N} \to A$ である。帰納法で $a_k \geq k$ もわかる。全射を示す。$a \in A$ とすると、$a_a \geq a$ なので $K := \lbrace k \in \mathbb{N} \mid a_k \geq a \rbrace$ は空でなく、最小元 $k$ をもつ。$k = 1$ なら $a_1 = \min A \leq a \leq a_1$ より $a = a_1$。$k \geq 2$ なら $a_{k-1} < a$ なので、$a$ は $\lbrace b \in A \mid b > a_{k-1} \rbrace$ に属し、その最小元 $a_k$ について $a_k \leq a$。$a_k \geq a$ と合わせて $a = a_k$。$\square$

系 5.11 次が成り立つ。

1. 単射 $X \to \mathbb{N}$ が存在すれば、$X$ は高々可算である。
2. 高々可算な集合の部分集合は高々可算である。
3. $X \neq \emptyset$ とする。全射 $\mathbb{N} \to X$ が存在すれば、$X$ は高々可算である。

証明. (1) 単射 $f\colon X \to \mathbb{N}$ について $X \sim f(X) \subset \mathbb{N}$ であり、$f(X)$ は有限か、定理 5.10 により可算である。(2) $Y$ が高々可算なら単射 $Y \to \mathbb{N}$ があるので（有限なら $Y \sim [n] \subset \mathbb{N}$）、部分集合 $X \subset Y$ への制限に (1) を適用する。(3) 全射 $g\colon \mathbb{N} \to X$ に対し、$h(x) := \min g^{-1}(\lbrace x \rbrace)$ とおくと $g \circ h = \mathrm{id}_X$ なので $h$ は単射であり（定理 3.16）、(1) が使える。ここでは最小元をとるという規則で選んでいるので、選択公理は使っていない。$\square$

定理 5.12 $\mathbb{N} \times \mathbb{N}$ は可算である。

証明. $\varphi\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$、$\varphi(m, n) := 2^{m-1}(2n - 1)$ が全単射であることを示す。

全射：$N \in \mathbb{N}$ とする。$2^k \mid N$ を満たす整数 $k \geq 0$ は $2^k \leq N$ を満たすので有限個しかなく（$k = 0$ は含まれる）、その最大のものを $k$ とする。$N = 2^k q$ と書くと、$q$ が偶数なら $2^{k+1} \mid N$ となり最大性に反するので、$q$ は奇数である。よって $N = \varphi(k + 1, (q + 1)/2)$。

単射：$\varphi(m, n) = \varphi(m', n')$ とし、$m \leq m'$ としてよい。両辺を $2^{m-1}$ で割ると $2n - 1 = 2^{m' - m}(2n' - 1)$。左辺は奇数なので $m' - m = 0$ であり、すると $n = n'$。$\square$

系 5.13

1. $X, Y$ が可算ならば $X \times Y$ は可算である。特に各 $k \in \mathbb{N}$ について $\mathbb{N}^k$ は可算である。
2. $\mathbb{Q}$ は可算である。

証明. (1) 全単射 $X \to \mathbb{N}$、$Y \to \mathbb{N}$ から全単射 $X \times Y \to \mathbb{N} \times \mathbb{N}$ が得られ、定理 5.12 と合わせればよい。$\mathbb{N}^{k+1} \sim \mathbb{N}^k \times \mathbb{N}$ なので後半は帰納法で従う。

(2) 各 $r \in \mathbb{Q}$ は、$p \in \mathbb{Z}$、$q \in \mathbb{N}$ で $p$ と $q$ が $1$ 以外の正の公約数をもたないような形 $r = p/q$ にただ一通りに書ける。$r \mapsto (p, q)$ は単射 $\mathbb{Q} \to \mathbb{Z} \times \mathbb{N}$ であり、$\mathbb{Z} \times \mathbb{N}$ は (1) と例 5.9 により可算なので、系 5.11 (1) より $\mathbb{Q}$ は高々可算である。$\mathbb{N} \subset \mathbb{Q}$ なので系 5.6 (2) より $\mathbb{Q}$ は有限でない。よって可算である。$\square$

$\mathbb{Q}$ は数直線上で「隙間なく」詰まっているように見えるのに、$\mathbb{N}$ と同じ大きさしかない。濃度の直観は、位置関係や密度の直観とはまったく別物である。

定理 5.14（可算集合の可算和）$(A_n)_{n \in \mathbb{N}}$ を高々可算な集合の族とする。選択公理を仮定すると、$\bigcup_{n \in \mathbb{N}} A_n$ は高々可算である。

証明. すべての $A_n$ が空なら和集合は空である。そうでないとき $N' := \lbrace n \in \mathbb{N} \mid A_n \neq \emptyset \rbrace \neq \emptyset$ とし、$n_0 \in N'$ を一つ固定する。各 $n \in N'$ について、全射 $\mathbb{N} \to A_n$ 全体の集合 $S_n$ は空でない（有限なら $[k]$ からの全単射を適当に延長し、可算なら全単射をとればよい）。選択公理により、各 $n \in N'$ で $g_n \in S_n$ となるような族 $(g_n)_{n \in N'}$ がとれる。$G\colon \mathbb{N} \times \mathbb{N} \to \bigcup_n A_n$ を、$n \in N'$ なら $G(n, k) := g_n(k)$、$n \notin N'$ なら $G(n, k) := g_{n_0}(k)$ で定めると、$G$ は全射である（$x \in A_n$ なら $n \in N'$ で、$x = g_n(k)$ となる $k$ がある）。$G$ と全単射 $\mathbb{N} \to \mathbb{N} \times \mathbb{N}$ を合成し、系 5.11 (3) を使えばよい。$\square$

注意 5.15（選択公理の使いどころ）各 $S_n$ は空でないが、その中から一つを選ぶ規則は一般にない。無限個の $n$ について同時に選ぶところで選択公理が必要になる。実際、選択公理を仮定しない ZF では、この定理は証明できないことが知られている（$\mathbb{R}$ が可算集合の可算和になるような ZF のモデルが存在する。フェファーマンとレヴィによる）。一方、各 $A_n$ の番号づけが具体的に与えられていれば、選択公理はいらない。たとえば $\mathbb{Q}$ の可算性（系 5.13）は選択公理を使わずに示した。

例 5.16（代数的数）整数係数の $0$ でない多項式の根になる複素数を代数的数 (algebraic number) という。代数的数全体 $\mathbb{A}$ は可算である。実際、次数 $d$ 以下の整数係数多項式全体は係数の組を通じて $\mathbb{Z}^{d+1}$ と対等で可算であり、それらの $d \in \mathbb{N}$ にわたる和集合も可算である。$0$ でない多項式の根は有限個しかないので（代数学）、$\mathbb{A}$ は可算個の有限集合の和として高々可算であり、$\mathbb{Z} \subset \mathbb{A}$ より無限集合である。（ここでは各 $\mathbb{Z}^{d+1}$ の番号づけや根の並べ方を具体的に与えられるので、選択公理を避けることもできる。）

5.4 実数の非可算性

$\mathbb{N}$、$\mathbb{Z}$、$\mathbb{Q}$、代数的数はみな可算だった。では $\mathbb{R}$ も可算だろうか。答えは否であり、その証明が有名な対角線論法 (diagonal argument) である。準備として、小数展開についての補題を示す。以下、級数 $\sum_{k=1}^{\infty} a_k 10^{-k}$（$a_k \in \lbrace 0, 1, \dots, 9 \rbrace$）が収束すること、および $[0, 1)$ の各実数 $x$ が $x = \sum_{k=1}^{\infty} a_k 10^{-k}$ の形の小数展開をもつこと（たとえば $a_k := \lfloor 10^k x \rfloor - 10 \lfloor 10^{k-1} x \rfloor$ とすればよい）は、微分積分学で学ぶ事実として認める。

補題 5.17 $(a_k), (b_k)$ を $\lbrace 0, 1, \dots, 9 \rbrace$ に値をとる数列とし、すべての $k$ で $\lvert a_k - b_k \rvert \leq 8$ とする。$(a_k) \neq (b_k)$ ならば $\sum_{k=1}^{\infty} a_k 10^{-k} \neq \sum_{k=1}^{\infty} b_k 10^{-k}$ である。

証明. $a_j \neq b_j$ となる最小の $j$ をとる。二つの和の差は

であり、第 1 項の絶対値は $10^{-j}$ 以上、第 2 項の絶対値は $8 \sum_{k > j} 10^{-k} = \frac{8}{9} 10^{-j}$ 以下である。よって差は $0$ でない。$\square$

条件 $\lvert a_k - b_k \rvert \leq 8$ は、$0.0999\cdots = 0.1000\cdots$ のような「二通りの展開」を排除するためのものである。

定理 5.18（カントール）開区間 $(0, 1)$ は非可算である。したがって $\mathbb{R}$ は非可算である。

証明. $(0, 1)$ は無限集合である（$n \mapsto 1/(n + 1)$ は単射 $\mathbb{N} \to (0, 1)$）。可算であると仮定して矛盾を導けばよいので、全射 $f\colon \mathbb{N} \to (0, 1)$ があると仮定する。各 $n$ について $f(n)$ の小数展開を上の公式で一つ定め、$f(n) = \sum_k a_{nk} 10^{-k}$ と書く。そこで

とおく。$4/9 \leq b \leq 5/9$ なので $b \in (0, 1)$ であり、$f$ は全射だから $b = f(m)$ となる $m$ がある。ところが $b_m \neq a_{mm}$ なので数列 $(b_k)$ と $(a_{mk})_k$ は異なり、$b_k \in \lbrace 4, 5 \rbrace$ より $\lvert a_{mk} - b_k \rvert \leq 5$ がすべての $k$ で成り立つ。補題 5.17 より $b \neq f(m)$ となり、矛盾する。最後に、$\mathbb{R}$ が高々可算なら部分集合 $(0, 1)$ も高々可算になるので（系 5.11 (2)）、$\mathbb{R}$ は非可算である。$\square$

$b$ は、表の対角線上の数字 $a_{11}, a_{22}, a_{33}, \dots$ をすべて変えて作った数であり、どの $f(n)$ とも第 $n$ 桁で食い違う。これが「対角線論法」の名の由来である。

系 5.19 無理数全体 $\mathbb{R} \setminus \mathbb{Q}$ は非可算である。また代数的数でない実数（超越数, transcendental number）が存在し、その全体は非可算である。

証明. $\mathbb{R} \setminus \mathbb{A}$ が高々可算なら、$\mathbb{R} = \mathbb{A} \cup (\mathbb{R} \setminus \mathbb{A})$ は高々可算集合二つの和として高々可算になり（定理 5.14。二つの場合は番号を交互に並べればよく、選択公理はいらない）、定理 5.18 に反する。$\mathbb{Q} \subset \mathbb{A}$ なので $\mathbb{R} \setminus \mathbb{Q} \supset \mathbb{R} \setminus \mathbb{A}$ も非可算である。$\square$

この証明は、超越数を一つも具体的に示さずにその存在を示している（非構成的証明、第1章 例 1.40）。

5.5 カントールの定理

対角線論法は、はるかに一般的な形で述べられる。

定理 5.20（カントールの定理）任意の集合 $X$ について、全射 $X \to \mathcal{P}(X)$ は存在しない。したがって $\lvert X \rvert < \lvert \mathcal{P}(X) \rvert$ である。

証明. $f\colon X \to \mathcal{P}(X)$ を任意の写像とし、$D := \lbrace x \in X \mid x \notin f(x) \rbrace \in \mathcal{P}(X)$ とおく。$D = f(a)$ となる $a \in X$ があったとすると、$D$ の定義より

となり矛盾する。よって $D \notin f(X)$ であり、$f$ は全射でない。一方 $x \mapsto \lbrace x \rbrace$ は単射 $X \to \mathcal{P}(X)$ なので $\lvert X \rvert \leq \lvert \mathcal{P}(X) \rvert$ であり、全単射は存在しないので $\lvert X \rvert \neq \lvert \mathcal{P}(X) \rvert$。$\square$

注意 5.21 証明の $D$ は、各 $x$ について「$x$ が $f(x)$ に属するか」を反転させて作っており、定理 5.18 の $b$ と同じ発想である。また「$a \in D \iff a \notin D$」という矛盾の形は、ラッセルのパラドックス（定理 2.25）と同じである（問題 5.10）。カントールの定理から

となり、最大の濃度は存在しない。無限の大きさには限りなく多くの段階がある。

5.6 ベルンシュタインの定理

二つの集合が対等であることを示すのに、全単射を具体的に作るのは難しいことが多い。次の定理により、単射を両方向に作れば十分になる。

定理 5.22（ベルンシュタインの定理, Cantor–Bernstein theorem）単射 $f\colon X \to Y$ と単射 $g\colon Y \to X$ が存在すれば、$X \sim Y$ である。すなわち $\lvert X \rvert \leq \lvert Y \rvert$ かつ $\lvert Y \rvert \leq \lvert X \rvert$ ならば $\lvert X \rvert = \lvert Y \rvert$ である。

証明. $X$ の部分集合の列を $C_0 := X \setminus g(Y)$、$C_{n+1} := g(f(C_n))$（$n \geq 0$）で定め、$C := \bigcup_{n \geq 0} C_n$ とおく。$h\colon X \to Y$ を

で定める。ここで $x \notin C$ なら $x \notin C_0$、すなわち $x \in g(Y)$ であり、$g$ は単射なので $g(y) = x$ となる $y$ がただ一つ定まる。これを $g^{-1}(x)$ と書いた。$h$ が全単射であることを示す。

単射：$h(x) = h(x')$ とする。$x, x'$ がともに $C$ に属するなら $f(x) = f(x')$ より $x = x'$。ともに $C$ に属さないなら $g^{-1}(x) = g^{-1}(x')$ で、両辺に $g$ を施して $x = x'$。$x \in C$、$x' \notin C$ とすると $f(x) = g^{-1}(x')$ なので $x' = g(f(x))$ である。$x \in C_n$ となる $n$ をとると $x' \in g(f(C_n)) = C_{n+1} \subset C$ となり、$x' \notin C$ に矛盾する。

全射：$y \in Y$ とする。$g(y) \notin C$ なら $h(g(y)) = g^{-1}(g(y)) = y$。$g(y) \in C$ なら、$g(y) \in C_n$ となる $n$ がある。$g(y) \in g(Y)$ なので $g(y) \notin C_0$、よって $n \geq 1$ であり、$g(y) \in C_n = g(f(C_{n-1}))$ より $g(y) = g(f(x))$ となる $x \in C_{n-1}$ がある。$g$ は単射なので $y = f(x)$ で、$x \in C$ より $h(x) = f(x) = y$。$\square$

直観的には、$C$ は「$g$ の像に入らない点から出発して $g \circ f$ で追いかけて到達できる点」の全体であり、そこでは $f$ を、それ以外では $g$ の逆を使って対応させている。この証明は選択公理を使っていない。

例 5.23

1. $[0, 1] \sim (0, 1)$：包含写像 $(0, 1) \to [0, 1]$ と、$x \mapsto (x + 1)/3$ による単射 $[0, 1] \to (0, 1)$ があるので、定理 5.22 より対等である（全単射を具体的に作ることもできる。問題 5.3）。例 5.3 と合わせて、$2$ 点以上を含むどんな区間も $\mathbb{R}$ と対等である。
2. $\mathbb{N} \times \mathbb{N} \sim \mathbb{N}$ の別証明：$n \mapsto (n, 1)$ と、$(m, n) \mapsto 2^m 3^n$（素因数分解の一意性により単射）を使えばよい。

注意 5.24 任意の二つの集合 $X, Y$ について $\lvert X \rvert \leq \lvert Y \rvert$ または $\lvert Y \rvert \leq \lvert X \rvert$ が成り立つだろうか（濃度の比較可能性）。これは選択公理のもとで正しい（第6章 問題 6.9）。逆に濃度の比較可能性から選択公理を導くこともでき（ハルトークスの定理を用いる。本教材では扱わない）、両者は同値であることが知られている。

5.7 連続体の濃度

定理 5.25 $\lvert \mathbb{R} \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert = \lvert \lbrace 0, 1 \rbrace^{\mathbb{N}} \rvert$ である。

証明. $\mathcal{P}(\mathbb{N}) \sim \lbrace 0, 1 \rbrace^{\mathbb{N}}$ は定理 3.32 である。

$\lvert \mathbb{R} \rvert \leq \lvert \mathcal{P}(\mathbb{N}) \rvert$：$c\colon \mathbb{R} \to \mathcal{P}(\mathbb{Q})$ を $c(x) := \lbrace q \in \mathbb{Q} \mid q < x \rbrace$ で定める。$x < y$ なら、有理数の稠密性（アルキメデスの性質から従う。微分積分学 第1章）により $x < q < y$ となる $q \in \mathbb{Q}$ があり、$q \in c(y) \setminus c(x)$ なので $c(x) \neq c(y)$。よって $c$ は単射である。また全単射 $\psi\colon \mathbb{Q} \to \mathbb{N}$（系 5.13）により $A \mapsto \psi(A)$ は全単射 $\mathcal{P}(\mathbb{Q}) \to \mathcal{P}(\mathbb{N})$ である（逆写像は $B \mapsto \psi^{-1}(B)$）。合成して単射 $\mathbb{R} \to \mathcal{P}(\mathbb{N})$ を得る。

$\lvert \lbrace 0, 1 \rbrace^{\mathbb{N}} \rvert \leq \lvert \mathbb{R} \rvert$：$d\colon \lbrace 0, 1 \rbrace^{\mathbb{N}} \to \mathbb{R}$ を $d((a_k)_k) := \sum_{k=1}^{\infty} a_k 10^{-k}$ で定めると、$\lvert a_k - b_k \rvert \leq 1$ なので補題 5.17 より単射である。

以上とベルンシュタインの定理から結論を得る。$\square$

$\mathbb{R}$ の濃度を連続体の濃度 (cardinality of the continuum) といい、$\mathfrak{c}$ と書く。定理 5.25 とカントールの定理から、$\aleph_0 < \mathfrak{c}$ が改めて得られる。

定理 5.26 $\lvert \mathbb{R}^2 \rvert = \lvert \mathbb{R} \rvert$ である。したがって各 $n \in \mathbb{N}$ について $\lvert \mathbb{R}^n \rvert = \lvert \mathbb{R} \rvert$ である。

証明. $\lbrace 0, 1 \rbrace^{\mathbb{N}} \times \lbrace 0, 1 \rbrace^{\mathbb{N}} \to \lbrace 0, 1 \rbrace^{\mathbb{N}}$ を、$((a_k), (b_k)) \mapsto (a_1, b_1, a_2, b_2, \dots)$（すなわち $c_{2k-1} = a_k$、$c_{2k} = b_k$）で定めると、奇数番目と偶数番目に分ける写像が逆写像になるので全単射である。定理 5.25 により全単射 $\theta\colon \mathbb{R} \to \lbrace 0, 1 \rbrace^{\mathbb{N}}$ が存在し、そこから全単射 $\mathbb{R}^2 \to \lbrace 0, 1 \rbrace^{\mathbb{N}} \times \lbrace 0, 1 \rbrace^{\mathbb{N}}$、$(x, y) \mapsto (\theta(x), \theta(y))$ が得られ、合成すれば $\mathbb{R}^2 \sim \lbrace 0, 1 \rbrace^{\mathbb{N}} \sim \mathbb{R}$。後半は $\mathbb{R}^{n+1} \sim \mathbb{R}^n \times \mathbb{R}$ から帰納法で従う。$\square$

平面と直線が「同じ個数の点」をもつというこの結果には、発見者のカントール自身も驚いたと伝えられる。ただしこの全単射は極めて不連続である。実際、連続な全単射 $\mathbb{R}^2 \to \mathbb{R}$ は存在しない（$\mathbb{R}^2$ から 1 点を除いても連結だが、$\mathbb{R}$ から 1 点を除くと連結でなくなるため。位相空間論 第6章）。「次元」は集合の濃度ではとらえられず、位相の概念なのである。

5.8 濃度の演算

有限集合の個数の和・積・べきを無限集合に拡張する。

定義 5.27（濃度の演算）集合 $A, B$ に対し次のように定める。

• 和：$\lvert A \rvert + \lvert B \rvert := \lvert (A \times \lbrace 0 \rbrace) \cup (B \times \lbrace 1 \rbrace) \rvert$（$A, B$ を交わらないように取り替えた和集合の濃度）
• 積：$\lvert A \rvert \cdot \lvert B \rvert := \lvert A \times B \rvert$
• べき：$\lvert A \rvert^{\lvert B \rvert} := \lvert A^B \rvert$

これらは $A, B$ の濃度だけで決まる（$A \sim A'$、$B \sim B'$ なら右辺の集合も対等になる。問題 5.6）。有限集合では通常の和・積・べきに一致する（例 3.31）。$\lvert \lbrace 0, 1 \rbrace \rvert = 2$ と書けば、定理 3.32 より $\lvert \mathcal{P}(X) \rvert = 2^{\lvert X \rvert}$ であり、定理 5.25 は $\mathfrak{c} = 2^{\aleph_0}$ と書ける。

定理 5.28（指数法則）集合 $A, B, C$ について、$\kappa = \lvert A \rvert$、$\lambda = \lvert B \rvert$、$\mu = \lvert C \rvert$ とおくと

$$\kappa^{\lambda + \mu} = \kappa^{\lambda} \kappa^{\mu}, \qquad (\kappa^{\lambda})^{\mu} = \kappa^{\lambda\mu}, \qquad (\kappa\lambda)^{\mu} = \kappa^{\mu} \lambda^{\mu}$$

が成り立つ。

証明. 第 1 式：$B \cap C = \emptyset$ としてよい。$A^{B \cup C} \to A^B \times A^C$、$f \mapsto (f\vert_B, f\vert_C)$ は全単射である（逆写像は、$g\colon B \to A$ と $h\colon C \to A$ をつないだ写像を対応させるもの）。第 2 式：$(A^B)^C \sim A^{C \times B}$ は問題 3.9 であり、$C \times B \sim B \times C$ である。第 3 式：$(A \times B)^C \to A^C \times B^C$、$f \mapsto (p_1 \circ f, p_2 \circ f)$ は全単射である（逆写像は $(g, h) \mapsto (c \mapsto (g(c), h(c)))$）。$\square$

また $A \subset A'$ なら $A^B \subset A'^B$、$B \subset B'$ かつ $A \neq \emptyset$ なら $A^B \to A^{B'}$ への単射がある（$B' \setminus B$ 上で一定値をとるように延長する）ので、べきは $\leq$ について単調である。

例 5.29

1. $\aleph_0 + \aleph_0 = \aleph_0$（偶数と奇数に分ける）、$\aleph_0 \cdot \aleph_0 = \aleph_0$（定理 5.12）。
2. $\mathfrak{c} \cdot \mathfrak{c} = \mathfrak{c}$（定理 5.26）。
3. $\mathfrak{c}^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0} = \mathfrak{c}$。つまり実数列全体 $\mathbb{R}^{\mathbb{N}}$ も $\mathbb{R}$ と対等である。
4. $\aleph_0^{\aleph_0} = \mathfrak{c}$：単調性より $2^{\aleph_0} \leq \aleph_0^{\aleph_0} \leq \mathfrak{c}^{\aleph_0} = \mathfrak{c}$ であり、ベルンシュタインの定理から等号が従う。
5. $\mathbb{R}$ から $\mathbb{R}$ への写像全体：$\mathfrak{c}^{\mathfrak{c}} = (2^{\aleph_0})^{\mathfrak{c}} = 2^{\aleph_0 \mathfrak{c}} = 2^{\mathfrak{c}}$（$\mathfrak{c} \leq \aleph_0 \mathfrak{c} \leq \mathfrak{c}\mathfrak{c} = \mathfrak{c}$ による）。カントールの定理より $2^{\mathfrak{c}} > \mathfrak{c}$ である。一方、連続関数全体は濃度 $\mathfrak{c}$ しかない（問題 5.9）。

選択公理を仮定すると、任意の無限集合 $X$ について $\lvert X \times X \rvert = \lvert X \rvert$ が成り立つことが知られている（証明は省略する）。

5.9 連続体仮説

$\aleph_0 < \mathfrak{c}$ であった。では、その間の濃度をもつ集合、すなわち $\aleph_0 < \lvert S \rvert < \mathfrak{c}$ となる集合 $S$ は存在するだろうか。カントールは存在しないと予想した。これを連続体仮説 (continuum hypothesis, CH) という。$S$ は $\mathbb{R}$ の部分集合としてよいので、「$\mathbb{R}$ の無限部分集合は、可算であるか $\mathbb{R}$ と対等であるかのどちらかである」と言いかえられる。

連続体仮説は 1900 年にヒルベルトが挙げた 23 の問題の第 1 問であった。その後、ゲーデル (K. Gödel, 1938 年頃) は ZFC から連続体仮説の否定を証明できないことを、コーエン (P. Cohen, 1963 年) は ZFC から連続体仮説を証明できないことを示した（いずれも ZFC が無矛盾であるという仮定のもとで）。つまり連続体仮説は ZFC から独立であり、標準的な公理だけでは真偽が決まらない。コーエンが開発した強制法 (forcing) は、その後の集合論の基本的な技法となった。

一方、具体的な集合については答えが出ることもある。たとえば $\mathbb{R}$ の閉集合は、高々可算であるか $\mathbb{R}$ と対等であるかのどちらかであることが ZFC で証明できる（カントール–ベンディクソンの定理）。

まとめ

• 集合の大きさは全単射の有無で比べる（対等）。無限集合は自分の真部分集合と対等になりうる。
• 鳩の巣原理により有限集合の元の個数は一意に定まり、$\mathbb{N}$ は無限集合である。
• $\mathbb{Z}$、$\mathbb{N} \times \mathbb{N}$、$\mathbb{Q}$、代数的数全体は可算である。可算集合の可算和が可算であることの証明には選択公理を使う。
• 対角線論法により $\mathbb{R}$ は非可算である。カントールの定理 $\lvert X \rvert < \lvert \mathcal{P}(X) \rvert$ により、最大の濃度は存在しない。
• ベルンシュタインの定理：単射が両方向にあれば対等である（選択公理は不要）。
• $\lvert \mathbb{R} \rvert = \lvert \mathcal{P}(\mathbb{N}) \rvert = \lvert \lbrace 0,1 \rbrace^{\mathbb{N}} \rvert = \lvert \mathbb{R}^2 \rvert = \mathfrak{c} = 2^{\aleph_0}$。
• 濃度の和・積・べきは直和・直積・写像の集合で定義され、指数法則が成り立つ。
• 連続体仮説（$\aleph_0$ と $\mathfrak{c}$ の間の濃度はない）は ZFC から独立である。

演習問題