康托对角线论证

论证的图像是一张无限表格：第 $n$ 行写下第 $n$ 个候选序列，然后沿对角线走，把第 $n$ 行第 $n$ 列的值翻转，拼出新序列 $d$。要保证 $d$ 不等于表中任何一行，本不需要处处不同——每行只需一处不同即可，而对角线恰好给每一行"专门分配"了一个位置去制造差异，且这些位置互不冲突。这就是论证以线性的努力击败整张表格的原因：反驳第 $n$ 个候选只花费第 $n$ 位这一格。更深一层看，它是一种自指式构造：新对象的定义引用了"枚举本身"，使得任何自称完备的枚举都被用来制造自己的反例。因此结论不是"这张表列错了"，而是"任何表都必然遗漏"——量词落在所有枚举上。

具体走一遍：若表格前三行是 $s_0=0,0,0,\dots$、$s_1=1,1,1,\dots$、$s_2=0,1,0,\dots$，则 $d$ 的前三位是 $1-0=1$、$1-1=0$、$1-0=1$；无论后面如何延续，$d$ 已在第 0、1、2 位分别与这三行错开。由此立即得到实数不可数：$\{0,1{\}}^{\mathbb{N}}$ 不可数，而它可单射入 $[0,1]$（例如把序列读作三进制只用数字 $0,2$ 的小数，避开进位歧义），故 $[0,1]$ 与 $\mathbb{R}$ 都是不可数集公理库不可数集Uncountable set无法单射进自然数集的集合；任何自然数编号的名单都会遗漏成员。。

边界之一是表示的歧义：若直接对十进制展开使用对角线，必须处理 $0.4999\dots =0.5000\dots$ 这类双重表示——新数字与旧数字不同不等于新实数与旧实数不同。补救办法是规定翻转规则避开 $0$ 和 $9$（例如一律在 $4,5$ 之间切换），或改用上述二进制序列加保距编码。边界之二是"修改后的对象必须仍属于目标集合"：把对角线用于证明某类对象不可枚举时，若翻转把对象带出该类，论证即失效。可计算性理论里这是真实的陷阱——全体部分可计算函数公理库部分可计算函数Partial computable function允许机器在函数未定义的输入上不停机的部分函数。可以被有效枚举，对角线之所以不能直接反驳这一点，是因为对部分函数取"翻转"可能在未定义处无从翻转；只有对全函数的假想枚举，对角化才产生矛盾，由此得到的是"可计算全函数没有可计算的完备枚举"。

对角线论证是数学中少数被反复移植的证明模式。集合论中它给出 Cantor 定理 $|\mathcal{P}(A)|>|A|$，从而由幂集公理库幂集Power set把 A 的每一种子集选择提升为元素所得的集合，记作 P(A)。迭代产生无穷多个越来越大的基数，也直接支撑基数公理库基数Cardinality · Size of a set忽略元素性质与排列，只用双射和单射刻画集合的大小及其比较。层级的非平凡性；实数不可数是它的第一个历史应用。可计算性理论中，停机问题公理库停机问题不可判定性Halting problem · Undecidability of halting不存在一个对任意程序和输入都能正确判断程序是否停机的算法。不可判定的证明就是对角线：假想的停机判定器被用来构造一个"在自己身上反着做"的程序。复杂性理论中，时间层级定理公理库时间层级定理Time hierarchy theorem在可构造时间界下，给予更多渐近时间会严格扩大可判定语言类。与空间层级定理公理库空间层级定理Space hierarchy theorem在适当空间可构造性条件下，更多渐近空间严格提升可判定语言能力。沿用同样的对角骨架，在相应的可构造性与资源间隙条件下证明更多资源确实能计算更多语言。这些应用共享同一个核心——自指式差异构造，与矩阵对角化无关；掌握"给每个候选分配一个专属位置并在该处偏离"这一模式，就能识别这些变体。