第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