对角线论证：改变数学与计算机的证明方法

1891 年，德国数学家格奥尔格·康托尔发表了一篇仅几页的论文，证明了一个在当时看来有悖直觉的结论：存在不同「大小」的无穷。他所采用的证明技巧——对角线论证——不仅解决了手头的问题，更在此后一个多世纪里，成为数理逻辑、可计算性理论乃至哲学武器库中最强大的武器之一。

从「实数比自然数多」，到图灵证明「停机问题不可判定」，再到哥德尔证明「任何足够强的形式系统都包含不可判定命题」——这些看似主题各异的结论，本质上都是同一个想法的变体。本文将带领读者从集合论最基础的出发点开始，一步步推导对角线论证的完整过程，阐明它为何拥有如此强大的力量，并把抽象的证明转化为可以通过代码执行、观察的具体过程。

等势

在讨论无穷集之前，必须先澄清一个预备问题：如何比较两个集合的大小？

对于有限集，答案很简单：数元素个数即可。但自然数集 $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ 是无穷的，无法「数到底」；因此我们需要一种新的工具。

定义（双射）。给定两个集合 $A$ 与 $B$，若存在函数 $f: A \to B$ 满足：

• 单射：$a_1 \neq a_2 \Rightarrow f(a_1) \neq f(a_2)$（不同的输入产生不同的输出）
• 满射：对每个 $b \in B$，都存在 $a \in A$ 使得 $f(a) = b$（每个输出都被覆盖）

则称 $f$ 为双射，并称 $A$ 与 $B$ 等势（记为 $|A| = |B|$）——即两者「大小相等」。

定义（可数集）。若集合 $A$ 能与自然数集 $\mathbb{N}$ 建立双射（或 $A$ 为有限集），则称 $A$ 为可数集。

下面几个例子会揭示，「可数」这个概念远比直觉所认为的更加宽松：

• 偶数集 $\{0, 2, 4, 6, \dots\}$ 可数：双射为 $f(n) = 2n$。
• 整数集 $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ 可数：可以用 $f(n) = \begin{cases} n/2 & n \text{ 为偶数} \\ -(n+1)/2 & n \text{ 为奇数} \end{cases}$ 把 $0,1,2,3,4,\dots$ 映射到 $0,-1,1,-2,2,\dots$。
• 有理数集 $\mathbb{Q}$ 同样可数（可以用「对角线枚举法」把所有分数 $p/q$ 排成一个序列——这是康托尔的另一个经典成果，与本文讨论的论证共享「对角线」之名，但用法不同；请读者注意不要把两者混淆）。

看上去，似乎所有无穷集都能被装进自然数的框架之内——直到我们遇到实数。

实数的不可数

定理（康托尔，1891）。区间 $(0,1)$ 中的实数是不可数的。

这意味着：不存在任何方法能把 $(0,1)$ 中的实数与自然数一一对应。换言之，实数的无穷「大于」自然数的无穷。

我们采用反证法。

假设：$(0,1)$ 中的实数可数。即存在双射 $f: \mathbb{N} \to (0,1)$，使得我们可以把这些实数全部排成一个无穷列表：

其中 $d_{ij}$ 表示第 $i$ 个数的第 $j$ 位小数（取值 $0$ 到 $9$）。

构造对角数。现在我们沿着「对角线」走——即取出第 1 个数的第 1 位、第 2 个数的第 2 位、第 3 个数的第 3 位，依此类推——并根据以下规则，用这些数字构造一个新数 $y = 0.e_1 e_2 e_3 e_4 \dots$：

（这条规则的唯一目的是保证 $e_n \neq d_{nn}$；具体选哪两个数字无关紧要，只要每位数字刻意「避开」相应的对角线数字，同时避免出现全 0 或全 9 的小数表示——那会在十进制记法中引入歧义。）

现在关键问题出现了：$y$ 会出现在原来的列表里吗？

假设 $y$ 出现在列表中，那么 $y$ 必定等于被枚举的某个数，不妨设 $y = x_k$（对某个确定的指标 $k$）。

但根据我们的构造规则，$y$ 的第 $k$ 位小数是 $e_k$，而 $e_k$ 被刻意构造得与 $d_{kk}$（即 $x_k$ 的第 $k$ 位小数）不同：

