幂集

集合 $A$ 的幂集（power set）是 $A$ 的所有子集组成的集合，记作 $𝒫(A)$。例如 $A=\{a,b\}$ 时， $$𝒫(A)=\{\varnothing ,\{a\},\{b\},\{a,b\}\}.$$ 这里 $\varnothing$ 与 $A$ 本身都必须列入；缺少其中一个，就没有列出“所有”子集。

子集的二选一计数

若 $A$ 有 $n$ 个不同元素，构造一个子集时，每个元素独立地选择“收入”或“不收入”。两种选择重复 $n$ 次，共有 $2^n$ 种互不相同的选择，因此 $$|𝒫(A)|=2^n(|A|=n).$$ 当 $n=0$ 时也成立：空集唯一的子集是它自己，故 $𝒫(\varnothing )=\{\varnothing \}$，元素个数为 $2^0=1$。

把子集写成一串 0、1 也能核对计数。例如 $A=\{a,b,c\}$，串 101 表示收入 $a,c$ 而不收入 $b$；八个三位二进制串与八个子集一一对应。这种对应比背诵 $2^n$ 更能说明指数从哪里来。

元素类型与大小

若 $a\in A$，那么 $\{a\}\in 𝒫(A)$，但通常不能写 $a\in 𝒫(A)$；后者还要求 $a$ 本身是 $A$ 的一个子集。对无限集合，仍有 $A$ 无法与其幂集建立双射，证明见对角线论证。所以幂集不只是有限情形中的一个计数技巧。

参考资料

• MIT，Mathematics for Computer Science，集合与计数章节。
• OpenStax《Contemporary Mathematics》1.2：子集与幂集。
• 继续阅读：子集与真子集、双射、对角线论证。