在对角线上改一笔：从康托尔到哥德尔、图灵与不动点

假设有人递给你一本目录，声称里面收录了所有可能的东西。怎样证明他漏了一项？

最直接的办法，是找到一个不在目录里的东西。但如果目录无限长，你既没法翻完，也没法逐一核对。对角线方法提供了一个漂亮的思路：利用目录本身，制造一个与第一个条目在第一处不同、与第二个条目在第二处不同、与第 n 个条目在第 n 处不同的新对象。

这样，你不必检查整本目录，就知道它一定漏了这一项。

康托尔用它研究无穷的大小。罗素在集合里遇见了它。哥德尔把它嵌进算术，图灵把它写成程序。到了范畴论，这个动作又显露出另一面：它不仅能制造“列不进去的东西”，也能制造不动点。

这篇文章沿着这条线走一遍。公式可以慢慢看，先记住一个动作：让描述对准自己，再对结果做一次变换。

一、康托尔：无穷清单也会漏项

自然数有无穷多个，偶数也有无穷多个。虽然偶数看起来只占自然数的一半，却可以通过 n ↦ 2n 与自然数一一配对。对无穷集合来说，“是它的一部分”并不自动意味着“比它小”。

那么，有没有一种无穷，真的比自然数更多？

考虑所有由 0 和 1 组成的无限序列。假设它们能按自然数编号，排成下面这样的一张表。表中的数字只是示意，论证对任何排列都成立。

序列编号	第 1 位	第 2 位	第 3 位	第 4 位	…
1	0	1	0	1	…
2	1	1	0	0	…
3	0	0	1	1	…
4	1	0	1	0	…
…	…	…	…	…	…

取出加粗的对角线：0、1、1、0、……，再逐位翻转，得到一个新序列：1、0、0、1、……。

它不可能是第一行，因为第一位不同；不可能是第二行，因为第二位不同；也不可能是第 n 行，因为第 n 位不同。

我们明明假设列出了全部序列，却又制造出了一个没有被列出的序列。因此，所有无限二进制序列无法被自然数编成一份完整清单。

这里直接谈序列，可以避开小数展开不唯一的麻烦。如果要联系实数，只需把序列的 0、1 分别换成三进制小数中的 0、2；不同序列会给出不同实数。所以实数也不可能被自然数列尽。

这个证明还有一个更一般的版本。设有人试图给集合 A 的所有子集编号，为每个 a 指定一个子集 F(a)。我们构造：

\[D=\{a\in A\mid a\notin F(a)\}.\]

如果 D 也有编号 d，即 F(d)=D，就会得到：

\[d\in D\quad\Longleftrightarrow\quad d\notin D.\]

于是，任何从 A 到它的幂集（所有子集组成的集合）的映射，都不可能满射。这就是康托尔定理。

值得留意的是，我们没有发现集合论本身有矛盾。被否定的是“这份清单能够列全”的假设。对角线上改一笔，得到的是一张清单的边界。

现在，把问题从“给子集编号”换成“什么条件都能定义一个集合”。

如果任意性质都能圈出一个集合，那么下面这个集合似乎也应该存在：

\[R=\{x\mid x\notin x\}.\]

它收集所有“不属于自身”的集合。接着问：R 属于 R 吗？

如果属于，按照定义，它就不属于自己。如果不属于，按照定义，它又应该被收进去。

\[R\in R\quad\Longleftrightarrow\quad R\notin R.\]

这是罗素悖论。它与康托尔的构造只隔了一小步：康托尔问“编号 a 是否属于编号 a 所指的集合”，罗素问“集合 x 是否属于集合 x”。两次出现的同一个变量，就是隐藏的对角线。

为什么康托尔得到定理，罗素却得到悖论？因为两者在不同地方提出了过强的要求。康托尔暂时假设存在完整枚举，再推翻这个假设；无限制的集合概括原则则直接保证 R 存在，因而把矛盾带进了体系。

现代 ZF 集合论中的分离公理只允许我们从一个已有集合里筛选元素。对任意已有集合 A，可以定义：

\[R_A=\{x\in A\mid x\notin x\}.\]

这个集合不会造成悖论；同样的推理只会告诉我们 R_A 不属于 A。如果存在一个包含所有集合的集合，它当然也得包含 R_A，矛盾才会重新出现。

因此，问题不在于数学禁止谈论自己，而在于哪些“收集一切”的承诺不能成立。

三、哥德尔：把“这句话”变成一个数

说谎者悖论的句子是：“这句话是假的。”哥德尔的关键转向是把“假”换成“不可证明”：

这句话在形式系统 T 中不可证明。

这次为什么没有立刻发生矛盾？因为“是真的”和“能在 T 中证明”是两回事。一句话完全可能是真的，却没有 T 内部的证明。

但自然语言里写出“这句话”很容易。算术只有数、加法、乘法和逻辑符号，怎样让它谈论自己？