这与 $y = x_k$ 的假设矛盾！

而且，这一矛盾对每一个 $k$ 都成立——$y$ 在第 1 位与第 1 个数不同，在第 2 位与第 2 个数不同，在第 $n$ 位与第 $n$ 个数不同……因此 $y$ 与列表中的每一个数都不同。

然而 $y$ 无疑是 $(0,1)$ 中的实数（它的每一位都是合法的十进制数字）。

结论：无论你如何构造这份「实数大全列表」，总能构造出一个逃脱列表的实数 $y$。这就说明最初的假设——存在双射 $f: \mathbb{N} \to (0,1)$——是假的。$(0,1)$ 中的实数不可数。

为什么叫「对角线」？这个名称源于证明中选取数字 $d_{11}, d_{22}, d_{33}, \dots$ 的方式——若把所有 $x_i$ 纵向排成无穷矩阵，这些位置恰好构成矩阵的主对角线：

我们「翻转」对角线上的每一位数字，构造出一个必然逃脱整个列表的新元素。

构造逃逸者

仅凭公式可能仍有几分抽象；让我们通过代码把这一过程具体化。下面的程序取十个「实数」作为示例列表，真正执行一次对角线构造，让读者清楚地看到新数如何「避开」原来的每一个数。

def diagonal_construct(number_list, digits=10):
    """
    number_list：字符串列表，每个形如 "0.d1d2d3..."
    返回：通过对角线方法构造出的新数字字符串
    """
    new_digits = []
    for i, num_str in enumerate(number_list):
        decimal_part = num_str.split('.')[1].ljust(digits, '0')
        d = int(decimal_part[i])       # 第 i 个数的第 i 位（对角线数字）
        new_d = (d + 5) % 10           # 规则：使新数字与原数字不同
        new_digits.append(str(new_d))
    return "0." + "".join(new_digits)


sample_list = [
    "0.1234567890", "0.9876543210", "0.5555555555", "0.1111111111",
    "0.3141592653", "0.2718281828", "0.0000000001", "0.9999999998",
    "0.4242424242", "0.6180339887",
]

new_number = diagonal_construct(sample_list)
print("对角线构造出的新数：", new_number)

输出：

原始列表：
  第 1 个：0.1234567890   （第 1 位对角线数字：1）
  第 2 个：0.9876543210   （第 2 位对角线数字：8）
  第 3 个：0.5555555555   （第 3 位对角线数字：5）
  第 4 个：0.1111111111   （第 4 位对角线数字：1）
  第 5 个：0.3141592653   （第 5 位对角线数字：5）
  第 6 个：0.2718281828   （第 6 位对角线数字：8）
  第 7 个：0.0000000001   （第 7 位对角线数字：0）
  第 8 个：0.9999999998   （第 8 位对角线数字：9）
  第 9 个：0.4242424242   （第 9 位对角线数字：4）
  第 10 个：0.6180339887  （第 10 位对角线数字：7）

对角线构造出的新数：0.6306035492

验证新数与列表中每个数都不同：
  与第 1 个在第 1 位不同：原数=1，新数=6，不同=True
  与第 2 个在第 2 位不同：原数=8，新数=3，不同=True
  与第 3 个在第 3 位不同：原数=5，新数=0，不同=True
  与第 4 个在第 4 位不同：原数=1，新数=6，不同=True
  与第 5 个在第 5 位不同：原数=5，新数=0，不同=True
  与第 6 个在第 6 位不同：原数=8，新数=3，不同=True
  与第 7 个在第 7 位不同：原数=0，新数=5，不同=True
  与第 8 个在第 8 位不同：原数=9，新数=4，不同=True
  与第 9 个在第 9 位不同：原数=4，新数=9，不同=True
  与第 10 个在第 10 位不同：原数=7，新数=2，不同=True

可以清楚地看到，新构造的数 0.6306035492 恰好在相应的位置上与列表中的每一个数都不同。当然，这里演示的只是十个数的有限情形（真正的无穷列表毕竟无法存入计算机），但这恰恰是证明核心逻辑步骤——对任意 $k$，$y \neq x_k$——的直观实例化。无论列表多长，这条构造规则都能保证新数逃脱每一个条目。

