形式陈述

康托对角线论证是一种反枚举构造。若假设所有无限二进制序列可列为

$$ s_0,s_1,s_2,\ldots, \qquad s_n=(s_n(0),s_n(1),\ldots), $$$$s_0,s_1,s_2,\dots ,s_n=(s_n(0),s_n(1),\dots ),$$

定义新序列 $d$$d$ 为

$$ d(n)=1-s_n(n). $$$$d(n)=1-s_n(n).$$

则对每个 $n$$n$，$d$$d$ 在第 $n$$n$ 位与 $s_n$$s_n$ 不同，所以 $d\ne s_n$$d\ne s_n$。因此列表不完备，$\{0,1\}^{\mathbb N}$$\{0,1{\}}^{\mathbb{N}}$ 不可数。

直觉

构造沿列表的对角线逐个“躲开”第 $n$$n$ 个候选对象：只需在专门分配给它的一位上不同，就能保证新对象不等于列表中的任何一项。

例子与边界

用十进制展开证明 $[0,1]$$[0,1]$ 不可数时必须处理 $0.4999\ldots=0.5000\ldots$$0.4999\dots =0.5000\dots$ 的双重表示；使用二进制序列或限制所用数字可避免歧义。对角线也出现在不可判定性证明中，但不同应用需确认“修改后的对象”仍属于目标集合。

推论与应用

该方法证明 $|\mathcal P(A)|>|A|$$|\mathcal{P}(A)|>|A|$、实数不可数以及不存在全体程序行为的完备枚举。其核心是自指式差异构造，而非几何上的矩阵对角线本身。

参考资料

• Paul R. Halmos, Naive Set Theory, 1960; Dover reprint 2017，§26。
• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019，Ch. 7。