康托定理

你能想到的每個集合——無論多大、有限還是無限——都有一個嚴格大於自身的冪集。這就是康托定理（Cantor’s theorem），其證明是數學中最優美的之一：一個稱為對角集的自指構造，一次性擊敗每個候選的滿射。這個結果也打開了一扇數學家此前不知存在的門：存在無窮多個不同大小的無窮。

康托定理的內容

康托定理。 對任意集合 $A$，不存在從 $A$ 到 $\mathcal{P}(A)$ 的滿射。等價地，

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

回憶映射中，$|A| < |B|$ 意味著存在從 $A$ 到 $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）**的技術。你構造一個子集 $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$： 則由 $D$ 的定義 $(2)$，我們需要 $d \notin f(d)$。但 $f(d) = D$，所以 $d \notin D$。矛盾。
• 若 $d \notin D$： 則由 $D$ 的定義 $(2)$，我們需要 $d \in f(d)$。但 $f(d) = D$，所以 $d \in D$。矛盾。

兩種情形都導致矛盾。$f$ 是滿射的假設必然是假的。$\square$

對角集的運作原理

定義 $D = \{x \in A \mid x \notin f(x)\}$ 的構造，使得 $D$ 對每一個 $x \in A$ 的成員關係都與 $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$

粗體的對角線條目回答了「$a_i \in f(a_i)$？」對每個 $i$ 的問題。對角集 $D$ 透過翻轉每個對角線條目來構造：恰好當第 $i$ 個對角線條目回答「否」時，將 $a_i$ 包含在 $D$ 中。由此得到的行在列 $a_i$ 上與第 $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}|$，所以實數構成比自然數嚴格更大的無窮。