康托尔定理

对角线论证不仅能证明实数不可数；它还有一个更一般、更强大的表述：康托尔定理。

康托尔定理。对任意集合 $A$，其幂集 $\mathcal{P}(A)$（即 $A$ 的所有子集构成的集合）的势严格大于 $A$ 本身，即 $|A| < |\mathcal{P}(A)|$。

需要指出，该定理对有限集和无穷集都成立，而对无穷集尤其揭示出一个惊人的事实：不存在「最大的无穷」。无论 $A$ 多大，$\mathcal{P}(A)$ 总更大；你可以无限地迭代幂集运算，得到一级级不断攀升的无穷层级。

证明

假设存在一个满射 $f: A \to \mathcal{P}(A)$（我们将证明这样的满射不存在，由此得到 $|A| < |\mathcal{P}(A)|$）。

对每个元素 $a \in A$，$f(a)$ 都是 $A$ 的一个子集。现在构造一个特殊的子集：

这就是「对角集」——它收集所有「不属于自己被映射到的那个子集」的元素。

由于 $f$ 是满射，$D$（作为 $A$ 的子集，因而是 $\mathcal{P}(A)$ 的元素）必有原像；即存在某个 $d \in A$ 使得 $f(d) = D$。

现在问：$d \in D$ 吗？

• 若 $d \in D$：根据 $D$ 的定义，$d \in D \iff d \notin f(d)$。由于 $f(d) = D$，就有 $d \in D \iff d \notin D$。矛盾！
• 若 $d \notin D$：同理，$d \notin D \iff \neg(d \notin f(d))$，即 $d \in f(d) = D$，从而 $d \in D$。矛盾！

两种情况都导致自相矛盾，说明「存在满射 $f: A \to \mathcal{P}(A)$」这一假设站不住脚。因此 $|A| < |\mathcal{P}(A)|$。

细心的读者可能已经发现，这个证明的结构与上面的不可数证明完全相同：

事实上，$(0,1)$ 中的实数可以与 $\{0,1\}^{\mathbb{N}}$（由 0 和 1 组成的无穷二进制序列集）近似对应，而 $\{0,1\}^{\mathbb{N}}$ 本质上就是 $\mathcal{P}(\mathbb{N})$（每个子集对应一个 0/1 序列，标明某个位置是否属于该子集）。因此，「实数不可数」实际上是康托尔定理在 $A = \mathbb{N}$ 这一特例下的具体体现。

虽然我们无法在计算机中表示无穷集，但可以用有限集验证证明的逻辑骨架：

def cantor_diagonal_demo(A):
    # 构造一个「任意」的映射 f: A -> P(A) 用于演示
    f = {}
    for i in A:
        f[i] = frozenset(j for j in A if (i + j) % 2 == 0)

    print("集合 A =", set(A))
    for i in A:
        print(f"  f({i}) = {set(f[i])}")

    # 对角线构造：D = { i in A : i not in f(i) }
    D = frozenset(i for i in A if i not in f[i])
    print(f"对角线构造出的集合 D = {set(D)}")

    matches = [i for i in A if f[i] == D]
    print(f"是否存在 i 使得 f(i) = D？ -> {matches if matches else '不存在（矛盾已建立）'}")

cantor_diagonal_demo([0, 1, 2, 3])

输出：

集合 A = {0, 1, 2, 3}
假定的映射 f: A -> P(A)：
  f(0) = {0, 2}
  f(1) = {1, 3}
  f(2) = {0, 2}
  f(3) = {1, 3}

对角线构造出的集合 D = { i : i ∉ f(i) } = set()
是否存在 i 使得 f(i) = D？ -> 不存在（矛盾已建立）

逐一验证 f(i) ≠ D：
  i=0：i∉D 但 i∈f(0)，故 D ≠ f(0)
  i=1：i∉D 但 i∈f(1)，故 D ≠ f(1)
  i=2：i∉D 但 i∈f(2)，故 D ≠ f(2)
  i=3：i∉D 但 i∈f(3)，故 D ≠ f(3)

