第15章：一致性与完备性——形式系统的两堵墙

你能建造一个不说谎、又无所不知的系统吗？

---

第14章给了我们一台精密的机器：形式系统接受公理，按推断规则运行，输出定理。这台机器看起来很可靠。但"看起来"不够好。我们需要知道它实际上有多可靠。

这个问题有两个维度，方向相反。

第一个维度：系统会不会说谎？也就是说，它证明出来的东西，是不是都真的成立？这叫一致性。

第二个维度：系统会不会遗漏？也就是说，所有真的东西，它能不能都证明出来？这叫完备性。

两个要求都很合理。20世纪初，数学家 David Hilbert 雄心勃勃地相信，可以为整个数学建立一个同时满足这两个条件的形式基础——严格、完备、无懈可击。这个计划叫做 Hilbert 纲领。

1931年，一个26岁的奥地利数学家，用两个定理，把这个纲领彻底摧毁了。

---

15.1 一致性：系统不说谎

先精确说清楚"说谎"是什么意思。

如果一个形式系统能同时证明某个命题 $A$ 和它的否定 $\mathrm{\neg }A$，这个系统就是不一致的。一旦发生这种情况，灾难是全面的：从 $A$ 和 $\mathrm{\neg }A$ 出发，利用标准的推断规则，可以证明任何命题。一个能证明所有命题的系统，等于什么都没有证明。

所以一致性是形式系统的底线，低于这条线的系统是废的。

兔狲教授评

"废"不是形容词，是诊断结论。一旦不一致，系统能证明所有命题，包括"1=2"。这不是系统"有点不对"，而是系统失去了证明的全部意义——它能证明一切，等于什么都没证明。这是全面失效，不是局部故障。

"任何命题都可证"——为什么这是灾难？

这个推论有一个拉丁名：ex contradictione quodlibet（从矛盾可得任意结论）。证明过程非常短：已知 $A$ 为真，所以 $A\vee B$ 为真（添加析取）；已知 $\mathrm{\neg }A$ 为真，由 $\mathrm{\neg }A$ 和 $A\vee B$ 可得 $B$（析取消去）。$B$ 是任意命题。也就是说，一旦系统里存在矛盾，所有命题都"可证"了——包括"1 = 2"和它的否定。系统不是变得"部分错误"，而是整体失效。

验证一致性的标准方法是构造一个模型——一个使所有公理为真的解释。命题逻辑是一致的，因为它的公理在真值表下都是重言式，而推断规则保持重言式的性质，所以系统不可能推出矛盾。

但对于更强的系统——比如皮亚诺算术——构造模型变得困难，依赖这类方法来保证一致性也变得靠不住。原因就在第二个定理里，稍后揭晓。

---

15.2 完备性：系统不遗漏

完备性说的是：凡是语义上成立的，句法上都可以证明。

更精确地，若 $\models A$（$A$ 是重言式，在所有解释下为真），则 $\mathcal{F}⊢A$（$A$ 在系统 $\mathcal{F}$ 中有形式证明）。

哥德尔 1930 年证明了一阶谓词逻辑满足这个性质。这是一个令人振奋的结果：一阶逻辑的推断规则恰好是"正确的"，没有遗漏任何语义上应该成立的推断。

完备性定理的意义

这个定理说的是：我们写下的那些推断规则——假言推理、全称例化、存在引入……——恰好捕捉了所有语义上有效的推断，一条不多，一条不少。这不是设计的结果，而是一个需要证明的非平凡事实。如果完备性不成立，意味着有些"显然成立"的推断被规则体系遗漏了，需要补充新的推断规则——而哥德尔告诉你：不需要。

这是哥德尔带来的最后一个好消息。

兔狲教授评

"最后一个好消息"——这句话值得停一下。1930年的完备性定理和1931年的不完备定理，是同一个人在相邻两年里带来的，方向完全相反。一阶逻辑完备，足够强的算术系统不完备。边界就在这里，非常精确，不是模糊的悲观主义。

