可算集合

set_intro では、有限集合の濃度（のうど、cardinality）$|A|$ がその要素数を数えるものだと学んだ。でも $\mathbb{N}$、$\mathbb{Z}$、$\mathbb{Q}$ のように無限に続く集合の「大きさ」はどういう意味だろう？驚くことに、無限集合がすべて同じ大きさというわけではない。可算性（かさんせい、countability）は無限集合を測り比べるための、最初の――そして最も具体的な――道具だ。

全単射による大きさの比較

2つの集合を比較するには、要素を数えることなく対応させる方法が必要だ。そのアイデアを捉えるのが、2種類の特別な写像だ。（写像の完全な説明は Maps にある。ここでは始めるのに十分な分だけ紹介する。）

写像（しゃぞう、map）$f \colon A \to B$ は各要素 $a \in A$ にちょうど1つの要素 $f(a) \in B$ を対応させる。写像が単射（たんしゃ、injective または one-to-one、$f \colon A \hookrightarrow B$ と書く）であるとは、異なる入力が常に異なる出力を生み出すことを言う：

$$f(a_1) = f(a_2) \;\Rightarrow\; a_1 = a_2.$$

単射は埋め込みのようなものだ。$A$ の各要素が $B$ の中に自分専用のスロットを持ち、2つの要素が同じスロットを共有することはない。

写像が全単射（ぜんたんしゃ、bijective）であるとは、単射であり、かつ $B$ のすべての要素がちょうど1つの $A$ の要素の像であることを言う。全単射（bijection）は $A$ と $B$ の完全な一対一の対応で、どちら側にも余りがない。

全単射は有限集合にも無限集合にも使える、等しい濃度の定義を与えてくれる：

$$|A| = |B| \;\coloneqq\; \exists \text{ 全単射 } f \colon A \to B. \tag{1}$$

有限集合に対しては $(1)$ は通常の数え方と一致する。驚きなのは、$(1)$ が無限集合に対して直感に反する結果を生み出せることだ――この記事の残りで詳しく見ていこう。

可算であることの意味

ペアノ公理より、自然数 $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$ は後者関数から構成されることを思い出そう。$\mathbb{N}$ を無限集合の基準として使う。

集合 $A$ が有限で濃度 $n$（ある $n \in \mathbb{N}$）を持つとは、$A \to \{0, 1, \ldots, n-1\}$ の全単射が存在することを言う。これは set_intro の濃度の定義と一致する。

集合 $A$ が可算無限（かさんむげん、countably infinite）であるとは、全単射

$$f \colon \mathbb{N} \to A \tag{2}$$

が存在することを言う。全単射 $(2)$ は $A$ のすべての要素の、繰り返しのない完全な列挙そのものだ：

$$a_0 \;\coloneqq\; f(0), \quad a_1 \;\coloneqq\; f(1), \quad a_2 \;\coloneqq\; f(2), \quad \ldots$$

各要素はちょうど1回ずつ現れる。つまり可算無限とは文字通り、すべての要素を $\mathbb{N}$ でインデックス付けされた無限列 $a_0, a_1, a_2, \ldots$ に並べられるということだ。

集合が有限または可算無限ならば可算（かさん、countable）という。可算でない集合は非可算（ひかさん、uncountable）だ――最初の具体的な例は 非可算集合 で登場する。

よく使う同値な定式化がある：

命題. 空でない集合 $A$ が可算であることと、単射 $A \hookrightarrow \mathbb{N}$ が存在することは同値。

理由. $A$ が可算無限なら、全単射 $\mathbb{N} \to A$ の逆写像はそれ自体全単射で、特に単射 $A \hookrightarrow \mathbb{N}$ だ。$A$ が濃度 $n$ の有限集合なら、全単射 $A \to \{0, \ldots, n-1\}$ と包含写像 $\{0, \ldots, n-1\} \hookrightarrow \mathbb{N}$ を合成する。逆に、単射 $g \colon A \hookrightarrow \mathbb{N}$ が与えられたとき、$g(A)$ の要素を昇順に並べると $\mathbb{N}$（または有限の初期切片）から $A$ への全単射が得られる。

可算集合の例

$\mathbb{N}$ 自身

恒等写像 $\mathrm{id} \colon \mathbb{N} \to \mathbb{N}$、$n \mapsto n$ は自明に全単射だ。よって $\mathbb{N}$ は定義より可算無限――基準となるケースだ。

整数 $\mathbb{Z}$

一見すると $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ は両方向に広がるため $\mathbb{N}$ の「2倍の大きさ」に見える。次の交互列挙写像を定義しよう：

$$f \colon \mathbb{N} \to \mathbb{Z}, \qquad f(n) \;\coloneqq\; \begin{cases} \phantom{-}n/2 & \text{$n$ が偶数のとき,} \\[4pt] -(n+1)/2 & \text{$n$ が奇数のとき.} \end{cases} \tag{3}$$

これは非負整数と負整数を交互にたどる：

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$\cdots$
$f(n)$	$0$	$-1$	$1$	$-2$	$2$	$-3$	$3$	$-4$	$\cdots$