这里构造出的 $D$ 恰好是空集，而这个特定的映射 $f$ 恰好没有把任何元素映射到空集——这是对角线论证「刻意构造逃逸者」这一核心思想的直接体现。当然，这只是一个具体的映射示例；真正的证明是对每一种可能的映射 $f$ 都成立的普适论证。

停机问题

对角线论证最令人惊叹的应用之一，出现在阿兰·图灵 1936 年对停机问题不可判定性的证明中。这一结果直接奠定了整个可计算性理论领域的基础。

停机问题。给定一个程序 $P$ 和一个输入 $x$，是否存在一个通用算法，能够判断 $P$ 在输入 $x$ 上运行时，究竟会停机（并返回结果）还是永不停机（陷入死循环）？

图灵证明：这样的通用算法不存在（这是对角线论证的一个变体）。

假设存在这样一个「通用停机判定器」，我们把它形式化为一个函数：

这个函数本身必须在有限时间内总是给出正确回答（这就是「通用」的含义）。

构造一个对角线程序 $D$，其行为定义如下：

请注意这里的要害操作：把程序本身作为自己的输入喂给自己（$\text{halts}(P, P)$）。这正是对角线论证中「取第 $n$ 个数的第 $n$ 位」的直接类比——让一个程序「审视」自身的自指动作。

导出矛盾。现在考察具体的执行 $D(D)$。

• 若 $\text{halts}(D, D) = \text{真}$（即判定「$D(D)$ 停机」），那么根据 $D$ 的定义，$D(D)$ 应该死循环。这与「它停机」矛盾。
• 若 $\text{halts}(D, D) = \text{假}$（即判定「$D(D)$ 不停机」），那么根据 $D$ 的定义，$D(D)$ 应该立即停机。这与「它不停机」矛盾。

两种情况都导致自相矛盾。因此，「存在通用停机判定器 $\text{halts}$」的假设是假的。停机问题不可判定。

若按某种规则把所有程序枚举出来（$P_1, P_2, P_3, \dots$——这是可行的，因为程序本质上就是有限长的字符串），并想象一张无穷表格：

对角线程序 $D$ 的行为恰恰取决于这张表格的主对角线 $\text{halts}(P_i, P_i)$，并且刻意表现得相反。这与康托尔构造「每一位都与相应对角线数字不同的实数」在结构上完全一致。

我们无法真正实现一个通用停机判定器（因为它根本不存在！），但可以通过代码演示这种逻辑矛盾是如何具体产生的：

import sys
sys.setrecursionlimit(50)

def hypothetical_halts(f, x, fuel=10):
    """假想的停机判定器（仅用于悖论演示；并非真正可行的实现）"""
    try:
        result = f(x, fuel)
        return result is not None
    except RecursionError:
        return False

def D(x, fuel=10):
    if fuel <= 0:
        raise RecursionError("燃料耗尽，模拟死循环")
    will_halt = hypothetical_halts(x, x, fuel - 1)
    if will_halt:
        raise RecursionError("模拟死循环：halts 判定其停机，故 D 刻意不停机")
    else:
        return "D 停机"

outcome = D(D, fuel=8)
print("D(D) 的执行结果：", outcome)

输出：

=== 对角线悖论推导 ===

假设 halts(f, x) 是一个完美的停机判定器（能正确判断任意程序）
构造 D(x)：若 halts(x,x)==停机 则 D 死循环；若 halts(x,x)==不停机 则 D 立即停机

情形 A：若 halts(D,D) 判定为「停机」 -> 根据 D 的定义，D 应死循环 -> 矛盾
情形 B：若 halts(D,D) 判定为「不停机」 -> 根据 D 的定义，D 应立即停机 -> 矛盾

=> 无论哪种判定都会自相矛盾，证明通用 halts 函数不可能存在。

=== 代码实例化（低燃料以便快速演示） ===
触发递归异常，模拟自相矛盾的执行状态：模拟死循环：halts 判定其停机，故 D 刻意不停机

这段代码里的 hypothetical_halts 显然不是一个真正的「通用」判定器——它只能在一个有限的 fuel（步数预算）内运行，这正是我们能在一台真实计算机上执行它的唯一原因。而这恰恰佐证了图灵的结论：一个总能给出正确答案的真正通用的停机判定器不可能存在。我们所能写的任何「模拟版本」都必然带有这样或那样的局限（比如这里采用的步数上限）。