第一步是编码。公式可以编码为自然数，证明也可以编码为自然数。原本关于符号串的问题——“这串符号是不是那句话的证明”——就转成了关于数的问题。

第二步是把代入操作也编码。给一个带空位的公式填入某个数，是一种可以机械执行的操作；填入这个公式自身的编码，也一样。语法层面的自我代入，便成了算术能够描述的运算。

这里的核心工具叫作对角引理。对于满足相应算术表达能力的理论 T，给定一个单自由变量公式 φ(x)，可以构造一句 G，使得：

\[T\vdash G\leftrightarrow\varphi(\ulcorner G\urcorner).\]

尖括号表示 G 的编码所对应的数码，符号 ⊢ 表示“系统能够证明”。这句话说的是：G 与“把 G 的编码填进 φ”在系统内部可证等价。

它是一个精确的自指装置，而不是在公式旁边偷偷补一句“此处指的是它自己”。

现在令 φ(x) 表示“编码为 x 的句子在 T 中不可证明”，就得到：

\[T\vdash G\leftrightarrow\neg\operatorname{Prov}_T(\ulcorner G\urcorner).\]

假如 T 证明了 G，那么那份具体证明的存在，又能让 T 证明“G 可证明”；而根据上面的等价式，T 同时证明“G 不可证明”。因此，只要 T 一致，它就不能证明 G。

想进一步断言 T 也不能证明 ¬G，需要注意假设：对通常的哥德尔句，原始论证使用比一致性更强的 ω-一致性；如果直接假定 T 的定理在标准自然数中都为真，也足够。Rosser 后来修改了句子的构造，使不可判定性的结论只需一致性。

常见的现代版本因此是：任何一致、可有效公理化、并且包含足够初等算术的经典理论，都有既不能证明也不能反驳的句子。“足够强”和“公理可有效生成”都不能随手删掉。

在这里，对角线没有制造一个真假矛盾，而是制造了一个系统无法凭自身证明能力解决的句子。它也第一次让“不动点”的意味变得清晰：G 与对其自身编码施加某种逻辑操作后的结果，达成了可证等价。

四、图灵：把反着做写成程序

程序同样可以编码，也可以作为数据传给另一个程序。于是，“把自己代入自己”有了一个很具体的版本：让程序接收自己的代码。

假设存在一个万能的停机判定程序 H。输入程序 p 和数据 x，它总能在有限时间内正确回答：p 在输入 x 上会不会停止？

利用它，我们写出下面的程序：

程序 D(p)：
    如果 H(p, p) 回答“会停止”：
        永远循环
    否则：
        立即停止

然后让 D 接收自己的代码，运行 D(D)。

如果 H 预测它会停止，它就永远循环；如果 H 预测它不会停止，它就立即停止。无论 H 回答什么，都错了。

所以不存在这样一个对所有程序和输入都正确、并且自身总会停止的判定程序。

这里有两个容易混淆的地方。第一，某些具体程序的停机情况完全可以判断；不可能的是覆盖全部情况的统一算法。第二，通用解释器依然存在，它可以模拟任何程序，只是被模拟的程序不停机时，模拟也可能一直进行下去。

换句话说，程序能够被列成清单，但它们的停机行为不能被一个总会给出答案的算法全部判定。若把“有通用解释器”误当成“有万能停机判定器”，就恰好抹掉了证明中最重要的区别。

这是对图灵不可判定性结果的现代停机问题表述；1936 年原论文使用的是机器、可计算数以及相关判定问题的语言。

五、把四个故事叠在一起

现在可以看见它们共同的轮廓：先建立对象与描述之间的联系，再让描述对准自身，最后施加一个会制造冲突的操作。

场景	自我代入发生在哪里	接下来做什么	暴露出的边界
康托尔	第 n 个序列的第 n 位	翻转这一位	清单无法列全
罗素	集合是否属于自身	对成员关系取否定	无限制概括导致矛盾
哥德尔	句子谈论自身的编码	断言自身不可证明	有效而一致的算术理论不完备
图灵	程序以自身代码为输入	与预测的停机行为相反	全面的停机判定算法不存在

这张表是理解结构的路标，不是把四份证明互相替代的许可证。特别是哥德尔的“可证明”不能直接换成“真”，图灵的部分计算也不能当成处处有值的普通函数。

那么，这种共同结构能不能写成一个定理？

六、Lawvere：对角线的另一面是不动点

先不用范畴论，只考虑一个二元函数：

\[E:A\times A\longrightarrow B.\]

把第一个输入理解为“描述或编号”，第二个输入理解为“被描述的对象”，输出则是 B 中的某个值。固定编号 a，就得到一行函数 E(a, −)。

假设这份描述系统足够完整：每个函数 g:A→B，都能由某个 a 表示，也就是对所有 x 都有 E(a,x)=g(x)。

再任取一个变换 α:B→B，构造：

\[g(x)=\alpha(E(x,x)).\]

