第9章哥德尔第一不完全性定理 第1节可表示性 根据一阶逻辑,我们只要证 ∧a(m,列)+r(mn,…,孙,fm) 根据(91)的唯一性方向,我们有 ∧a(m,)+∧(≈h(m) 再在(92)中,将n1用h(m)替代,即可得到我们所要证的。 再看从左向右的方向,我们要证:}rⅤz(φ(m,x)→z≈fm)。仍根据一阶逻辑,我 们只要证 …r∧a(n,)→v(m,…,,2)+r2≈f(m) i=1 根据(9.1)的从右向左方向,我们有r∧=1B(m,h(m);再根据假设,就得到y(m,z)hr u(h1(m),…,h-(m),z)。再根据(92)中唯一性的方向,我们有 y(m,x)+rz≈g(h1(m),…,hr(m) 因此,y(m,z)+rz≈fm) 注 ·我们在证明中给出的公式φ是I1-的(假定其它给定的公式都是△1-的)。我们也可 以用一个∑1-公式(x,2)来表示f 彐u彐 ∧a(x,m)A 这对关心复杂性的读者也许是有用的。 我们给出详细证明的目的之一是说明引进“作为函数表示”这一概念的必要性。注 意在上面的证明中,即使是较为简单的从右向左方向,也用到了唯一性。更进一步, 我们可以举出具体反例说明仅用关系的可表示性是不够的(习题)。 我们下面处理正则极小算子。先证明一个有用的引理 引理95.令公式a(,y)表示(k+1元关系PN中。并假定9abP(a 定义公式p(,y)为a(,y)A(z<y)-a(x,2)。则公式y(,y)(作为函数)表示函 数f:d+pb{P(a,b)第 9 章 哥德尔第一不完全性定理 第 1 节 可表示性 根据一阶逻辑，我们只要证 ∧r i=1 θi(m⃗ , yi) ⊢T ψ(y1, · · · , yr, f(m⃗ ))。 根据 (9.1) 的唯一性方向，我们有 ∧r i=1 θi(m⃗ , yi) ⊢T ∧r i=1 (yi ≈ hi(m⃗ )), 再在 (9.2) 中，将 ni 用 hi(m⃗ ) 替代，即可得到我们所要证的。 再看从左向右的方向，我们要证：⊢T ∀z(φ(m⃗ , z) → z ≈ f(m⃗ ))。仍根据一阶逻辑，我 们只要证 ∀y1 · · · ∀yr[(∧r i=1 θi(m⃗ , yi)) → ψ(y1, · · · , yr, z)] ⊢T z ≈ f(m⃗ )。 根据 (9.1) 的从右向左方向，我们有 ⊢T ∧r i=1 θi(m⃗ , hi(m⃗ ))；再根据假设，就得到 φ(m⃗ , z) ⊢T ψ(h1(m⃗ ), · · · , hr(m⃗ ), z)。再根据 (9.2) 中唯一性的方向，我们有 φ(m⃗ , z) ⊢T z ≈ g(h1(m⃗ ), · · · , hr(m⃗ ))。 因此，φ(m⃗ , z) ⊢T z ≈ f(m⃗ )。 注： • 我们在证明中给出的公式 φ 是 Π1-的（假定其它给定的公式都是 ∆1- 的）。我们也可 以用一个 Σ1-公式 ϕ(⃗x, z) 来表示 f: ∃y1∃y2 · · · ∃yr[(∧r i=1 θi(⃗x, yi)) ∧ ψ(y1, · · · , yr, z)]。 这对关心复杂性的读者也许是有用的。 • 我们给出详细证明的目的之一是说明引进“作为函数表示”这一概念的必要性。注 意在上面的证明中，即使是较为简单的从右向左方向，也用到了唯一性。更进一步， 我们可以举出具体反例说明仅用关系的可表示性是不够的（习题）。 我们下面处理正则极小算子。先证明一个有用的引理： 引理 9.5. 令公式 α(⃗x, y) 表示 (k + 1)-元关系 P ⊆ N k+1。并假定 N |= ∀⃗a∃b P(⃗a, b)。 定义公式 φ(⃗x, y) 为 α(⃗x, y) ∧ (∀z < y)¬α(⃗x, z)。则公式 φ(⃗x, y) （作为函数）表示函 数 f : ⃗a 7→ µb[P(⃗a, b)]。 7