一年之后，他带来的是完全不同的东西。问题出在"足够强"这三个字上。一旦系统强大到能够表达算术——自然数、加法、乘法——完备性就永久地失去了。

---

15.3 哥德尔的两个定理

1931年，哥德尔发表了《论〈数学原理〉及相关系统的形式不可判定命题》。文章开头直接给出了结论，毫无铺垫：

定理一（第一不完备定理）：任何足够强的一致形式系统，都包含既无法被证明也无法被反驳的命题。

定理二（第二不完备定理）：任何足够强的一致形式系统，都无法在自身内部证明自身的一致性。

这两个定理的"足够强"是一个技术条件：系统能表达初等算术。皮亚诺算术满足，ZFC 集合论满足，几乎所有实际数学使用的系统都满足。

让我们追踪哥德尔是怎么做到的。

---

15.4 哥德尔编号：让系统看见自己

哥德尔的关键洞察可以用一句话说完：语法也是数学对象。

形式系统里的符号、公式、证明，全都是有限的字符串。有限字符串可以被编码为自然数——给每个符号分配一个数字，把公式编码为这些数字的某种算术组合。这个编码叫做哥德尔编号，把命题 $A$ 的编号记作 $⌜A⌝$。

一旦语法被编码为自然数，"这个命题在系统里可证"这件事，就变成了一个关于自然数的算术陈述。而皮亚诺算术恰好能表达关于自然数的陈述。于是系统获得了一种奇特的能力：它可以谈论自己。

编码是否是一种作弊？

这是一个合理的怀疑。哥德尔编号是否只是一种技巧性的把戏，实质上没有意义？不。编码的关键不是编号本身，而是：关于"哪些符号串是合法证明"的问题，可以用算术谓词表达——这是可以验证的数学事实，不依赖于编号的具体方式。换言之，任何足够强的算术系统，都能用自己的语言谈论"可证性"这件事，而不仅仅是谈论数字。哥德尔只是把这个可能性利用到了极致。

这就是自指的入口。

---

15.5 哥德尔句：说"我不可证"的命题

利用哥德尔编号，可以在系统内部表达一个谓词 $\mathsf{Prov}(n)$，含义是"编号为 $n$ 的命题在这个系统里可证"。这个谓词本身是一个算术命题，完全合法。

现在的任务是：构造一个命题 $G$，使它在逻辑上等价于 $\mathrm{\neg }\mathsf{Prov}(⌜G⌝)$，也就是"我自己在这个系统里不可证"。

这看起来像循环定义——$G$ 的内容涉及 $G$ 自身的编号，而 $G$ 的编号取决于 $G$ 是什么。怎么可能先写出 $G$，再谈论 $G$ 的编号？

对角化引理解决的正是这个结。

先考虑一个一元谓词 $P(x)$，其中 $x$ 是一个自然数（也就是某个命题的哥德尔编号）。我们想找到一个命题 $A$，使得 $A$ 等价于 $P(⌜A⌝)$——也就是说，$A$ 在谈论"命题 $A$ 自身满足性质 $P$"。

构造分两步。

第一步：引入替换函数。 定义一个算术函数 $\mathsf{sub}(m,n)$，表示"把编号为 $m$ 的公式里的自由变量替换为数字 $n$ 后，所得公式的哥德尔编号"。这是一个纯算术操作——输入两个数，输出一个数——皮亚诺算术完全能表达它。

第二步：写出自指公式。 取谓词 $P(x)$，考虑下面这个含自由变量 $y$ 的公式：

$$D(y)\equiv P(\mathsf{sub}(y,y))$$

$D(y)$ 说的是："把编号为 $y$ 的公式里的自由变量替换为 $y$ 本身后，所得命题满足 $P$。"

现在计算 $D$ 自身的哥德尔编号，记作 $d=⌜D⌝$。把 $d$ 代入 $D(y)$，得到命题：

