康托对角线论证

论证的图像是一张无限表格：第 $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无法单射进自然数集的集合；任何自然数编号的名单都会遗漏成员。。具体地，编码 $a\mapsto \sum _{j\ge 0}2a_j{3}^{-(j+1)}$ 的两条序列若首次在位置 $k$ 不同，该位贡献相差 $2\cdot 3^{-(k+1)}$，全部后续位最多抵消 $3^{-(k+1)}$，所以结果仍相差至少 $3^{-(k+1)}>0$。这直接证明了所需的单射性。

边界之一是表示的歧义：若直接对十进制展开使用对角线，必须处理 $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用总停机判断器的自反转构造证明 HALT 不可判定，并区分识别、有限步数检查与局部终止性证明。不可判定的证明就是对角线：假想的停机判定器被用来构造一个"在自己身上反着做"的程序。复杂性理论中，时间层级定理理路时间层级定理Time hierarchy theorem在可构造时间界下，给予更多渐近时间会严格扩大可判定语言类。与空间层级定理理路空间层级定理Space hierarchy theorem在适当空间可构造性条件下，更多渐近空间严格提升可判定语言能力。沿用同样的对角骨架，在相应的可构造性与资源间隙条件下证明更多资源确实能计算更多语言。这些应用共享同一个核心——自指式差异构造，与矩阵对角化无关；掌握"给每个候选分配一个专属位置并在该处偏离"这一模式，就能识别这些变体。