这就是熟悉的动作：取对角线，再做变换。由于假设描述系统完整，g 也有一个编号 a。于是：

\[E(a,x)=g(x).\]

令 x=a，便得到：

\[E(a,a)=g(a)=\alpha(E(a,a)).\]

记 b=E(a,a)，结论就是：

\[b=\alpha(b).\]

b 是 α 的不动点。所谓不动点，就是经过某种变换以后仍保持不变的东西；这里并不要求反复迭代，也没有极限或收敛过程。

我们由此得到了一个非常简洁的命题：

如果 E 的各行能表示所有从 A 到 B 的函数，那么 B 上的每个自映射都有不动点。

把它反过来看：只要 B 上存在一个没有不动点的变换，这种完整的表示系统就不可能存在。

例如，取 B={0,1}，令 α 把 0 和 1 互换。它显然没有不动点，所以不可能用 A 为所有 A→{0,1} 的函数编出完整目录。而这样的函数恰好对应 A 的子集：输出 1 表示属于，输出 0 表示不属于。

康托尔定理，就这样从一个不动点命题的逆否形式里重新出现了。

七、范畴论究竟统一了什么？

范畴论把刚才的构造提炼成对象与箭头之间的关系。在笛卡尔闭范畴中，我们有乘积 A×A、表示“从 A 到 B 的函数”的指数对象 Bᴬ，以及把函数应用到输入上的求值箭头。

还有一个对角箭头：

\[\Delta_A:A\longrightarrow A\times A,\qquad x\longmapsto(x,x).\]

平时表格里的那条斜线，到这里变成了“复制同一个输入”的结构。整个构造只需要三步：

\[A\xrightarrow{\Delta_A}A\times A\xrightarrow{E}B\xrightarrow{\alpha}B.\]

在集合中，这就是 x ↦ α(E(x,x))。在别的范畴中，同一串箭头则可以承载相应的结构。

更精确地说，若 E:A×A→B 弱点满射，即每个箭头 g:A→B 都有一个点 a:1→A，使得对每个点 x:1→A 都有 E(a,x)=g(x)，那么每个箭头 α:B→B 都存在点 b:1→B 满足 α∘b=b。这里 1 是终对象，“点”由从 1 出发的箭头表达。

这就是 Lawvere 在 1969 年给出的不动点定理的常用表述。在一般范畴中，“所有点上的值相同”未必推出箭头相同，因此不能不加说明地把弱点满射当成普通满射；在集合范畴中，它就是前面所用的逐行表示条件。

那么，可以说这些理论“同构”吗？日常语言中，用“结构同构”表达惊人的相似性可以理解。但数学上，同构需要明确指出是哪两个对象，以及互为逆的结构保持映射。康托尔定理、罗素悖论、哥德尔不完备定理与图灵不可判定性，并不是四个可以直接宣称彼此同构的对象。

这里确实有一个严格的自然对应：

\[\operatorname{Hom}(A\times A,B) \cong \operatorname{Hom}(A,B^A).\]

左边把 E 看成“接收编号和输入的二元操作”，右边把它看成“由编号选出一个函数的目录”。两种写法可以相互转换，这就是柯里化对应，也是指数对象的基本性质。

而对四个故事，更准确的说法是：它们的核心对角构造可以放进同一个抽象框架；不同结论还需要各自的逻辑、编码与可计算性条件。

尤其不能拿 B={真,假} 上的取反，直接替代哥德尔的“不可证明”。前者没有不动点；后者构造的是句子与关于其编码的断言之间的可证等价。要把这种联系写成严格的范畴化证明，必须处理语法、代入和可证等价，而不是仅给符号换个名字。

同样，通用程序求值可能不终止，不符合前面集合版本中 E 处处有值的假设。关于程序自指的正面结论需要合适的计算框架；Kleene 递归定理便允许程序在行为意义上获得相应的不动点。这与停机问题的否定结论并不冲突。

八、一种构造，两种结局

走到这里，对角线方法就有了两张面孔。

如果变换没有不动点，例如真假翻转，那么自我代入会告诉我们：某种全包式的描述、收集或判定承诺不能成立。

如果适当的表示机制确实存在，自我代入就会迫使不动点出现。逻辑中的自指句、计算中的递归结构，都能从这个方向理解，但各自还要满足相应的技术条件。

所以，“自指必然导致悖论”并不准确。自指有时制造矛盾，有时暴露表达与证明的边界，有时则让递归成为可能。真正决定结果的，是表示机制允许你做什么，以及最后施加的变换能不能容纳不动点。

康托尔从一张无限清单里抽出对角线，证明无穷还有更大的无穷。此后的数学家不断把同一个动作放进新的世界：集合问自己是否属于自己，句子谈论自己的证明，程序接收自己的代码。

最初看上去只是“在对角线上改一笔”的小技巧，最终变成了一个关于描述能力的深刻问题：当一套描述把自身也纳入对象时，它究竟还能承诺多少？