$$A\equiv D(d)\equiv P(\mathsf{sub}(d,d))$$

关键观察：$\mathsf{sub}(d,d)$ 是"把 $D(y)$ 里的自由变量替换为 $d$ 后所得公式的编号"——而那个公式正是 $D(d)$，也就是 $A$ 本身。所以 $\mathsf{sub}(d,d)=⌜A⌝$，于是：

$$A\equiv P(⌜A⌝)$$

$A$ 在谈论自己是否满足性质 $P$，没有循环，没有预设 $A$ 的编号——编号是通过 $\mathsf{sub}$ 函数在构造过程中自然产生的。

把 $P(x)$ 取为 $\mathrm{\neg }\mathsf{Prov}(x)$，所得的 $A$ 就是哥德尔句 $G$：

$$G\equiv \mathrm{\neg }\mathsf{Prov}(⌜G⌝)$$

$G$ 的意思是："编号为 $⌜G⌝$ 的命题——也就是我自己——在这个系统里不可证。"

$G$ 不是比喻，不是哲学表态，而是皮亚诺算术里一个明确写出的算术命题，其内容恰好描述了它自身的可证状态。

现在来看 $G$ 的命运。分两种情况讨论：

若 $G$ 可证：则 $\mathsf{Prov}(⌜G⌝)$ 为真，即 $\mathrm{\neg }G$ 为真，即系统同时证明了 $G$ 和 $\mathrm{\neg }G$。系统不一致。

若 $G$ 不可证：则 $\mathrm{\neg }\mathsf{Prov}(⌜G⌝)$ 为真，即 $G$ 本身为真——它确实在系统里不可证，正如它自己所说。但系统无法证明这件事。

所以，在系统一致的前提下，$G$ 不可证。而且 $G$ 实际上是真的——我们从系统外部能看出这一点，但系统内部永远触及不到它。

$\mathrm{\neg }G$ 呢？若 $\mathrm{\neg }G$ 可证，则系统声称 $G$ 可证，但我们已经知道 $G$ 不可证——系统在对自己的可证性撒谎，这同样破坏了一致性。

结论：在一致的系统里，$G$ 既不可证，也不可反驳。它是一个不可判定的命题——真实的，但超出了系统的推理射程。

"从系统外部看出"是什么意思？

这是整个论证里最微妙的一步。我们说"$G$ 实际上是真的"，依据的是在元层次上的推理：我们在系统之外论证了系统是一致的，从而得出 $G$ 不可证，从而得出 $G$ 为真。但这个元层次的论证，本身也是在某个更强的系统里进行的。哥德尔没有找到"绝对的真"，他只是证明了：对于任何足够强的系统，总存在需要爬出这个系统才能看见的真理。层次是真实的，而且没有顶端。

---

15.6 第二定理：系统无法为自己担保

第二不完备定理是第一个定理的一个推论，但它的冲击力不亚于第一个。

把"系统 $\mathcal{F}$ 是一致的"这件事，用哥德尔编号编码为一个算术命题，记作 $\mathsf{Con}(\mathcal{F})$。

第一定理的证明过程本身可以在系统内部被形式化——因为证明过程是有限的符号操作，而系统能表达算术。形式化之后，得到：

$$\mathcal{F}⊢\mathsf{Con}(\mathcal{F})\to \mathrm{\neg }\mathsf{Prov}(⌜G⌝)$$

也就是说，系统自己能证明："如果我是一致的，那么 $G$ 不可证。"

现在假设系统还能证明自身一致，即 $\mathcal{F}⊢\mathsf{Con}(\mathcal{F})$。把这两件事用假言推理组合起来，系统就能证明 $G$ 不可证——但 $G$ 不可证等价于 $G$ 本身，于是系统证明了 $G$，与第一定理矛盾。

因此，系统不可能证明自身的一致性。

