On Gödel’s Theorems on Lengths of Proofs I

by Samuel R. Buss

Theorem 3 (Strengthened Gödel's Speed-up)

Let i ≥ 0. Then there is an infinite family F of Π⁰₁-formulas such that:

(1) for all φ ∈ F, Z_i ⊢ φ, and
(2) there is a fixed k ∈ ℕ such that for all φ ∈ F, Z_i+1 ⊢_{k steps} φ, and
(3) there is no fixed k ∈ Z_i such that for all φ ∈ F, Z_i ⊢_{k steps} φ.

Proof

Let i ≥ 0. Let φ(x) be the formula obtained by Gödel diagonalization such that Z₀ proves:

φ (x) \leftrightarrow \neg Z_{i} ⊢_{x steps} φ (x)

这就像一句神奇的咒语：“这句咒语，你无法在念出它的字数那么多的步数内将它写下来。”

符号详解

φ(x)
- 名称： 哥德尔语句（Gödel Sentence）。
- 物理意义： 这不是一个描述物理世界的公式，而是一个“元数学”的构造，一个可以谈论自身的数学命题。它像一面镜子，照见的正是它自己被证明的过程。
- 在本公式中的作用： 这是我们整个证明的核心“演员”。它被精确地构造出来，其真假与它自身是否能被“有限步骤地证明”直接挂钩。x 是一个变量，代表一个具体的数字，比如5、100等等。
↔
- 名称： 逻辑等价（Logical Equivalence）。
- 物理意义： 想象一个天平，这个符号就是天平的支点，表示两边的“逻辑重量”完全相等。一边为真，另一边必然为真；一边为假，另一边也必然为假。
- 在本公式中的作用： 它声明了左边的命题 φ(x) 和右边的命题 ¬(Zᵢ ⊢ₓ steps φ(x)) 是完全一回事。
¬
- 名称： 否定（Negation）。
- 物理意义： 这是一个“反转”开关。如果一个陈述是真的，加上它就变成假的；反之亦然。
- 在本公式中的作用： 它把“可以被证明”这件事，变成了“不可以被证明”。
Zᵢ
- 名称： i阶算术系统（i-th Order Arithmetic）。
- 物理意义： 把它想象成一个有严格规则的“数学推理机器人”。Z₀ (i=0) 是一阶算术，像一个非常严谨、只懂基础加减乘除和逻辑的机器人。Z₁ (i=1) 是二阶算术，是 Z₀ 的升级版，能力更强，能理解更复杂的概念（比如“所有数字的集合”）。
- 在本公式中的作用： 这是我们进行证明的“舞台”或“规则体系”。我们正在讨论的是，在这个名为 Zᵢ 的规则体系内，能不能证明 φ(x)。
⊢ₓ steps
- 名称： 在x步内证明（Provable within x steps）。
- 物理意义： ⊢ 符号代表“证明”。它像一个法官的木槌，敲下去就表示“结论成立”。下标的 x steps 给这个证明加上了一个资源限制——你必须在不超过 x 步的推导内完成。
- 在本公式中的作用： 这是对证明能力的量化。整个右半部分 Zᵢ ⊢ₓ steps φ(x) 的意思就是：“在 Zᵢ 这个体系里，存在一个长度不超过 x 步的证明，其结论是 φ(x)。”

Let F = {φ(n) : n ≥ 0}. We must show three facts:

(1) For all n ≥ 0, it is not the case that Z_i ⊢_n φ(n).

This is immediate from the consistency of Z_i, since, if Z_i ⊢_n φ(n), then Z_i proves this fact and thus Z_i ⊢ ¬φ(n).

Z_{i} ⊢ φ (n)

虽然无法在有限步内证明它，但系统 Zᵢ 最终还是能（通过更曲折的、没有步数限制的思考）想明白：这个咒语是真的。

符号详解

Zᵢ ⊢ φ(n)
- 名称： Zᵢ 证明 φ(n) (Zᵢ proves φ(n))。
- 物理意义： 这表示，我们的“数学推理机器人” Zᵢ，在没有步数限制的情况下，开足马力进行推理，最终成功地推导出了 φ(n) 这个结论。
- 在本公式中的作用： 这是我们宣称的一个惊人事实。我们先来看看为什么。在 Zᵢ 体系内部，它可以进行这样的“反证”思考：
  1. “假设 φ(n) 是假的吧。”
  2. “那么根据 φ(n) 的定义，就意味着‘我能在 n 步内证明 φ(n)’。”
  3. “可如果我能证明 φ(n)，那 φ(n) 就是真的啊！”
  4. “这就矛盾了！我从‘φ(n)是假的’出发，推出了‘φ(n)是真的’。唯一的可能就是，我最初的假设错了。”
  5. “结论：φ(n) 必须是真的！”
  这个思考过程本身，就是 Zᵢ 对 φ(n) 的一个（虽然可能很长很长的）证明。

(3) There is a k ≥ 0 such that, for all n ≥ 0, Z_i+1 ⊢_{k steps} φ(n).

To establish this, it will suffice to show that Z_i+1 can prove (∀x)φ(x). The argument is like the one above; however, Z_i+1 can define a truth predicate for all formulas of the language of Z_i.

Z_{i + 1} ⊢ (\forall x) φ (x)

更高级的系统 Zᵢ₊₁ 就像一个站在山顶的观察者，它能一眼看穿山脚下 Zᵢ 的所有“小把戏”，并给出一个普遍性的结论。

符号详解

Zᵢ₊₁
- 名称： i+1阶算术系统。
- 物理意义： 这是 Zᵢ 的“超级升级版”。如果说 Zᵢ 是一个在棋盘上按规则移动的棋手，那 Zᵢ₊₁ 就是能俯瞰整个棋盘、理解“所有可能的棋局”的上帝视角玩家。它拥有更强大的“元语言”，可以直接谈论并判断 Zᵢ 体系内所有命题的真假。
- 在本公式中的作用： 它是提供“加速”的关键。它能做到 Zᵢ 做不到的事情——用一个统一、简洁的方式证明所有 φ(n)。
∀x
- 名称： 全称量词（Universal Quantifier）。
- 物理意义： 读作“对于所有的...”。它是一个强大的概括工具，能将一个对特定个体成立的陈述，推广到整个群体。
- 在本公式中的作用： (∀x)φ(x) 表示“对于所有的自然数x，命题φ(x)都成立”。Zᵢ₊₁ 不再像 Zᵢ 那样需要对每一个n（比如n=1, n=2, n=3...）都费力地进行一次反证法，而是直接通过其强大的“真理定义”能力，一举证明了对所有n都成立的普遍规律。这就像发明了乘法，而不用一遍遍地做加法。

阶段总结：办公室里的普通员工、部门经理和CEO

整个定理的证明，就像一出发生在一家大型公司里的、关于“效率与洞察力”的戏剧。

普通员工 (系统 Zᵢ)：
这位员工非常勤奋、严谨，但视野有限。他有一份工作手册（Zᵢ 的公理和规则），上面写着所有的操作规范。现在，他面对一个特殊的任务——处理一系列“自指”的备忘录 φ(n)。每一份备忘录都写着：“这份备忘录无法在n小时内完成归档”。
对于任何一份具体的备忘录（比如n=10），这位员工会陷入沉思。他尝试用“反证法”：如果我假设“这份备忘录能在10小时内归档”，那么备忘录上写的“不能在10小时内归档”就是错的。但如果备忘录是错的，我就不该相信它... 噢，等等，如果我真的能在10小时内归档它，这就证明了备忘录的内容是假的。但我的手册规定我不能归档内容为假的备忘录！这太矛盾了。唯一的结论是：我最初的假设是错的，这份备忘录“真的无法在10小时内归档”。于是，他终于明白了这份备忘录的“真相”。
但是请注意，对于n=10，他需要思考半天；对于n=100，他需要思考更久。他的证明长度（花费的时间）随着n的增大而无限增长，他永远也找不到一个“固定几小时内搞定所有备忘录”的通用方法。

部门经理 (系统 Zᵢ₊₁)：
这位经理站得更高，他不仅拥有员工的所有手册，还有一个更高级的视角：他能直接判断“一份备忘录的陈述是否真实”。他走过来，看了一眼所有这些 φ(n) 备忘录，笑了。
他没有陷入每一份备忘录的具体数字n里，而是直接抓住了问题的本质。他发表了一个全局性的声明 (证明了 (∀x)φ(x)):
“所有这些写着‘我无法在n小时内被归档’的备忘录，其陈述本身都是真实的。因为任何试图在n小时内归档它们的行为，都会导致逻辑上的自我否定。因此，我宣布，所有这些备忘录的‘真相’就是它们所说的那样。”
这个声明，他只花了5分钟就想清楚了，并且这个声明对所有n都有效。无论来多少份这种备忘录，他都用这同一个、固定的、极其简短的逻辑来处理。

大美之处：
这就是哥德尔加速定理的震撼之处。从 Zᵢ 到 Zᵢ₊₁，我们得到的不仅仅是线性的效率提升，而是无限的、不可计算的“认知飞跃”。对于同一系列真理（φ(n)），低级系统需要付出越来越大的、乃至无限的努力才能逐一认识到它们；而高级系统仅凭其更深刻的洞察力，用一个恒定、微小的代价就一览无余。这揭示了数学真理世界的层次性：总有更强大的视角，能以我们无法想象的简洁之美，看透我们当前系统里那些最复杂的难题。