对角线论证

对角线论证（diagonal argument）把一份声称“已经列尽”的名单与它自己的第 $n$ 项在第 $n$ 个位置比较，再构造一项处处与名单对应项不同的对象。核心不是画出一条对角线，而是保证新对象确实属于所讨论的集合，同时不可能等于名单中任何一项。

幂集不可能被原集合列尽

设 $A$ 为任意集合，暂时假定有满射 $f:A\to 𝒫(A)$，即 $A$ 的每个子集都等于某个 $f(a)$。定义 $$D=\{a\in A:a\notin f(a)\}.$$ 这个定义对每个 $a$ 做了一次“反着选”：若 $a$ 在名单给它的子集中，就不放进 $D$；否则放进 $D$。由于 $D\subseteq A$，满射假设给出某个 $d\in A$ 使 $f(d)=D$。

现在只问 $d$ 是否属于 $D$。由定义，$d\in D$ 当且仅当 $d\notin f(d)=D$，矛盾。因此原先的满射不存在。证明没有依赖 $A$ 有限或无限；即使 $A=\varnothing$，其幂集仍含一个元素，也不可能由空集满射到它。

与实数不可数的联系

对实数小数展开的名单，第 $n$ 位扮演“$a\in f(a)$”的角色；构造新小数时在该位选不同数字。新数于是与第 $n$ 个数不同，适用于每个 $n$。不可数集给出完整的小数构造。使用小数时需处理 $0.4999\dots =0.5$ 这样的双重表示，不能只写“每位改一下”就结束。

参考资料

• MIT，Mathematics for Computer Science，Cardinality 章节。
• MIT 18.100A Fall 2020，实分析讲义。
• 继续阅读：幂集、双射、不可数集。