すべての整数がちょうど1回現れるので $f$ は全単射であり $|\mathbb{Z}| = |\mathbb{N}|$。整数集合は両方向に数直線を占めるにもかかわらず、自然数より大きくない。

積集合 $\mathbb{N} \times \mathbb{N}$

$\mathbb{N} \times \mathbb{N} = \{(m, n) \mid m, n \in \mathbb{N}\}$ は無限の二次元格子だ。対角線的走査（たいかくせんてきそうさ）は $m + n = k$ となる反対角線に沿ってペアをグループ分けし、すべてのセルを訪れる：

$$(0,0) \;\to\; (1,0) \;\to\; (0,1) \;\to\; (2,0) \;\to\; (1,1) \;\to\; (0,2) \;\to\; (3,0) \;\to\; \cdots$$

カントールの対関数（Cantor pairing function）はこの走査を閉じた式で表す：

$$\pi \colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}, \qquad \pi(m, n) \;\coloneqq\; \frac{(m+n)(m+n+1)}{2} + m. \tag{4}$$

三角数の項 $\frac{(m+n)(m+n+1)}{2}$ はそれより前の対角線上のペアの数を数え、$m$ を加えることで $(m, n)$ がその対角線上の何番目かを表す。$\pi$ が全単射であることが確認でき、$|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$ が得られる。無限に多くの無限行が1本の列に畳み込まれる。

有理数 $\mathbb{Q}$

すべての正の分数 $p/q$（$p, q \geq 1$）を格子に並べる。$p$ を一方の軸、$q$ をもう一方の軸に取る。上と同じ対角線的走査を適用するが、$\gcd(p, q) > 1$ となるエントリ $(p, q)$ はスキップして各有理数が既約分数としてちょうど1回現れるようにする。次に $0$ を先頭に加え、$\mathbb{Z}$ のときと同じ交互列挙で負の有理数を織り込む。すべての有理数がこの列挙に現れるので $\mathbb{Q}$ は可算無限だ――数直線上では $\mathbb{N}$ よりはるかに密に見えるにもかかわらず。

2つの重要な閉包性質

可算集合の部分集合は可算

定理. $A$ が可算で $B \subseteq A$ ならば、$B$ は可算だ。

直感. 包含写像 $\iota \colon B \hookrightarrow A$ は単射だ。これと $A \hookrightarrow \mathbb{N}$ の単射（$A$ が可算だから存在する）を合成すると単射 $B \hookrightarrow \mathbb{N}$ が得られ、上の命題より $B$ は可算だ。

この定理は、可算な「入れ物」を見つけたら、その中のすべての部分集合は自動的に可算だということを意味する。

可算個の可算集合の和集合は可算

定理. $A_0, A_1, A_2, \ldots$ が可算集合の可算族ならば、$\bigcup_{k=0}^{\infty} A_k$ も可算だ。

直感. 各 $A_k$ の要素を1行に並べる（有限行は必要に応じてパディングする）。すると $\mathbb{N} \times \mathbb{N}$ のような無限格子が得られる。対角線的走査を適用し、既出の要素はスキップして重複を避ける。$\bigcup_k A_k$ のすべての要素が訪問されるので和集合は可算だ。

顕著な応用として：整数係数多項式の根である代数的数（だいすうてきすう、algebraic numbers）は可算集合を成す。そのような多項式は可算個存在し（各多項式は整数係数の有限リストであり、カントールの対関数 $(4)$ を繰り返し適用すると整数の有限リストが可算であることが示せる）、各多項式の根は有限個しかない。よって代数的数は有限集合の可算和であり、可算だ。

まとめ

• 濃度の等号 $|A| = |B|$ は全単射 $A \to B$ の存在によって定義される。この定義は有限集合から無限集合へ自然に拡張される――式 $(1)$ を参照。
• 写像 $f \colon A \to B$ が単射（$A \hookrightarrow B$）であるとは異なる入力が異なる出力を持つことで、全単射とは単射かつ $B$ のすべての要素がちょうど1回ヒットされること。完全な理論は Maps にある。
• 集合が可算無限であるとは全単射 $\mathbb{N} \to A$ が存在すること――同値な言い方として、要素を省略も繰り返しもなく $a_0, a_1, a_2, \ldots$ と列挙できること。
• 集合が可算とは有限または可算無限であること。そうでない集合は非可算だ。
• 同値な判定基準：空でない集合 $A$ が可算であることと、単射 $A \hookrightarrow \mathbb{N}$ が存在することは同値。
• 標準的な可算集合：$\mathbb{N}$（自明）、$\mathbb{Z}$（交互列挙全単射 $(3)$）、$\mathbb{N} \times \mathbb{N}$（カントールの対関数 $(4)$）、$\mathbb{Q}$（スキップ付き対角線的走査）。
• 可算集合の部分集合は可算で、可算集合の可算和も可算だ――代数的数がその注目すべき帰結だ。
• すべての無限集合が可算というわけではない。$\mathbb{R}$ が $\mathbb{N}$ より真に大きい理由を知るには 非可算集合 へ進もう。