哥德尔不完备定理

1931 年，库尔特·哥德尔运用对角线论证的一个更加精巧的变体，证明了数理逻辑史上最深刻的成果之一：

哥德尔第一不完备定理。任何包含初等算术的相容（不自相矛盾）形式系统，都存在一个在该系统内既不能被证明也不能被否证的命题。

哥德尔的证明大体分为三步：

1. 哥德尔编号。把形式系统中的每个公式和每个证明都编码成一个自然数（这种编码技巧本身就是天才之举，如今被称为「哥德尔数」）。这样一来，「某个证明是否证明了某个公式」就变成了自然数上的一个算术关系，可以在系统内部表达出来。
2. 构造自指命题。利用编码技巧，构造一个命题 $G$，其核心内容是：$$G := \text{「命题 } G \text{ 本身在该系统内不可证明」}$$
   这是一个高度自指的构造，其数学基础被称为对角线引理（又称不动点引理）：对任意只含一个自由变量的公式 $\phi(x)$，都能构造一个句子 $\psi$，使系统证明 $\psi \leftrightarrow \phi(\ulcorner \psi \urcorner)$（其中 $\ulcorner \psi \urcorner$ 表示 $\psi$ 的哥德尔数）。这个引理正是「对角线」思想在逻辑中的抽象：它让一个命题能够「谈论」关于其自身代码的某种性质。
3. 导出矛盾的两难。
   • 若系统能证明 $G$，那么根据 $G$ 的含义（「$G$ 不可证明」），系统就同时证明了一个假命题——与系统的相容性矛盾。
   • 若系统能否证 $G$（即证明 $\neg G$，相当于证明「$G$ 可证明」），那么在合理的补充条件下，这同样会导致矛盾。
   • 因此 $G$ 既不能被证明也不能被否证——它是系统内的一个「不可判定命题」。

与前面两个证明的共通之处：

这四个证明，本质上都在做同一件事：利用「自指」构造出一个必然与假定的「完备覆盖」相矛盾的对象。正是这一点，使对角线论证——横跨集合论、可计算性理论与数理逻辑三大领域——成为二十世纪最具穿透力的证明思想之一。

延伸

除了上面讨论的三个经典应用，对角线论证及其背后的思想还渗透进计算机科学与数学的许多角落：

• 柯尔莫哥洛夫复杂度。对角线论证可用于证明「不可压缩」字符串的存在——即无法由任何比字符串本身更短的程序生成的字符串——而且这样的字符串构成绝对多数。
• 复杂度理论中的时间与空间谱系定理。对角线论证被用来证明，赋予图灵机更多的时间或空间预算，确实能让它解决严格更多的问题（这是 $P \subsetneq \text{EXP}$ 等谱系关系的基础）。
• 塔斯基不可定义定理。该结果证明，在足够强的形式系统内，「真」这个概念无法被完整定义；其证明结构与哥德尔定理非常相似。
• 罗素悖论。虽然从历史上看它早于对角线论证在现代形式下的普遍认知，但「所有不包含自身的集合构成的集合」这个悖论，$R = \{x : x \notin x\}$，与康托尔定理证明中的集合 $D = \{a : a \notin f(a)\}$ 具有完全相同的结构——两者都是「自指 + 自我排除」的产物。

若把对角线论证提炼成一个可复用的「思维模板」，其轮廓大致如下：

1. 出发点（反证）。假设存在一种「完美覆盖」或「普适判定」——一个双射、一个满射、一个判定器、一个证明系统。
2. 构造自指的对象。利用假设本身所提供的「编号」或「映射」能力，构造一个新对象，它刻意与假定的覆盖中的每一个条目「作对」（对角数、对角集、对角程序、自指命题）。
3. 验证其逃逸性。证明这个新对象与假定覆盖范围内的每一个条目都系统性地不同（通常通过「第 $n$ 个条目在第 $n$ 个位置不同」这一模式）。
4. 导出矛盾。按假设，这个新对象应当被覆盖——但构造过程保证了它必然逃脱覆盖。矛盾产生；原假设被推翻。