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

RSS 阅读器可能不支持渲染数学公式。 点击这里阅读原文：

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

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

等势

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

对于有限集，答案很简单：数元素个数即可。但自然数集 是无穷的，无法「数到底」；因此我们需要一种新的工具。

定义（双射）。给定两个集合 与 ，若存在函数 满足：

• 单射：（不同的输入产生不同的输出）
• 满射：对每个 ，都存在 使得 （每个输出都被覆盖）

则称 为双射，并称 与 等势（记为 ）——即两者「大小相等」。

定义（可数集）。若集合 能与自然数集 建立双射（或 为有限集），则称 为可数集。

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

• 偶数集 可数：双射为 。
• 整数集 可数：可以用 把 映射到 。
• 有理数集 同样可数（可以用「对角线枚举法」把所有分数 排成一个序列——这是康托尔的另一个经典成果，与本文讨论的论证共享「对角线」之名，但用法不同；请读者注意不要把两者混淆）。

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

实数的不可数

定理（康托尔，1891）。区间 中的实数是不可数的。

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

我们采用反证法。

假设： 中的实数可数。即存在双射 ，使得我们可以把这些实数全部排成一个无穷列表：

其中 表示第 个数的第 位小数（取值 到 ）。

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

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

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

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

但根据我们的构造规则， 的第 位小数是 ，而 被刻意构造得与 （即 的第 位小数）不同：

这与 的假设矛盾！

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

然而 无疑是 中的实数（它的每一位都是合法的十进制数字）。

结论：无论你如何构造这份「实数大全列表」，总能构造出一个逃脱列表的实数 。这就说明最初的假设——存在双射 ——是假的。 中的实数不可数。

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

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

构造逃逸者

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

defdiagonal_construct(number_list, digits=10):
    """
    number_list：字符串列表，每个形如 "0.d1d2d3..."
    返回：通过对角线方法构造出的新数字字符串
    """
    new_digits = []
    for i, num_str inenumerate(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 恰好在相应的位置上与列表中的每一个数都不同。当然，这里演示的只是十个数的有限情形（真正的无穷列表毕竟无法存入计算机），但这恰恰是证明核心逻辑步骤——对任意 ，——的直观实例化。无论列表多长，这条构造规则都能保证新数逃脱每一个条目。

康托尔定理

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

康托尔定理。对任意集合 ，其幂集 （即 的所有子集构成的集合）的势严格大于 本身，即 。

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

证明

假设存在一个满射 （我们将证明这样的满射不存在，由此得到 ）。

对每个元素 ， 都是 的一个子集。现在构造一个特殊的子集：

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

由于 是满射，（作为 的子集，因而是 的元素）必有原像；即存在某个 使得 。

现在问： 吗？

• 若 ：根据 的定义，。由于 ，就有 。矛盾！
• 若 ：同理，，即 ，从而 。矛盾！

两种情况都导致自相矛盾，说明「存在满射 」这一假设站不住脚。因此 。

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

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

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

defcantor_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 notin 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)

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

停机问题

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

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

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

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

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

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

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

导出矛盾。现在考察具体的执行 。

• 若 （即判定「 停机」），那么根据 的定义， 应该死循环。这与「它停机」矛盾。
• 若 （即判定「 不停机」），那么根据 的定义， 应该立即停机。这与「它不停机」矛盾。

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

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

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

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

import sys
sys.setrecursionlimit(50)

defhypothetical_halts(f, x, fuel=10):
    """假想的停机判定器（仅用于悖论演示；并非真正可行的实现）"""try:
        result = f(x, fuel)
        return result isnotNoneexcept RecursionError:
        returnFalsedefD(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. 构造自指命题。利用编码技巧，构造一个命题 ，其核心内容是：这是一个高度自指的构造，其数学基础被称为对角线引理（又称不动点引理）：对任意只含一个自由变量的公式 ，都能构造一个句子 ，使系统证明 （其中 表示 的哥德尔数）。这个引理正是「对角线」思想在逻辑中的抽象：它让一个命题能够「谈论」关于其自身代码的某种性质。
3. 导出矛盾的两难。
   • 若系统能证明 ，那么根据 的含义（「 不可证明」），系统就同时证明了一个假命题——与系统的相容性矛盾。
   • 若系统能否证 （即证明 ，相当于证明「 可证明」），那么在合理的补充条件下，这同样会导致矛盾。
   • 因此 既不能被证明也不能被否证——它是系统内的一个「不可判定命题」。

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

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

延伸

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

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

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

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