第9章哥德尔第一不完全性定理 我们现在考察语言Car={0,5,+,}并且研究初等数论的标准模型9=(N,O,S,+,)。 同时具有加法和乘法的模型与前面的普莱斯伯格算术(N,0,S,+)和司寇伦的乘法模型 (N,0,×)大不相同。我们本章的目标是下列三大定理:塔尔斯基不可定义定理,哥德尔的 第一不完全性定理和丘奇的不可判定性定理 需要的主要三个步骤为:可表示性,语法的算术化和不动点引理。我们下面分别讨 论。 第1节可表示性 911罗宾逊算术Q 粗略地说,研究“可表示性”就是研究什么样的标准自然数上的关系可以用形式语言 Ca中的公式表示或表达出来。我们的目标是先确定“表示”的精确定义,然后证明所有 递归关系都是在选定的算术系统内“可表示的”。自然,算术系统越强,所能证明的命题 就越多。因此,为了获得最强烈的反差,我们选取一个非常弱的(可以说是最弱的)系统 Q,称为罗宾逊算术。其它的选择还有PA-(差不多是PA除掉归纳法)和PA;或者为 了编码的方便,也有把指数函数添到语言之中并添加适当的关于指数运算的公理;当然还 可以选择集合论的语言和ZFC公理或适当的片断。 罗宾逊算术理论Q的公理有如下7条 Q1VxSx≈0 Q2rvy(Sx≈Sy→x≈y) Q3x(x≠0→3yx≈Sy) Q4Vr(x+0≈x) Q5wnvy(x+Sy≈S(x+y) 罗宾逊, Raphael Robinson(1911-1995),美国数学家
第 9 章 哥德尔第一不完全性定理 我们现在考察语言 Lar = {0, S, +, ·} 并且研究初等数论的标准模型 N = (N, 0, S, +, ·)。 同时具有加法和乘法的模型与前面的普莱斯伯格算术 (N, 0, S, +) 和司寇伦的乘法模型 (N, 0, ×) 大不相同。我们本章的目标是下列三大定理：塔尔斯基不可定义定理，哥德尔的 第一不完全性定理和丘奇的不可判定性定理。 需要的主要三个步骤为：可表示性，语法的算术化和不动点引理。我们下面分别讨 论。 第 1 节 可表示性 9.1.1 罗宾逊算术 Q 粗略地说，研究“可表示性”就是研究什么样的标准自然数上的关系可以用形式语言 Lar 中的公式表示或表达出来。我们的目标是先确定“表示”的精确定义，然后证明所有 递归关系都是在选定的算术系统内“可表示的”。自然，算术系统越强，所能证明的命题 就越多。因此，为了获得最强烈的反差，我们选取一个非常弱的（可以说是最弱的）系统 Q，称为罗宾逊1 算术。其它的选择还有 PA− （差不多是 PA 除掉归纳法）和 PA；或者为 了编码的方便，也有把指数函数添到语言之中并添加适当的关于指数运算的公理；当然还 可以选择集合论的语言和 ZFC 公理或适当的片断。 罗宾逊算术理论 Q 的公理有如下 7 条: Q1 ∀x Sx ̸≈ 0。 Q2 ∀x∀y (Sx ≈ Sy → x ≈ y)。 Q3 ∀x (x ̸≈ 0 → ∃y x ≈ Sy)。 Q4 ∀x (x + 0 ≈ x)。 Q5 ∀x∀y (x + Sy ≈ S(x + y))。 1罗宾逊，Raphael Robinson （1911 - 1995），美国数学家。 1
第1节可表示性 第9章哥德尔第一不完全性定理 Q6Vr(x.0≈0) Q7vy(x:Sy≈x:y+x) 显然,标准自然数模型叽是Q的一个模型。但是Q还有很多其它模型 例9.1.考察结构9=(NU{o∞},0,S,+,),其中函数S、+和·为通常的后继、加法和乘 法依照如下方式扩张到新元素∞上 1)S(∞)=∞; (2)n+∞=∞+n=∞+∞=∞0(对所有的n∈N); (3)∞·0=0·∞=0并且n·∞=∞·n=∞·∞=∞(对所有的n∈N且n≠0)。 则结构9卜Q。(练习) 引理9.1.何a) QyVe Sz≠x b)对每一个标准自然数n∈N,QSnn,其中n代表S"0。 证明:根据S(∞)=∞在例9.1中的模型上成立,我们立刻得到(a) 断言(b)则是通过(外面的)对标准自然数n∈N作归纳而得到的 当n=0时,Q}S0≈0,这是根据(Q1) 假定QSn≠n。则根据(Q2)的逆否命题,我们立刻有QS(n+1)≈n+1。口 注:引理9.虽然很短,但包含的信息对本节的理解是至关重要的 ·首先它表明了标准和非标准自然数的区别。每一个标准自然数n∈N都在我们的语 言内有一个“名字”,即数码n。这个数码n是算术语言中的项S"0,它是语言内与 外面的”自然数n的对应物。而非标准数则都是“无名鼠辈”,似乎飘忽不定 ·考察断言(b)对所有n∈N,Qn≈Sn。注意这里实际上是一族证明,而不是一个 证明。当自然数n越来越大时,Q对n≈Sn的证明也越来越长。而断言(a)则不然, 它否证的是一个适用于所有数的一致的2证明 最后,请大家注意我们在“外部的”证明(如证明(b)时可以用归纳法)和系统Q 内证明(Q中显然没有归纳法)的区别。 我们再看Q的一些其它的简单事实。在本节中,我们用“”来表达“QH”;并且将 x≤y定义成彐(x+z≈y) 这里的一致指的是数学中常用的一致性,即 uniformity,与无矛盾性无关
第 1 节 可表示性 第 9 章 哥德尔第一不完全性定理 Q6 ∀x (x · 0 ≈ 0)。 Q7 ∀x∀y (x · Sy ≈ x · y + x)。 显然，标准自然数模型 N 是 Q 的一个模型。但是 Q 还有很多其它模型。 例 9.1. 考察结构 M = (N ∪ {∞}, 0, S, +, ·)，其中函数 S、+ 和 · 为通常的后继、加法和乘 法依照如下方式扩张到新元素 ∞ 上： (1) S(∞) = ∞； (2) n + ∞ = ∞ + n = ∞ + ∞ = ∞（对所有的 n ∈ N）； (3) ∞ · 0 = 0 · ∞ = 0 并且 n · ∞ = ∞ · n = ∞ · ∞ = ∞ （对所有的 n ∈ N 且 n ̸= 0）。 则结构 M |= Q。（练习） 引理 9.1. (a) Q ̸⊢ ∀x Sx ̸≈ x。 (b) 对每一个标准自然数 n ∈ N，Q ⊢ Sn ̸≈ n，其中 n 代表 S n 0。 证明: 根据 S(∞) = ∞ 在例 9.1 中的模型 M 上成立，我们立刻得到 (a)。 断言 (b) 则是通过（外面的）对标准自然数 n ∈ N 作归纳而得到的。 当 n = 0 时，Q ⊢ S0 ̸≈ 0，这是根据 (Q1)。 假定 Q ⊢ Sn ̸≈ n。则根据 (Q2) 的逆否命题，我们立刻有 Q ⊢ S(n + 1) ̸≈ n + 1。 注： 引理 9.1 虽然很短，但包含的信息对本节的理解是至关重要的。 • 首先它表明了标准和非标准自然数的区别。每一个标准自然数 n ∈ N 都在我们的语 言内有一个“名字”，即数码 n。这个数码 n 是算术语言中的项 S n 0，它是语言内与 “外面的”自然数 n 的对应物。而非标准数则都是“无名鼠辈”，似乎飘忽不定。 • 考察断言 (b) 对所有 n ∈ N，Q ⊢ n ̸≈ Sn。注意这里实际上是一族证明，而不是一个 证明。当自然数 n 越来越大时，Q 对 n ̸≈ Sn 的证明也越来越长。而断言 (a) 则不然， 它否证的是一个适用于所有数的一致的2证明。 • 最后，请大家注意我们在“外部的”证明（如证明 (b) 时可以用归纳法）和系统 Q 内证明（Q 中显然没有归纳法）的区别。 我们再看 Q 的一些其它的简单事实。在本节中，我们用“⊢”来表达“Q ⊢”；并且将 x ≤ y 定义成 ∃z(x + z ≈ y)。 2这里的一致指的是数学中常用的一致性，即 uniformity，与无矛盾性无关。 2
第9章哥德尔第一不完全性定理 第1节可表示性 引理92.对所有m,n∈N,我们有 1)+var(Sx+n≈x+Sn) (2)+m+n≈Smn+0并且}mn≈Sm"0 (3)如果n≠m则+nm。 4)如果m≤n则}m≤n 5)如果mxn则+mzn 6+vr(x≤n4x≈0V…Vr≈n) 7)+vx(x≤nvn≤x)o 证明:见习题 引理92告诉我们一些有关Q模型的事实,后面我们会用到。令9为任意一个Q的 模型。 ·由引理92(2)和(3)我们有:函数n→n是从标准模型9到模型9的一个嵌入。 因此,我们可以不失一般性地假设9c9t ·还有(6)告诉我们:如果b∈9并且a<b,则a∈9。换句话说,9中所有的新 元素都是缀在9后面的;表述这种情形的术语为9是9的一个尾节扩张。 912可表示性 令T为一个包含Q的理论。在下面的讨论中,如果不加说明,则可隐含地假定理论 T为Q。 定义91.我们称一个自然数上的k元关系P为在T中数码逐点可表示的3或简称为可表 示的,如果存在一个公式p(),称为P的一个表示公式,使得 (m1,n2,…,nk)∈P→Thp(n1,n2,…,nk);并且 (m1,n2,…,nk)gP→T=p(n,n2,…,nk) 例9.2.(1)自然数上的等同关系{(m,m):n∈N}被公式x≈y所表示:显然,m=n蕴 涵}m≈n,并且根据引理9.2(3),m≠n蕴涵}m≠n (2)类似地,引理9.2(4和(5告诉我们关系≤可以被公式x≤y表示 数码逐点可表示的, numeralwise representable;可表示的, representable
第 9 章 哥德尔第一不完全性定理 第 1 节 可表示性 引理 9.2. 对所有 m, n ∈ N，我们有 (1) ⊢ ∀x(Sx + n ≈ x + Sn)。 (2) ⊢ m + n ≈ S m+n 0 并且 ⊢ m · n ≈ S m·n 0。 (3) 如果 n ̸= m 则 ⊢ n ̸≈ m。 (4) 如果 m ≤ n 则 ⊢ m ≤ n。 (5) 如果 m ̸≤ n 则 ⊢ m ̸≤ n。 (6) ⊢ ∀x(x ≤ n ↔ x ≈ 0 ∨ · · · ∨ x ≈ n)。 (7) ⊢ ∀x(x ≤ n ∨ n ≤ x)。 证明: 见习题。 引理 9.2 告诉我们一些有关 Q 模型的事实，后面我们会用到。令 M 为任意一个 Q 的 模型。 • 由引理 9.2 (2) 和 (3) 我们有：函数 n 7→ n M 是从标准模型 N 到模型 M 的一个嵌入。 因此，我们可以不失一般性地假设 N ⊆ M。 • 还有 (6) 告诉我们：如果 b ∈ N 并且 a ≤M b，则 a ∈ N。换句话说，M 中所有的新 元素都是缀在 N 后面的；表述这种情形的术语为 M 是 N 的一个尾节扩张。 9.1.2 可表示性 令 T 为一个包含 Q 的理论。在下面的讨论中，如果不加说明，则可隐含地假定理论 T 为 Q。 定义 9.1. 我们称一个自然数上的 k-元关系 P 为在 T 中数码逐点可表示的 3 或简称为可表 示的 ，如果存在一个公式 ρ(⃗x)，称为 P 的一个表示公式，使得 (n1, n2, · · · , nk) ∈ P ⇒ T ⊢ ρ(n1, n2, · · · , nk); 并且 (n1, n2, · · · , nk) ̸∈ P ⇒ T ⊢ ¬ρ(n1, n2, · · · , nk)。 例 9.2. (1) 自然数上的等同关系 {(n, n) : n ∈ N} 被公式 x ≈ y 所表示：显然，m = n 蕴 涵 ⊢ m ≈ n，并且根据引理 9.2 (3)，m ̸= n 蕴涵 ⊢ m ̸≈ n。 (2) 类似地，引理 9.2 (4) 和 (5) 告诉我们关系 ≤ 可以被公式 x ≤ y 表示。 3数码逐点可表示的，numeralwise representable；可表示的，representable。 3
第1节可表示性 第9章哥德尔第一不完全性定理 我们看一些可表示性的简单性质 ·如果P是可表示的,则P是递归的。 证明:对给定的自然数组,递归地枚举所有Q(或任何递归的公理系统T)中 的证明序列,直到p(n或p()的证明出现。如果是前者,则P(n)成立;后者, 则P(可)不成立。可表示性告诉我们该证明一定会出现。 ·可表示的关系在布尔运算下是封闭的。 证明:假设P和Q分别由公式p1和P表示。则PUQ、P∩Q和Ⅳ\P分别由公 式p1VP2、p1AP2和→p1来表示 如果P在Q中被公式p表示,则P在Q的任何相容扩张(例如,PA或Th(9)中 都被p表示。 P在Th(9)中被ρ表示当且仅当P在结构?中被ρ定义。 证明:练习。 定理9(Q的∑1完备性).对任一∑1-闭语句r,我们有 9F7当且仅当Q+T。 注 我们称一个Car中的公式为△0的,如果它只包含有界量词。我们称一个形 如彐x1…丑xn6的公式为∑1的,其中θ是△0的。一个∑1公式的否定总是逻辑 等价于一个形如Vx1…VxnO的公式,我们称这样的公式是I1的。而如果一个公式 机即等价于一个∑1公式又等价于一个∏1公式,我们就称之为△1的。 ·引理9.1告诉我们对I1-闭语句,如x(Sx≈x),我们则没有这种完备性 证明:由于“←”立刻可以从犷是Q的一个模型导出,我们下面证明另一个方向“→” 断言对任何△o-闭语句σ,对任何Q的模型,我们有9a当且仅当9a 断言的证明我们对σ进行归纳。首先注意:对任何一个闭项t(即,t中不含自由变元) 我们有=。因此断言对任何的原子闭公式成立。不难证明对于不含量词(无论有界 或无界的)的闭语句r断言也成立。 给定任意的形如(wx≤t)(x)的闭公式a,其中t是一个闭项,并假定9}(wx≤ f)e(x)。则对所有的a<,都有9}6(a)。移到模型中来讨论,我们有tm
第 1 节 可表示性 第 9 章 哥德尔第一不完全性定理 我们看一些可表示性的简单性质： • 如果 P 是可表示的，则 P 是递归的。 证明: 对给定的自然数组 ⃗n，递归地枚举所有 Q （或任何递归的公理系统 T）中 的证明序列，直到 ρ(⃗n) 或 ¬ρ(⃗n) 的证明出现。如果是前者，则 P(⃗n) 成立；后者， 则 P(⃗n) 不成立。可表示性告诉我们该证明一定会出现。 • 可表示的关系在布尔运算下是封闭的。 证明: 假设 P 和 Q 分别由公式 ρ1 和 ρ2 表示。则 P ∪ Q、P ∩ Q 和 N k \ P 分别由公 式 ρ1 ∨ ρ2、ρ1 ∧ ρ2 和 ¬ρ1 来表示。 • 如果 P 在 Q 中被公式 ρ 表示，则 P 在 Q 的任何相容扩张（例如，PA 或 Th (N)）中 都被 ρ 表示。 • P 在 Th (N) 中被 ρ 表示当且仅当 P 在结构 N 中被 ρ 定义。 证明: 练习。 定理 9.1 (Q 的 Σ1-完备性). 对任一 Σ1-闭语句 τ，我们有 N |= τ 当且仅当 Q ⊢ τ。 注： • 我们称一个 Lar 中的公式为 ∆0 的，如果它只包含有界量词。我们称一个形 如 ∃x1 · · · ∃xn θ 的公式为 Σ1 的，其中 θ 是 ∆0 的。一个 Σ1 公式的否定总是逻辑 等价于一个形如 ∀x1 · · · ∀xnθ 的公式，我们称这样的公式是 Π1 的。而如果一个公式 机即等价于一个 Σ1 公式又等价于一个 Π1 公式，我们就称之为 ∆1 的。 • 引理 9.1 告诉我们对 Π1-闭语句，如 ∀x(Sx ̸≈ x)，我们则没有这种完备性。 证明: 由于“⇐”立刻可以从 N 是 Q 的一个模型导出，我们下面证明另一个方向“⇒”。 断言. 对任何 ∆0-闭语句 σ，对任何 Q 的模型 M，我们有 M |= σ 当且仅当 N |= σ。 断言的证明. 我们对 σ 进行归纳。首先注意：对任何一个闭项 t （即，t 中不含自由变元）， 我们有 t N = t M。因此断言对任何的原子闭公式成立。不难证明对于不含量词（无论有界 或无界的）的闭语句 τ 断言也成立。 给定任意的形如 (∀x ≤ t)θ(x) 的闭公式 σ，其中 t 是一个闭项，并假定 N |= (∀x ≤ t)θ(x)。则对所有的 a ≤N t N，都有 N |= θ(a)。移到模型 M 中来讨论，我们有 t M = 4
第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
第1节可表示性 第9章哥德尔第一不完全性定理 从这段讨论我们可以得出,如果公式φ表示f(作为一个一元函数),则公式φ也表 示Gr(作为一个二元关系)。但反过来则不一定。关于函数可表示性的问题,我们等一下 在推论9.1中会有更明确的结论。 引理9.4.令t为语言Car中的一个项,其中出现的变元都包含在x1,x2,…,xk当中。则它 诱导出的k-元函数f(m1,m2,…,nk)=t(m1,n2…,nk)是可表示的。特别地,后继函数 常数函数、加法、乘法和投射函数都是可表示的。 证明:令y(x1,x2,…,xk,y)为y≈t(x1,x2,…,xk)。则对任何的m,m2,…,mk∈N显然 有 rwyy≈tn,n2,…,nk)分y≈f(m1,n2,……,nk) 因为rt(n1,n2,…,nk)≈ft(n1,n2,…,nk)(这可以从引理92,加上对t归纳来证 明)。 定理9.2.可表示函数构成的类对复合运算封闭,即,假定函数h1(x1,x2,…,xn)、h2(x1,x2,…,xn) hn(x1,x2,…,xn)和函数g(h,y2,…,y)都是可表示的,则复合函数∫=9(h1,h2,……,h)也 证明:我们用向量符号表示(x1,x2,…,xn)。固定公式1(x,y)(作为函数)分别表 示h()(1≤i≤r),和公式v(h,y2,…,y,2)(作为函数)表示g(,y2,…,y)。对1≤ i<r,m∈Ⅳ我们有 l(m,)+v≈ha(m)] (9.1) 并且对n1,m2,…,m-∈N,我们有 g(n1, n2 令φ(x,z)为公式 (∧a(E,9)→v( 我们证明:对任何m∈N, ≈f(m 先看从右向左的方向,我们要证:rφ(m,f(m),即 …H∧a(,)→m,…,,f)
第 1 节 可表示性 第 9 章 哥德尔第一不完全性定理 从这段讨论我们可以得出，如果公式 φ 表示 f（作为一个一元函数），则公式 φ 也表 示 Gf（作为一个二元关系）。但反过来则不一定。关于函数可表示性的问题，我们等一下 在推论 9.1 中会有更明确的结论。 引理 9.4. 令 t 为语言 Lar 中的一个项，其中出现的变元都包含在 x1, x2, · · · , xk 当中。则它 诱导出的 k-元函数 ft(n1, n2, · · · , nk) = t(n1, n2, · · · , nk) 是可表示的。特别地，后继函数、 常数函数、加法、乘法和投射函数都是可表示的。 证明: 令 φ(x1, x2, · · · , xk, y) 为 y ≈ t(x1, x2, · · · , xk)。则对任何的 n1, n2, · · · , nk ∈ N 显然 有 ⊢T ∀y [y ≈ t(n1, n2, · · · , nk) ↔ y ≈ ft(n1, n2, · · · , nk)] 因为 ⊢T t(n1, n2, · · · , nk) ≈ ft(n1, n2, · · · , nk) （这可以从引理 9.2，加上对 t 归纳来证 明）。 定理9.2. 可表示函数构成的类对复合运算封闭，即，假定函数h1(x1, x2, · · · , xn)、h2(x1, x2, · · · , xn)、…… 、hr(x1, x2, · · · , xn) 和函数 g(y1, y2, · · · , yr) 都是可表示的，则复合函数f = g(h1, h2, · · · , hr) 也 是。 证明: 我们用向量符号 ⃗x 表示 (x1, x2, · · · , xn)。固定公式 θi(⃗x, yi)（作为函数）分别表 示 hi(⃗x) (1 ≤ i ≤ r)，和公式 ψ(y1, y2, · · · , yr, z)（作为函数）表示 g(y1, y2, · · · , yr)。对 1 ≤ i ≤ r，⃗m ∈ N n 我们有 ⊢T ∀yi [θi(m⃗ , yi) ↔ yi ≈ hi(m⃗ )], (9.1) 并且对 n1, n2, · · · , nr ∈ N，我们有 ⊢T ∀z[ψ(n1, n2, · · · , nr, z) ↔ z ≈ g(n1, n2, · · · , nr)]。 (9.2) 令 φ(⃗x, z) 为公式 ∀y1 · · · ∀yr[(∧r i=1 θi(⃗x, yi)) → ψ(y1, · · · , yr, z)]。 我们证明：对任何 ⃗m ∈ N n， ⊢T ∀z(φ(m⃗ , z) ↔ z ≈ f(m⃗ ))。 先看从右向左的方向，我们要证：⊢T φ(m⃗ , f(m⃗ ))，即 ⊢T ∀y1 · · · ∀yr[(∧r i=1 θi(m⃗ , yi)) → ψ(y1, · · · , yr, f(m⃗ ))]。 6
第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
第1节可表示性 第9章哥德尔第一不完全性定理 证明:我们只证明唯一性的方向:+y(a,y)→y≈f(a 令b=∫(d。则根据一阶逻辑b<y}(z<y)a(a,x)。 另一方面,y<b}Vn<by≈n,而根据P的可表示性a(a,y) 最后再利用引理92(7):对任何b∈N,Vy(y≤bvb≤y),我们就得到 gy(a,y)→y≈b 推论91.如果一个函数f(的图像)作为关系是可表示的,则∫作为函数也是可表示的 (但表示它们的公式可能不相同)。 证明:只需注意到如果Gr是函数f的图像,则函数d→pbG(a,b)就是f自身。口 所以对一个函数来说,就可表示性而言,作为关系和作为函数没有什么不同,不同的 只是表达它们的公式而已。 引理9.5还告诉我们可表示的函数类对正则极小算子是封闭的。为了强调,我们把它 列为定理 定理93.假定函数g(x,y)是可表示的并且y9(x,y)=0。则函数f(x)=dyg(x,y)= 0也是可表示的。 附带提以下,在哥德尔1931年的文章中,他只证明了原始递归函数都是可表示的, 而没有考虑正则极小算子和所有的递归函数。我们可以进一步说,哥德尔的可表示的函数 实际上是递归函数的一个等价刻画(见推论92)。 914仅用加法和乘法编码 我们已经证明了所有的初始函数都是可表示的,并且可表示函数的类对复合和正则 的极小算子封闭。我们还剩下原始递归有待处理 回忆一下我们通常(例如在集合论中)是怎样论证原始递归的合理性的。假设函 数f(x,y)是通过g和h由原始递归得到的。我们可以直接写出f(x,n)=m的显式定 义:“存在一个有穷序列(的编码)s,它的长度是n+1使得(s)o=9(x)且对所有 的i<n,(s)+1=h(x,,(s))和(s)n=m"。这里的编码和解码通常是利用指数函数ry和 素数分解来完成的。但是,指数函数xy和pn2本身都是利用原始递归来定义的。论证它们 的可表示性和论证原始递归的可表示性难度是一样的。要想打破这种“鸡生蛋,蛋生鸡” 的怪圈,我们需要一个可表示的编码和解码函数。哥德尔利用了中国剩余定理,巧妙地解 决了这个问题。 我们需要下面关于整数的引理 8
第 1 节 可表示性 第 9 章 哥德尔第一不完全性定理 证明: 我们只证明唯一性的方向：⊢ φ(⃗a, y) → y ≈ f(⃗a)。 令 b = f(⃗a)。则根据一阶逻辑 b < y ⊢ (∃z < y)α(⃗a, z)。 另一方面，y < b ⊢ ∨ n<b y ≈ n，而根据 P 的可表示性 ⊢ ¬α(⃗a, y)。 最后再利用引理 9.2 (7)：对任何 b ∈ N，⊢ ∀y(y ≤ b ∨ b ≤ y)，我们就得到 ⊢ φ(⃗a, y) → y ≈ b。 推论 9.1. 如果一个函数 f （的图像）作为关系是可表示的，则 f 作为函数也是可表示的 （但表示它们的公式可能不相同）。 证明: 只需注意到如果 Gf 是函数 f 的图像，则函数 ⃗a 7→ µb[Gf (⃗a, b)] 就是 f 自身。 所以对一个函数来说，就可表示性而言，作为关系和作为函数没有什么不同，不同的 只是表达它们的公式而已。 引理 9.5 还告诉我们可表示的函数类对正则极小算子是封闭的。为了强调，我们把它 列为定理： 定理 9.3. 假定函数 g(x, y) 是可表示的并且 ∀x∃y g(x, y) = 0。则函数 f(x) =df µy g(x, y) = 0 也是可表示的。 附带提以下，在哥德尔 1931 年的文章中，他只证明了原始递归函数都是可表示的， 而没有考虑正则极小算子和所有的递归函数。我们可以进一步说，哥德尔的可表示的函数 实际上是递归函数的一个等价刻画（见推论 9.2）。 9.1.4 仅用加法和乘法编码 我们已经证明了所有的初始函数都是可表示的，并且可表示函数的类对复合和正则 的极小算子封闭。我们还剩下原始递归有待处理。 回忆一下我们通常（例如在集合论中）是怎样论证原始递归的合理性的。假设函 数 f(⃗x, y) 是通过 g 和 h 由原始递归得到的。我们可以直接写出 f(⃗x, n) = m 的显式定 义：“存在一个有穷序列（的编码） s，它的长度是 n + 1 使得 (s)0 = g(⃗x) 且对所有 的 i < n，(s)i+1 = h(⃗x, i,(s)i) 和 (s)n = m”。这里的编码和解码通常是利用指数函数 x y 和 素数分解来完成的。但是，指数函数 x y 和 pn 本身都是利用原始递归来定义的。论证它们 的可表示性和论证原始递归的可表示性难度是一样的。要想打破这种“鸡生蛋，蛋生鸡” 的怪圈，我们需要一个可表示的编码和解码函数。哥德尔利用了中国剩余定理，巧妙地解 决了这个问题。 我们需要下面关于整数的引理： 8
第9章哥德尔第一不完全性定理 第1节可表示性 引理96(欧几里得.假定a,b为互素的整数。则存在整数a和v使得u+vb=1 通常的证明是利用欧几里得的辗转相除法。我们后面会证明一个在PA中的版本。这 里我们就不证 定理94(中国剩余定理)令d,…,dn为两两互素的自然数、a0,…,an为满足a1<d1 (0≤i≤n)的自然数。则存在自然数c使得对所有的i≤m,a1是的余数。换句话说, c是下列同余方程组的解 证明:我们对n施行归纳。当n=0时是显然的。假定命题对n=k成立。我们考 察n=k+1的情形。根据归纳假定,存在自然数b使得对所有i≤k都有b≡da。 令d为自然数do,…,dk的最小公倍数。不难验证,d和dk+1是互素的。 我们先找到整数r,s使得b+rd=sdk+1+ak+1:由于d和dk+1互素,根据欧几里得 引理,存在整数u和υ使得ud+vdk+1=1。将等式两边都乘上ak+1-b,再通过简单移 项便可以知道,取r=(ak+1-b)u和s=(b-ak+1)v即可。 令z=b+rd=sdk+1+ak+1。一方面,对i<k,我们有 另一方面,2≡a+1sdk+1+ak+1≡ak+1ak+1最后,由于同余方程组的解具有周期D do,…,dk+1的最小公倍数。存在足够大的自然数m使得c=z+mD是非负整数。c就是 我们所要的 要想使用中国剩余定理来将有穷序列(ao,…,an)编码,我们需要足够大的两两互素 的自然数do,…,dn,下面的引理说明怎样找它们。 引理97.对任意的s≥0,下列s+1个自然数 是两两互素的。 证明:假定某个素数p满足p|1+(i+1)s!且pl1+(j+1)s!。则p(-i)s!。所以,或 者p(-i)或者pls!。无论哪种情形,都有pls!,进而p1,矛盾
第 9 章 哥德尔第一不完全性定理 第 1 节 可表示性 引理 9.6 (欧几里得). 假定 a, b 为互素的整数。则存在整数 u 和 v 使得 ua + vb = 1。 通常的证明是利用欧几里得的辗转相除法。我们后面会证明一个在 PA 中的版本。这 里我们就不证了。 定理 9.4 (中国剩余定理). 令 d0, · · · , dn 为两两互素的自然数、a0, · · · , an 为满足 ai < di （0 ≤ i ≤ n）的自然数。则存在自然数 c 使得对所有的 i ≤ n，ai 是 c di 的余数。换句话说， c 是下列同余方程组的解： x ≡d0 a0 x ≡d1 a1 . . . x ≡dn an。 证明: 我们对 n 施行归纳。当 n = 0 时是显然的。假定命题对 n = k 成立。我们考 察 n = k + 1 的情形。根据归纳假定，存在自然数 b 使得 对所有 i ≤ k 都有 b ≡di ai。 令 d 为自然数 d0, · · · , dk 的最小公倍数。不难验证，d 和 dk+1 是互素的。 我们先找到整数 r, s 使得 b + rd = sdk+1 + ak+1：由于 d 和 dk+1 互素，根据欧几里得 引理，存在整数 u 和 v 使得 ud + vdk+1 = 1。将等式两边都乘上 ak+1 − b，再通过简单移 项便可以知道，取 r = (ak+1 − b)u 和 s = (b − ak+1)v 即可。 令 z = b + rd = sdk+1 + ak+1。一方面，对 i ≤ k，我们有 z ≡di b + rd ≡di b ≡di≡di ai。 另一方面，z ≡dk+1 sdk+1 + ak+1 ≡dk+1 ak+1。最后，由于同余方程组的解具有周期 D - d0, · · · , dk+1 的最小公倍数。存在足够大的自然数 m 使得 c = z + mD 是非负整数。c 就是 我们所要的。 要想使用中国剩余定理来将有穷序列 (a0, · · · , an) 编码，我们需要足够大的两两互素 的自然数 d0, · · · , dn，下面的引理说明怎样找它们。 引理 9.7. 对任意的 s ≥ 0，下列 s + 1 个自然数 1 + 1 · s!, 1 + 2 · s!, · · · , 1 + (s + 1) · s! 是两两互素的。 证明: 假定某个素数 p 满足 p|1 + (i + 1)s! 且 p|1 + (j + 1)s!。则 p|(j − i)s!。所以，或 者 p|(j − i) 或者 p|s!。无论哪种情形，都有 p|s!，进而 p|1，矛盾。 9
第1节可表示性 第9章哥德尔第一不完全性定理 引理98.定义函数a:N3→N为 a(c,d,)= 中的余数 1+(i+1)d ur Bq scc=q(1+(i+1)d)+r)l 则a在Q中是可表示的 证明:因为它是从可表示的关系经有界量词和正则极小算子得到的 我们在系统外面(即在N中)验证对所有的n,a0,…,an,存在c和d使得对任 意i≤n都有a(c,d,i)=a;所以a(c,d,)可以胜任可表示的编码函数。给定n,an,,an 让s=max{n,ao,…,an}、d=s!、d=1+(+1)·s!、和c=中国剩余定理中的那个 数c显然我们有a(c,d,i)=a 我们利用数对的编码函数来把c和d压缩成一个数。 引理99.令 Ja,b)=(a+b)(a+b+1)+a K(p) ≤P3b≤pJ(a,b) L(p)=pb≤p3a≤pJ(a,b)=p 则函数,K,L在Q中都是可表示的。 引理910.定义哥德尔的-函数为B(s,)=a(K(s),L(s),)。则B(s,i)在Q中是可表示 的。且对任何自然数n,ao,…,an都存在自然数s使得对任意i≤n都有B(s,i)=a2 这两个引理的证明我们都留作练习 定理9.5.可表示函数形成的类对原始递归封闭 证明:假设∫的递归定义为:f(On,0)=9(m)和f(m,n)=h(m,n,f(m,m),其中g和h都 是可表示的。则关系 P(m,m,s):=B(s,0)=9(m)∧i<n[6(s,+1)=h(m,m,B(s,i) 也是可表示的,因为它是可表示关系和函数的复合。直观上看,P(m,n,s)说的是 s是∫从i=0到i=n的计算历史的编码”。令F(m,n)=AP(m,n,s)。因 为9}ⅷ,n彐sP(m,n,s),根据可表示函数对正则极小算子的封闭性,F是可表示 的。所以,f(m,n)=B(F(m,n),m)也是可表示的
第 1 节 可表示性 第 9 章 哥德尔第一不完全性定理 引理 9.8. 定义函数 α : N 3 → N 为 α(c, d, i) = c 1 + (i + 1)d 中的余数 = µr [∃q ≤ c(c = q(1 + (i + 1)d) + r)]。 则 α 在 Q 中是可表示的。 证明: 因为它是从可表示的关系经有界量词和正则极小算子得到的。 我们在系统外面（即在 N 中）验证对所有的 n, a0, · · · , an，存在 c 和 d 使得对任 意 i ≤ n 都有 α(c, d, i) = ai；所以 α(c, d, i) 可以胜任可表示的编码函数。给定 n, a0, . . . , an， 让 s = max{n, a0, · · · , an}、d = s!、di = 1 + (i + 1) · s!、和 c = 中国剩余定理中的那个 数 c。显然我们有 α(c, d, i) = ai . 我们利用数对的编码函数来把 c 和 d 压缩成一个数。 引理 9.9. 令 J(a, b) = 1 2 (a + b)(a + b + 1) + a。 K(p) = µa ≤ p ∃b ≤ p J(a, b) = p。 L(p) = µb ≤ p ∃a ≤ p J(a, b) = p。 则函数 J, K, L 在 Q 中都是可表示的。 引理 9.10. 定义哥德尔的 β-函数 为 β(s, i) = α(K(s), L(s), i)。则 β(s, i) 在 Q 中是可表示 的。且对任何自然数 n, a0, · · · , an 都存在自然数 s 使得对任意 i ≤ n 都有 β(s, i) = ai。 这两个引理的证明我们都留作练习。 定理 9.5. 可表示函数形成的类对原始递归封闭。 证明: 假设 f 的递归定义为：f(⃗m, 0) = g(⃗m) 和 f(⃗m, n) = h(⃗m, n, f(⃗m, n))，其中 g 和 h 都 是可表示的。则关系 P(⃗m, n, s) := β(s, 0) = g(⃗m) ∧ ∀i < n [β(s, i + 1) = h(⃗m, n, β(s, i))] 也是可表示的，因为它是可表示关系和函数的复合。直观上看，P(⃗m, n, s) 说的是 “s 是 f 从 i = 0 到 i = n 的计算历史的编码”。令 F(⃗m, n) = µs P(⃗m, n, s)。因 为 N |= ∀⃗m, n∃s P(⃗m, n, s)，根据可表示函数对正则极小算子的封闭性，F 是可表示 的。所以，f(⃗m, n) = β(F(⃗m, n), n) 也是可表示的。 10
