第9章哥德尔第一不完全性定理 第1节可表示性 ∈叽。由于t是卯的尾节扩张,任何a<卾都是属于9的,所以根据归纳假定 9=(a)。所以9σ 同理,9Fσ也蕴涵9}σ,这就验证了断 注意:断言实际上是“△-完全性”的模型论表述。换句话说,断言告诉我们,对任 何△-闭语句a,9}σ当且仅当Qσ。现在假定9卜σ(),其中σ为一个△0公 式。则对某个d∈,我们有9卜σ(a)。根据断言,Q}θ(a。所以Q丑σ(。口 下面的引理告诉我们如何处理约束量词。该引理我们以后会常常用到 引理93.如果关系P三N+被公式p(x,y)所表示,则关系(c<b)P(a,c)和(vc< b)P(d,c)分别被(z<y)p(x,2)和(vz<y)p(,z)所表示 证明:习题。 913函数的可表示性 我们的目标是证明每个递归的关系都是可表示的(从而递归关系就是可表示关系) 由于递归关系是用递归函数来定义的,为此我们自然地想借助递归函数来达到我们的目 标。为此,我们引入一个函数的可表示性概念。 定义92.我们称一个函数f:N→N为在T中可表示的,如果存在一个公式φ(x1,…,xk,y)使 得对所有的(n1,…,nk)∈Ⅳ,我们有 ry{y(n1,……,nk,y)y=fn1,…,nk 在此情形下,我们也称φ作为一个函数表示f 我们常常把一个函数f(x)与它的图像Gr={(x,y):r=f()}等同起来(为简化讨 论,我们假定k=1)。那么公式φ表示Gr(作为一个二元关系)与公式表示f(作 为一个一元函数)有什么不同吗?首先,如果f(n)=m,则(m,m)∈Gr,我们作为关系 要求+rφ(n,m),而作为函数也要求(从右向左方向,当y=f(n)时)+ry(n,m),这 点双方是一样的。如果y≠f(m)时,作为关系表示Gr的y仅仅能逐点地验证对每 个m≠f(n)的标准自然数m,+r-p(n,m),而对作为函数表示∫的φ,我们要求的更 多,我们要求它能有个相容的对I1语句的证明:+rwy≠fn)→-(n,y)。如同前面 引理9.1所告诉我们的,后者要强得多 我们举一个具体的例子:令T=Q。对于零函数Z(x)=0的图像Gz={(x,0):x∈ N}来说,它被公式y(x,y):=y+y≈y作为一个关系表示(练习);但由于Q不能证 明vy(y+y≈y→y≈0)(练习),所以,φ(x,y)并不作为一个函数表示零函数。第 9 章 哥德尔第一不完全性定理 第 1 节 可表示性 t N ∈ N。由于 M 是 N 的尾节扩张，任何 a ≤M t M 都是属于 N 的，所以根据归纳假定， M |= θ(a)。所以 M |= σ。 同理，M |= σ 也蕴涵 N |= σ，这就验证了断言。 注意：断言实际上是“∆0-完全性”的模型论表述。换句话说，断言告诉我们，对任 何 ∆0-闭语句 σ，N |= σ 当且仅当 Q ⊢ σ。现在假定 N |= ∃⃗x σ(⃗x)，其中 σ 为一个 ∆0 公 式。则对某个 ⃗a ∈ Nk，我们有 N |= σ(⃗a)。根据断言，Q ⊢ θ(⃗a)。所以 Q ⊢ ∃⃗x σ(⃗x)。 下面的引理告诉我们如何处理约束量词。该引理我们以后会常常用到。 引理 9.3. 如果关系 P ⊆ N k+1 被公式 ρ(⃗x, y) 所表示，则关系 (∃c < b)P(⃗a, c) 和 (∀c < b)P(⃗a, c) 分别被 (∃z < y)ρ(⃗x, z) 和 (∀z < y)ρ(⃗x, z) 所表示。 证明: 习题。 9.1.3 函数的可表示性 我们的目标是证明每个递归的关系都是可表示的（从而递归关系就是可表示关系）。 由于递归关系是用递归函数来定义的，为此我们自然地想借助递归函数来达到我们的目 标。为此，我们引入一个函数的可表示性概念。 定义9.2. 我们称一个函数 f : N k → N 为在 T 中可表示的，如果存在一个公式φ(x1, · · · , xk, y) 使 得对所有的 (n1, · · · , nk) ∈ N k，我们有 ⊢T ∀y[φ(n1, · · · , nk, y) ↔ y = f(n1, · · · , nk)]。 在此情形下，我们也称 φ 作为一个函数表示 f。 我们常常把一个函数 f(x) 与它的图像 Gf = {(x, y) : x = f(y)} 等同起来（为简化讨 论，我们假定 k = 1）。那么公式 φ 表示 Gf（作为一个二元关系）与公式 φ 表示 f（作 为一个一元函数）有什么不同吗？首先，如果 f(n) = m，则 (n, m) ∈ Gf，我们作为关系 要求 ⊢T φ(n, m)，而作为函数也要求（从右向左方向，当 y = f(n) 时） ⊢T φ(n, m)，这 一点双方是一样的。如果 y ̸= f(n) 时，作为关系表示 Gf 的 φ 仅仅能逐点地验证对每 个 m ̸= f(n) 的标准自然数 m，⊢T ¬φ(n, m)，而对作为函数表示 f 的 φ ，我们要求的更 多，我们要求它能有个相容的对 Π1 语句的证明：⊢T ∀y[y ̸= f(n) → ¬φ(n, y)]。如同前面 引理 9.1 所告诉我们的，后者要强得多。 我们举一个具体的例子：令 T = Q。对于零函数 Z(x) = 0 的图像 GZ = {(x, 0) : x ∈ N} 来说，它被公式 φ(x, y) :=df y + y ≈ y 作为一个关系表示（练习）；但由于 Q 不能证 明 ∀y(y + y ≈ y → y ≈ 0) （练习），所以，φ(x, y) 并不作为一个函数表示零函数。 5