第3节不动点引理和递归定理 第9章哥德尔第一不完全性定理 (19)令T同前。定义谓词bewr(,a)为“b是一个T上的一个证明序列且ho-1=a 则bewr(b,a)是递归的。(“ Beweis”是“证明”的德语。) (20)令T同前。定义谓词bwbr(a)为彐bewr(b,a)。则bwbr(a)是递归可枚举的。在 般情况下是不递归的。(“ Beweisbar”是“可证”的德语。) bewr(b,a)说的是“b是一个T上对公式a的一个证明”,而bwbr(a)说的是“公式a在T中 是可证的”。由于我们后面经常会用到它们,我们特别引入这两个新的记号 第3节不动点引理和递归定理 93.1不动点引理 引理911(不动点引理).给定一个公式β(1)其中只有变元n1自由出现,我们可以能行的 找到一个闭语句σ使得 Q+a4B(S0)。 直观上看,σ说的是“B对我成立”。人们经常使用「σ来表示Car中的项S=0,即, σ的数码。从而不动点引理的结论可以表达得更有暗示性:Q卜σ←β(σ 证明:令(1,2,t3)表示递归函数 (a,n)+#a(n) 的一个公式,其中a为一个仅含一个自由变元的公式。所以 Q VU3 [e(a7, n, 03)+>03 N a(n) [注意:这是我们使用可表示性以及句法算术化的地方 考察公式r(v1): r(v1):=t3(v1,t1,t3)→B(v3) 令q为公式r(v1)的哥德尔编码。再令闭语句a为 t(6(q,q,3)→6(v3) 注意a是在公式r(1)中将唯一的变元n用r(1)自己的哥德尔编码q代入而得到的。 我们验证 Q+a分B(a) (9.5)
第 3 节 不动点引理和递归定理 第 9 章 哥德尔第一不完全性定理 (19) 令 T 同前。定义谓词 bewT (b, a) 为“b 是一个 T 上的一个证明序列 且 blh(b)−1 = a”。 则 bewT (b, a) 是递归的。（“Beweis”是“证明”的德语。） (20) 令 T 同前。定义谓词 bwbT (a) 为 ∃b bewT (b, a)。则 bwbT (a) 是递归可枚举的。在一 般情况下是不递归的。（“Beweisbar”是“可证”的德语。） bewT (b, a) 说的是“b 是一个 T 上对公式a的一个证明”，而bwbT (a) 说的是“公式a在 T 中 是 可证的”。由于我们后面经常会用到它们，我们特别引入这两个新的记号。 第 3 节 不动点引理和递归定理 9.3.1 不动点引理 引理 9.11 (不动点引理). 给定一个公式 β(v1) 其中只有变元 v1 自由出现，我们可以能行的 找到一个闭语句 σ 使得： Q ⊢ σ ↔ β(S ♯σ0)。 直观上看，σ 说的是“β 对我成立”。人们经常使用 pσq 来表示 Lar 中的项 S ♯σ0，即， ♯σ 的数码。从而不动点引理的结论可以表达得更有暗示性：Q ⊢ σ ↔ β(pσq)。 证明: 令 θ(v1, v2, v3) 表示递归函数 ⟨♯α, n⟩ 7→ ♯ α(n) 的一个公式，其中 α 为一个仅含一个自由变元的公式。所以 Q ⊢ ∀v3 [θ(pαq, n, v3) ↔ v3 ≈ pα(n)q] (9.3) [注意：这是我们使用可表示性以及句法算术化的地方。] 考察公式 τ (v1)： τ (v1) := ∀v3 [θ(v1, v1, v3) → β(v3)]。 令 q 为公式 τ (v1) 的哥德尔编码。再令闭语句 σ 为 σ := ∀v3(θ(q, q, v3) → β(v3))。 (9.4) 注意 σ 是在公式 τ (v1) 中将唯一的变元 v1 用 τ (v1) 自己的哥德尔编码 q 代入而得到的。 我们验证 Q ⊢ σ ↔ β(pσq)。 (9.5) 16
第9章哥德尔第一不完全性定理 第3节不动点引理和递归定理 根据θ的选择,如果我们在(93)式中将a和n分别用r和q=t代入,我们就得到 Q+vva(q,q,t3)+t3≈「a]。 (96) 先看(9.5)式中从左向右“→”的方向:由(94)式,我们有a}(q,q,a)→B(a) 根据(96),Q}θ(q,q,「a)。所以QU{o}+B(a) 再看(9.5)式中从右向左“←”的方向:根据(96),B(a)→[a((q,q,ta)→B(v3) 原因是只有唯一的那样的υ3,也就是「σ。而方括号中的公式恰恰是σ,我们就得到了 (9.5)式。 注意:尽管我们把不动点引理写得富有暗示性,但不动点σ本身可能“什么都没说” 或者与B毫无关系。例如,令β(v1)为丑x(n1≈x+x)(即表达,n1是一个偶数),则由 于我们的编码保证了任何闭语句的哥德尔数都是偶数,我们可以取不动点σ为0≈0或 0≈S0等等,显然它与变元的奇偶性毫无关系。 这正是哥德尔伟大的地方。说谎者悖论“这句话为假”是真正的循环论证。我们无法 直接定义“这句话”。哥德尔巧妙地利用了哥德尔编码(即利用语法对象的同构像)打破 了这种循环。不动点定理中只是断言存在某个闭语句σ和某个数码n可以使得σβ(n) 这里面没有任何的循环。只不过碰巧,σ的同构像「σ刚好也可以被选作n。 932克林尼递归定理 在递归论中,克林尼证明了著名的递归定理: 定理97(克林尼.令0,91,…为所有部分递归函数的能行枚举(见通用函数定理)。对 任何的递归函数f(x)都存在一个自然数e,使得pre)=9e 递归定理也被称为不动点定理,它在递归论中有非常广泛的应用。它的证明并不长 但需要用到s-m-n-定理,所以我们略去不讲。递归定理可以看作是哥德尔不动点引理在 递归论中的版本,都与自指示有关。证明也很类似,短但充满神秘。在递归论中,为了帮 助理解,人们给岀了一些对递归定理证明的直观解释。大致上说是某种“对角化策略的失 败”。这里,我们借用递归论中的解释来看不动点引理的证明,这种解释对证明的理解和 定理的应用都不重要,我们只希望能减少一点神秘感而已。 让我们能行地列出所有只含有自由变元1公式:po(v),y1(vn),…。其次,对自 然数0,1,2,…,我们用下表的第i行记录所有Q是否证明≌(0),证明(S0),证 明φ(S30),…等等。我们用√表示Q能证明,×表示Q不能证明。例如,结果可 能是
第 9 章 哥德尔第一不完全性定理 第 3 节 不动点引理和递归定理 根据 θ 的选择，如果我们在 (9.3) 式中将 α 和 n 分别用 τ 和 q = ♯τ 代入，我们就得到 Q ⊢ ∀v3[θ(q, q, v3) ↔ v3 ≈ pσq]。 (9.6) 先看 (9.5) 式中从左向右 “⇒” 的方向：由 (9.4) 式，我们有 σ ⊢ θ(q, q, pσq) → β(pσq)。 根据 (9.6)，Q ⊢ θ(q, q, pσq)。所以 Q ∪ {σ} ⊢ β(pσq)。 再看 (9.5) 式中从右向左 “⇐” 的方向：根据 (9.6)，β(pσq) → [∀v3(θ(q, q, v3) → β(v3))]， 原因是只有唯一的那样的 v3，也就是 pσq。而方括号中的公式恰恰是 σ，我们就得到了 (9.5) 式。 注意：尽管我们把不动点引理写得富有暗示性，但不动点 σ 本身可能“什么都没说”， 或者与 β 毫无关系。例如，令 β(v1) 为 ∃x(v1 ≈ x + x) （即表达，v1 是一个偶数），则由 于我们的编码保证了任何闭语句的哥德尔数都是偶数，我们可以取不动点 σ 为 0 ≈ 0 或 0 ̸≈ S0 等等，显然它与变元的奇偶性毫无关系。 这正是哥德尔伟大的地方。说谎者悖论“这句话为假”是真正的循环论证。我们无法 直接定义“这句话”。哥德尔巧妙地利用了哥德尔编码（即利用语法对象的同构像）打破 了这种循环。不动点定理中只是断言存在某个闭语句 σ 和某个数码 n 可以使得 σ ↔ β(n)。 这里面没有任何的循环。只不过碰巧，σ 的同构像 pσq 刚好也可以被选作 n。 9.3.2 克林尼递归定理 在递归论中，克林尼证明了著名的递归定理： 定理 9.7 (克林尼). 令 φ0, φ1, · · · 为所有部分递归函数的能行枚举（见通用函数定理）。对 任何的递归函数 f(x) 都存在一个自然数 e，使得 φf(e) = φe。 递归定理也被称为不动点定理，它在递归论中有非常广泛的应用。它的证明并不长， 但需要用到 s-m-n-定理，所以我们略去不讲。递归定理可以看作是哥德尔不动点引理在 递归论中的版本，都与自指示有关。证明也很类似，短但充满神秘。在递归论中，为了帮 助理解，人们给出了一些对递归定理证明的直观解释。大致上说是某种“对角化策略的失 败”。这里，我们借用递归论中的解释来看不动点引理的证明，这种解释对证明的理解和 定理的应用都不重要，我们只希望能减少一点神秘感而已。 让我们能行地列出所有只含有自由变元 v1 公式：φ0(v1), φ1(v1), · · · 。其次，对自 然数 0, 1, 2, · · · ，我们用下表的第 i 行记录所有 Q 是否证明 φi(0)，证明 φi(S0)，证 明 φi(S 2 0)，……等等。我们用 √ 表示 Q 能证明，× 表示 Q 不能证明。例如，结果可 能是： 17