这不是谦虚，也不是能力不足。这是逻辑的结构性事实：你无法用一把尺子测量这把尺子本身是否准确。任何关于系统一致性的证明，都必须来自一个更强的外部系统，而那个更强系统的一致性又是一个悬而未决的问题——这个层级没有顶端。

兔狲教授评

真正震撼的是第二定理说的不是"很难"，而是"原则上不可能"——不是工程问题，是逻辑结构问题。一个系统对自身一致性的证明，永远需要一个更强的外部系统背书。没有顶端。这才是重点，不是那把尺子的比喻。

那我们怎么相信 ZFC 是一致的？

实话实说：我们不能证明。数学界接受 ZFC 的理由是：它用了将近一百年，产生了大量相互一致的结果，没有出现矛盾。这是归纳推理，不是演绎证明。哥德尔第二定理告诉我们，这也是我们能做到的最好程度。数学的地基不是一块被证明无误的磐石，而是一个被反复压测、至今未裂的支撑结构。这个区别，比大多数数学课承认的要重要。

---

15.7 Hilbert 纲领的终结与遗产

Hilbert 的目标是建立一个完备、一致、可判定的数学基础。两个不完备定理说明了：

• 完备性：在足够强的一致系统里，不可能实现。
• 一致性的自我保证：不可能在系统内部完成。
• 可判定性：图灵 1936 年证明了不可能，这是第19章的故事。

三项目标，全军覆没。

但 Hilbert 不是失败者

Hilbert 纲领的失败是科学史上最有价值的失败之一。正是因为他把目标定得足够精确，哥德尔和图灵才能精确地证明那些目标不可达。如果 Hilbert 说的是"数学应该有个好的基础"，就没有什么可以反驳，也没有什么可以学习。精确的问题，才能得到精确的否定答案——而精确的否定答案，比模糊的肯定答案更有价值。

但这不是悲剧的终点，而是一个更清醒认识的起点。Hilbert 纲领的失败没有让数学崩溃，而是让数学家更精确地知道了边界在哪里。边界之内，形式系统依然是人类历史上最可靠的知识建构工具。边界之外，是永久的开放问题——有些命题的真假，永远取决于你选择接受哪些公理。

这种清醒，比盲目的乐观更有价值。

---

15.8 实战：算术被形式化是什么感觉

本章一直在说"足够强的系统"——强到能表达算术。这不是抽象的描述。皮亚诺算术（PA）是这样一个系统，它有五条关于自然数的公理。在进入"悬而未决"之前，先花几分钟真实接触它。

皮亚诺公理（非形式版本）：

1. $0$ 是自然数。
2. 每个自然数 $n$ 都有唯一的后继 $S(n)$，也是自然数。
3. $0$ 不是任何自然数的后继（即不存在 $n$ 使得 $S(n)=0$）。
4. 不同的自然数有不同的后继：若 $S(m)=S(n)$，则 $m=n$。
5. 数学归纳原理：若某个性质对 $0$ 成立，且对任意 $n$ 成立时对 $S(n)$ 也成立，则它对所有自然数成立。

在这五条公理里，加法可以被定义出来：

$$m+0=mm+S(n)=S(m+n)$$

这不是约定，是定义——加法的全部行为由这两条递归方程决定。

---

练习：用这个定义，推出 $1+1=2$。

首先约定符号：$1=S(0)$，$2=S(S(0))$。

$$1+1=S(0)+S(0)=S(S(0)+0)=S(S(0))=2$$

每一步用了哪条定义？第一步是展开符号，第二步用了加法的第二条定义（$m+S(n)=S(m+n)$，其中 $m=S(0),n=0$），第三步用了加法的第一条定义（$m+0=m$），第四步是展开符号。

这就是 $1+1=2$ 的形式证明。它不依赖任何直觉，只依赖两个递归方程和皮亚诺公理。

---

