冪集

每個集合都帶有一個隱藏的伴侶：它所有子集所構成的集合。這個伴侶稱為冪集（power set），它永遠嚴格大於原來的集合——即使對無限集合也是如此。冪集出現在組合數學、邏輯、拓樸學和電腦科學中，因此早早理解它將在許多學科中帶來豐厚回報。

定義

設 $A$ 為一個集合。$A$ 的冪集，記作 $\mathcal{P}(A)$，是以 $A$ 的所有子集為元素的集合：

$$\mathcal{P}(A) \;\coloneqq\; \{S \mid S \subseteq A\}.$$

$\mathcal{P}(A)$ 的元素本身也是集合——這是冪集初看起來讓人感到奇特的原因。對任何 $A$，有兩個子集永遠保證在 $\mathcal{P}(A)$ 中：

• $\emptyset \in \mathcal{P}(A)$，因為空集是每個集合的子集。
• $A \in \mathcal{P}(A)$，因為 $A$ 永遠是其自身的子集。

逐步建構冪集

設 $A = \{1, 2, 3\}$。你可以按大小分組列舉所有子集：

大小	子集
0	$\emptyset$
1	$\{1\}$、$\{2\}$、$\{3\}$
2	$\{1,2\}$、$\{1,3\}$、$\{2,3\}$
3	$\{1,2,3\}$

因此：

$$\mathcal{P}(\{1,2,3\}) = \bigl\{ \emptyset,\; \{1\},\; \{2\},\; \{3\},\; \{1,2\},\; \{1,3\},\; \{2,3\},\; \{1,2,3\} \bigr\}.$$

計算元素個數：共有 $8$ 個。

冪集的基數

對於元素個數為 $|A| = n$ 的有限集合 $A$，

$$|\mathcal{P}(A)| = 2^n. \tag{1}$$

為何是 $2^n$？ 對 $A$ 中的 $n$ 個元素中的每一個，你面臨二元選擇：將它包含在子集中，或是排除在外。做出所有 $n$ 個選擇的不同方式總數為

$$\underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ 個因數}} = 2^n.$$

這就是 $\mathcal{P}(A)$ 也記作 $2^A$ 的原因。

驗證範例。 $|\{1,2,3\}| = 3$，所以 $|\mathcal{P}(\{1,2,3\})| = 2^3 = 8$。這與上面列出的八個子集一致。

幾個值得知道的小情形：

| $|A|$ | $|\mathcal{P}(A)|$ | 範例 | |-------|--------------------|---------| | $0$ | $1$ | $\mathcal{P}(\emptyset) = \{\emptyset\}$ | | $1$ | $2$ | $\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$ | | $2$ | $4$ | $\mathcal{P}(\{a,b\}) = \{\emptyset, \{a\}, \{b\}, \{a,b\}\}$ | | $3$ | $8$ | （如上） | | $10$ | $1024$ | — |

注意 $\mathcal{P}(\emptyset) = \{\emptyset\}$ 恰好有一個元素（空集本身），而非零個。

二進位字串的觀點

每個子集 $S \subseteq A$ 對應一個特徵函式（characteristic function），標記 $A$ 中哪些元素屬於 $S$：

$$\mathbf{1}_S \colon A \to \{0, 1\}, \quad a \mapsto \begin{cases} 1 & a \in S \\ 0 & a \notin S \end{cases}$$

對 $A = \{1, 2, 3\}$，將元素排序為 $(a_1, a_2, a_3) = (1, 2, 3)$，可得 $\mathcal{P}(A)$ 與長度為 3 的二進位字串之間的一個雙射：

子集	二進位字串 $(a_1, a_2, a_3)$
$\emptyset$	$(0,\;0,\;0)$
$\{1\}$	$(1,\;0,\;0)$
$\{2\}$	$(0,\;1,\;0)$
$\{3\}$	$(0,\;0,\;1)$
$\{1,2\}$	$(1,\;1,\;0)$
$\{1,3\}$	$(1,\;0,\;1)$
$\{2,3\}$	$(0,\;1,\;1)$
$\{1,2,3\}$	$(1,\;1,\;1)$

長度為 3 的二進位字串恰好有 $2^3 = 8$ 個，這獨立地確認了方程式 $(1)$。

這個雙射 $\mathcal{P}(A) \cong \{0,1\}^A$ 是記號 $2^A$ 更深層的原因：$2$ 就是集合 $\{0, 1\}$，而 $\{0,1\}^A$ 是從 $A$ 到 $\{0,1\}$ 的所有映射的集合。

無限集合的冪集

對於無限集合，方程式 $(1)$ 不再直接適用——但其精神仍然延續。**康托定理（Cantor’s theorem）**指出，對任意集合 $A$，不存在從 $A$ 到 $\mathcal{P}(A)$ 的滿射。特別地：

$$|A| < |\mathcal{P}(A)|$$

這意味著存在從 $A$ 到 $\mathcal{P}(A)$ 的單射（將每個 $a$ 送到 $\{a\}$），但不存在雙射。冪集永遠嚴格大於原來的集合，即使兩者都是無限的。

摘要

• 冪集 $\mathcal{P}(A)$ 是 $A$ 的所有子集的集合；其元素本身也是集合。
• 它永遠包含 $\emptyset$ 和 $A$ 本身。
• 對有限集合，$|\mathcal{P}(A)| = 2^{|A|}$——每種包含的二元選擇對應一個子集。
• 每個子集對應一個長度為 $|A|$ 的二進位字串，給出雙射 $\mathcal{P}(A) \cong \{0,1\}^A$；因此有替代記號 $2^A$。
• 康托定理：對任意集合 $A$，$\mathcal{P}(A)$ 嚴格大於 $A$——不存在滿射 $A \twoheadrightarrow \mathcal{P}(A)$。