现在感受一下这个系统"足够强"是什么意思：它能表达所有关于自然数的初等陈述——"存在无穷多个质数"、"每个偶数是两个质数之和（哥德巴赫猜想）"、甚至"这个系统本身是否一致"——都可以在 PA 的语言里被写成公式。正是这种表达能力，让哥德尔的对角化引理得以发挥。一个系统能谈论自己，是因为它能谈论所有足够复杂的数论陈述——而关于自身的陈述，是数论陈述的一个特例。

---

悬而未决

$G$ 是"真"的，但在哪个意义上？ 我们从系统外部看出 $G$ 为真，但这个"外部"依赖一个更强的系统，而那个系统有自己的 $G$。"真"是一个绝对的概念，还是总是相对于某个系统？

不完备性与停机问题是同一件事吗？ 哥德尔和图灵都通过自指构造建立了边界，两者在结构上高度相似。递归函数论给出了部分答案——它们确实是同一枚硬币的两面——但这个故事的全貌在第19章才会展开。

能否逃出不完备性？ 把 $G$ 加入公理得到更强的系统，但新系统有自己的哥德尔句。把那个也加进去，如此往复。这个超限层级有没有极限？答案是肯定的，但极限本身是什么，是现代集合论的前沿问题。

不完备性是由哪条结构规则造成的？ 第14章列出了三条在后台默默运行的结构规则：弱化、收缩、交换。哥德尔定理的存在，根植于系统足够强——而"足够强"依赖于假设可以被任意重复使用。如果我们质疑这一点——如果每个假设只能用一次——推理会变成什么？这是第16章的起点。

---

思考题

★ 热身

对角化引理的核心是替换函数 $\mathsf{sub}(m,n)$。对以下描述判断正误：

1. $\mathsf{sub}(m,n)$ 的输入是两个自然数，输出也是一个自然数。（对/错？）
2. $\mathsf{sub}(⌜D⌝,⌜D⌝)$ 的结果，是把公式 $D$ 里的自由变量替换为公式 $D$ 本身之后的哥德尔编号。（对/错？）
3. 哥德尔编号的具体方式（比如用质数幂乘积还是别的编码）会影响第一不完备定理的结论。（对/错？）

（这三道题的目的是确认：哥德尔编号是算术操作，不依赖编码方式的选择。）

---

★★ 推导

把哥德尔句 $G$（"我在系统 $\mathcal{F}$ 中不可证"）作为新公理加入 $\mathcal{F}$，得到 ${\mathcal{F}}^{\prime }=\mathcal{F}+\{G\}$。

1. ${\mathcal{F}}^{\prime }$ 还是一致的吗？（提示：$G$ 在 $\mathcal{F}$ 中不可证意味着什么？把 $G$ 加进去会和 $\mathcal{F}$ 的其他定理矛盾吗？）
2. ${\mathcal{F}}^{\prime }$ 有自己的哥德尔句 $G^{\prime }$ 吗？$G^{\prime }$ 和 $G$ 是同一个命题吗？为什么不是？
3. 这个过程可以无限重复。把所有这样的哥德尔句全部加入，得到的极限系统是否完备？试着用自然语言解释为什么答案是否定的——完备性逃不掉。

---

★★★ 挑战

第二不完备定理说：$\mathcal{F}$ 无法在自身内部证明 $\mathsf{Con}(\mathcal{F})$。但我们（在更强的外部系统里）确实可以论证 $\mathcal{F}$ 是一致的——比如，通过构造一个使所有 $\mathcal{F}$ 的公理为真的模型。

试着用本章的语言写出：这个"外部论证"本身依赖什么？它用了哪个更强系统的一致性？这个更强系统的一致性，又依赖什么？

这个问题没有终点，但试着把无穷退回的结构写清楚——用 $\mathcal{F}$、${\mathcal{F}}_1$、${\mathcal{F}}_2$……的符号链条表示。这个链条的存在，对"数学有没有最终的基础"这个问题意味着什么？

不需要解决这些问题——只需要想清楚为什么每个问题都比看起来的更难。