第9章哥德尔第一不完全性定理 第2节语法的算术化 915可表示性定理 由于递归函数类是最小的包含初始函数并且对复合,原始递归和正规p-算子封闭的 函数类;综合前面的结果,我们立刻得到下列定理 定理96(可表示性定理).所有的递归函数在Q中都是可表示的。因而,所有的递归关系 在Q中也都是可表示的。 证明:习题。 回忆一下,在给出可表示的关系的定义后,我们立刻知道:所有可表示关系都是递归 关系。因此可表示关系就是递归关系。我们把它单列出来,以加深印象 推论92.对任何的k-元关系RCⅣ和任何递归且相容的扩张T2Q,下列命题等价 )R在T中可表示; ijR是一个递归关系 对于关心定义复杂性的读者,借助递归论的知识,我们有进一步的推论 推论93.对任何的k元关系RcN和任何递归且相容的扩张T2Q,下列命题等价 )R在T中可表示; iR在T中可被一个△1的公式表示 证明:我们只证明“()→(i)”。如果R在T中是可表示的,则R是递归的。由于R和R的 否定都是递归可枚举的,根据引理?,R在结构中可以被一个Δ1的公式定义。再由 Q的∑1-完全性,我们就得到R可以被一个△1的公式所表示。 第2节语法的算术化 回忆一下,我们选择算术语言Cax的初衷是讨论自然数的算术性质。例如,闭语句 v(1≠2·+21)表达了关于自然数1和21的某些性质。表面上看,语言Ca不适合讨 论逻辑中的语法性质,例如,“量词符号Ⅴ不是一个变元符号”这一事实似乎不属于语言 Car的讨论范围。 下面我们将论证:在语言Car中我们能够讨论逻辑中的语法,甚至在某种程度上我们 还可以讨论语义。关键的想法是用编码。这一想法是哥德尔在不完全性定理证明中首先使 用的,通常被称为哥德尔编码。与前面简化版本的算术语言不同,一旦语言中同时包含
第 9 章 哥德尔第一不完全性定理 第 2 节 语法的算术化 9.1.5 可表示性定理 由于递归函数类是最小的包含初始函数并且对复合，原始递归和正规 µ- 算子封闭的 函数类；综合前面的结果，我们立刻得到下列定理： 定理 9.6 (可表示性定理). 所有的递归函数在 Q 中都是可表示的。因而，所有的递归关系 在 Q 中也都是可表示的。 证明: 习题。 回忆一下，在给出可表示的关系的定义后，我们立刻知道：所有可表示关系都是递归 关系。因此可表示关系就是递归关系。我们把它单列出来，以加深印象： 推论 9.2. 对任何的 k-元关系 R ⊆ N k 和任何递归且相容 的扩张 T ⊇ Q，下列命题等价： (i) R 在 T 中可表示； (ii) R 是一个递归关系。 对于关心定义复杂性的读者，借助递归论的知识，我们有进一步的推论： 推论 9.3. 对任何的 k-元关系 R ⊆ N k 和任何递归且相容 的扩张 T ⊇ Q，下列命题等价： (i) R 在 T 中可表示； (ii) R 在 T 中可被一个 ∆1 的公式表示。 证明: 我们只证明“(i) ⇒ (ii)”。如果 R 在 T 中是可表示的，则 R 是递归的。由于 R 和 R 的 否定都是递归可枚举的，根据引理 ??，R 在结构 N 中可以被一个 ∆1 的公式定义。再由 Q 的 Σ1- 完全性，我们就得到 R 可以被一个 ∆1 的公式所表示。 第 2 节 语法的算术化 回忆一下，我们选择算术语言 Lar 的初衷是讨论自然数的算术性质。例如，闭语句 ∀v (1 ̸≈ 2 · v + 21) 表达了关于自然数 1 和 21 的某些性质。表面上看，语言 Lar 不适合讨 论逻辑中的语法性质，例如，“量词符号 ∀ 不是一个变元符号”这一事实似乎不属于语言 Lar 的讨论范围。 下面我们将论证：在语言 Lar 中我们能够讨论逻辑中的语法，甚至在某种程度上我们 还可以讨论语义。关键的想法是用编码。这一想法是哥德尔在不完全性定理证明中首先使 用的，通常被称为哥德尔 编码。与前面简化版本的算术语言不同，一旦语言中同时包含 11
第2节语法的算术化 第9章哥德尔第一不完全性定理 加法和乘法,我们可以把各种对象进行编码,然后通过讨论它们的码间接地讨论对象的性 质。我们在递归论部分曾经体验过编码带来的好处,例如,我们把(图灵机或其它)程序 用它的码e来代表。这样一来,关于程序的命题就转换成关于自然数e的命题。我们要做 的是把逻辑语法中的对象,如“公式”、“证明”等等都用自然数来编码,从而在语言Car 中研究它们的性质。这一过程就是所谓的语法的算术化。 显然,编码的方法不是唯一的,我们的兴趣也不在编码的细节上,除了一点:为了可 表示性的需要,我们所感兴趣的对象(如公式,证明等等)在编码之后应该是自然数的递 归子集。哥德尔编码在1930年代被视为非常神奇的技巧。但现在由于计算机的普及,把 各种对象数字化已经是司空见惯了。直观上看,我们下面列出的清单中的所有对象(除了 最后一项“可证性”)都是可以用计算机处理的,因而都是递归的。 921哥德尔编码 我们首先给每一个逻辑符号指派一个自然数 「符号 哥德尔数坎 7911131517192123 接下来,我们指派给字符串5=0…n的哥德尔数为(0…,n)=p60 ·下面我们给项编码时会把项当作有穷序列来处理,因此所有项(和公式)的编码都 是偶数。所以用奇数来代表原始符号有一个小小的好处,我们可以区别作为符号 的0还是作为项的0;前者的编码是3而后者是23+1=16 ·上述的编码方法也可以推广到更一般的语言,只要语言中的参数集L是可判定的即 ·我们这一节中的一切都是在标准自然数上完成的,与形式系统无关。因此使用指数 函数等等均不会带来任何问题。 (1)V={a:a是一个变元}是原始递归的。 由于V={n∈N:(玉k<n)n=2k+21},所以显然是原始递归的 注意:我们实际上是在自然数中创造一个逻辑中变元符号的同构像。例如,21就 是t在这个同构下的像。为了强调逻辑中的对象与其在自然数中的像的联系,我们用 加下划线的方法来增强暗示性,例如,V中的元素就被称为一个“变元"。现在v(1≈ 12
第 2 节 语法的算术化 第 9 章 哥德尔第一不完全性定理 加法和乘法，我们可以把各种对象进行编码，然后通过讨论它们的码间接地讨论对象的性 质。我们在递归论部分曾经体验过编码带来的好处，例如，我们把（图灵机或其它）程序 用它的码 e 来代表。这样一来，关于程序的命题就转换成关于自然数 e 的命题。我们要做 的是把逻辑语法中的对象，如“公式”、“证明”等等都用自然数来编码，从而在语言 Lar 中研究它们的性质。这一过程就是所谓的语法的算术化。 显然，编码的方法不是唯一的，我们的兴趣也不在编码的细节上，除了一点：为了可 表示性的需要，我们所感兴趣的对象（如公式，证明等等）在编码之后应该是自然数的递 归子集。哥德尔编码在 1930 年代被视为非常神奇的技巧。但现在由于计算机的普及，把 各种对象数字化已经是司空见惯了。直观上看，我们下面列出的清单中的所有对象（除了 最后一项“可证性”）都是可以用计算机处理的，因而都是递归的。 9.2.1 哥德尔编码 我们首先给每一个逻辑符号指派一个自然数。 符号 ζ ∀ 0 S + · ( ) ¬ → = v0 v1 . . . 哥德尔数 ♯ζ 1 3 5 7 9 11 13 15 17 19 21 23 . . . 接下来，我们指派给字符串ξ = ζ0 . . . ζn 的哥德尔数为⟨♯ζ0, · · · , ♯ζn⟩ = p ♯ζ0+1 0 . . . p♯ζn+1 n 。 注： • 下面我们给项编码时会把项当作有穷序列来处理，因此所有项（和公式）的编码都 是偶数。所以用奇数来代表原始符号有一个小小的好处，我们可以区别作为符号 的 0 还是作为项的 0；前者的编码是 3 而后者是 2 3+1 = 16。 • 上述的编码方法也可以推广到更一般的语言，只要语言中的参数集 L 是可判定的即 可。 • 我们这一节中的一切都是在标准自然数上完成的，与形式系统无关。因此使用指数 函数等等均不会带来任何问题。 (1) V = {♯α : α 是一个变元 } 是原始递归的。 由于 V = {n ∈ N : (∃k < n)n = 2k + 21}，所以显然是原始递归的。 注意：我们实际上是在自然数中创造一个逻辑中变元符号的同构像。例如，21 就 是 v0 在这个同构下的像。为了强调逻辑中的对象与其在自然数中的像的联系，我们用 加下划线的方法来增强暗示性，例如，V 中的元素就被称为一个“变元”。现在 ∀v (1 ̸≈ 12
第9章哥德尔第一不完全性定理 第2节语法的算术化 2u+21)说的是“y不是一个变元”。这样,通过讨论自然数里的同构像,我们间接地可 以在算术语言Ca内讨论逻辑中的语法 般地,对于一个逻辑中的对象O,我们用O表示O在自然数中的同构像,即O {a:a∈O 当然,v和址都是21。必要的时候,我们仍会使用符号。我们用表示ta的逆 运算,即,坻=x当且仅当x=ξ。(对不属于编码值域的自然数y,我们不关心的 值,可以定义它为任何事先给定的符号。 (2)集合{t:t是一个项}是原始递归的 证明:仿照项的递归定义,项具有如下的递归定义:t是一个项,如果 3s<t使得t=(s)且s是一个变元或者s=Q;或者 3r,s<t使得t=(r)s且r=S且s是一个项;或者 彐q,r,s<t使得t=(q)^r^s且q=±∨q=:且r和s都是项。 所以结论成立 注意,定义项的哥德尔数通常由两种办法。以t=SS0为例,一种是=(#s,#S,:0)序 列长度为3;一种是址=(S,(1S,t0)》序列长度为2。我们采用的是前者。 类似地, (3)集合{a:a是一个原子公式}是原始递归的。 (4)集合{a:a是一个公式}是原始递归的。 (5)存在一个原始递归函数Sb使得对任意项或公式α,对任意变元x和任意项t,我们 有 Sb(ta, tc, #t)=for 证明:仿照替换的定义 如果a是变元x; 如果a是项Su (u1)(u2),如果a是u1口u2其中口是+或 (u1)≈(u2)2,如果a是u1≈u2; 如果a=(-); (2→)如果a=(8→) Vy Bi 如果y≠x且a是vyB; 其它情形。 我们可以利用强递归来定义Sba,b,c)。具体步骤我们留作习题
第 9 章 哥德尔第一不完全性定理 第 2 节 语法的算术化 2v + 21) 说的是“∀ 不是一个变元”。这样，通过讨论自然数里的同构像，我们间接地可 以在算术语言 Lar 内讨论逻辑中的语法。 一般地，对于一个逻辑中的对象 O，我们用 O 表示 O 在自然数中的同构像，即 O = {♯a : a ∈ O}。 当然，v0 和 ♯v0 都是 21。必要的时候，我们仍会使用符号 ♯。我们用 ♮a 表示 ♯a 的逆 运算，即，♯ξ = x 当且仅当 ♮x = ξ。（对不属于编码值域的自然数 y，我们不关心 ♮y 的 值，可以定义它为任何事先给定的符号。） (2) 集合 {t : t 是一个项} 是原始递归的。 证明: 仿照项的递归定义，项 具有如下的递归定义：t 是一个项，如果 • ∃s < t 使得 t = ⟨s⟩ 且 s 是一个变元 或者 s = 0；或者 • ∃r, s < t 使得 t = ⟨r⟩^s 且 r = S 且 s 是一个项；或者 • ∃q, r, s < t 使得 t = ⟨q⟩^r^s 且 q = + ∨ q = · 且 r 和 s 都是项。 所以结论成立。 注意，定义项的哥德尔数通常由两种办法。以 t = SS0为例，一种是♯t = ⟨♯S, ♯S, ♯0⟩ 序 列长度为 3；一种是 ♯t = ⟨♯S,⟨♯S, ♯0⟩⟩ 序列长度为 2。我们采用的是前者。 类似地， (3) 集合 {a : a 是一个原子公式} 是原始递归的。 (4) 集合 {a : a 是一个公式} 是原始递归的。 (5) 存在一个原始递归函数 Sb 使得对任意项或公式 α，对任意变元 x 和任意项 t，我们 有： Sb(♯α, ♯x, ♯t) = ♯αx t 。 证明: 仿照替换的定义 α x t = t, 如果 α 是变元 x； Su x t , 如果 α 是项 Su； (u1) x t (u2) x t , 如果 α 是 u1u2 其中 是 + 或 ·； (u1) x t ≈ (u2) x t , 如果 α 是 u1 ≈ u2； (¬β x t ) 如果 α = (¬β)； (β x t → γ x t ) 如果 α = (β → γ)； ∀y βx t 如果 y ̸= x 且 α 是 ∀yβ； α, 其它情形。 我们可以利用强递归来定义 Sb(a, b, c)。具体步骤我们留作习题。 13
第2节语法的算术化 第9章哥德尔第一不完全性定理 (6)函数f(n)=#(S"0)是原始递归的,因而,集合{m:m是一个数码}是原始递归的。 证明:f(0)=(0)且f(n+1)=(S)^f(m) (7)定义自然数上的二元关系“x在a中自由出现”如下:x是一个变元,a是一个项 或公式,且x在t中自由出现。(显然,当加a为一个项时,自由出现和出现的意 思是一样的。)则关系“x在a中自由出现”是原始递归的。 证明x在a中自由出现当且仅当Sb(a,x,(0)≠a (8)集合{a:a是一个闭语句}是原始递归的 证明:a是一个闭语句当且仅当a一个公式且对任何x<a,如果x是一个变元则x不 在a中自由出现 (9)定义自然数上的三元关系“t在a中可以替换x”,如果x是一个变元,a是一个公式, t是一个项,且址t在址a中可以替换加x。则关系“t在α中可以替换x”是原始递归 的 证明:首先请读者自己给出“a是一b”、“a是b→c”和“a是yb”的定义,并验证它们 可以是原始递归的。 关系“t在a中可以替换x”可以递归地定义如下 如果a是原子公式,则t在a中可以替换x永远成立; ·如果a是b,则t在α中可以替换x当且仅当t在b中可以替换x ·如果a是b→c,则t在a中可以替换x当且仅当t在b和c中都可以替换x; ·如果a是νψyb,则t在α中可以替换x当且仅当y不在t中自由出现且t在b中可以替换x。 (10)关系“a是b的一个全称概括”是原始递归的。 证明:细节留给读者。 (11)集合{a:a是一个(一阶逻辑意义下的)形如(A1)、(A2)或(A3)的(命题逻辑) 公理}是原始递归的
第 2 节 语法的算术化 第 9 章 哥德尔第一不完全性定理 (6) 函数 f(n) = ♯(S n 0) 是原始递归的，因而，集合 {m : m 是一个数码} 是原始递归的。 证明: f(0) = ⟨0⟩ 且 f(n + 1) = ⟨S⟩^f(n)。 (7) 定义自然数上的二元关系“x 在 a 中自由出现”如下：x 是一个变元，a 是一个项 或公式，且 ♮x 在 ♮a 中自由出现。（显然，当 ♮a 为一个项时，自由出现和出现的意 思是一样的。）则关系“x 在 a 中自由出现”是原始递归的。 证明: x 在 a 中自由出现 当且仅当 Sb(a, x,⟨0⟩) ̸= a。 (8) 集合 {a : a 是一个闭语句} 是原始递归的。 证明: a 是一个闭语句 当且仅当 a 一个公式 且对任何 x < a，如果 x 是一个变元 则 x 不 在 a 中自由出现。 (9) 定义自然数上的三元关系“t 在 a 中可以替换 x”，如果 x 是一个变元，a 是一个公式， t 是一个项，且 ♮t 在 ♮a 中可以替换 ♮x。则关系“t 在 a 中可以替换 x”是原始递归 的。 证明: 首先请读者自己给出“a 是 ¬b”、“a 是 b → c”和“a 是 ∀yb”的定义，并验证它们 可以是原始递归的。 关系“t 在 a 中可以替换 x”可以递归地定义如下： • 如果 a 是原子公式，则 t 在 a 中可以替换 x 永远成立； • 如果 a 是 ¬b，则 t 在 a 中可以替换 x 当且仅当 t 在 b 中可以替换 x； • 如果 a 是 b → c，则 t 在 a 中可以替换 x 当且仅当 t 在 b 和 c 中都可以替换 x； • 如果 a 是 ∀yb，则t 在a 中可以替换x 当且仅当 y 不在t 中自由出现 且 t 在 b 中可以替换x。 (10) 关系“a 是 b 的一个全称概括”是原始递归的。 证明: 细节留给读者。 (11) 集合 {a : a 是一个（一阶逻辑意义下的）形如 (A1)、(A2) 或 (A3) 的（命题逻辑） 公理} 是原始递归的。 14
第9章哥德尔第一不完全性定理 第2节语法的算术化 证明:我们只验证(A1)的情形,即,a:=如a具有(→(r→σ)的形式且a和r为素公 注意:一个公式a是素公式当且仅当它的第一个符号不是左括号(。所以,“s是一 个素公式”是原始递归的 因此,a是形如(A1)的公理当且仅当(彐s,t<a),s和t是素公式,且 a=(^^→^→^s22 下面5条分别对应一阶逻辑的第2到第6组公理 (12)集合{a:a是形如ⅵrφ→κ的公理,其中t在φ中可以替换x}是原始递归的。 证明:(梗概)根据(9)我们只需原始递归地判断a具有x→φ的形式即可。而a具有 正确的形式当且仅当(x,p,t,b,c<a){a是b→c且b是vxp且c=Sb(p,x,t)且t在p中 可替换x];其中Sb(P,x,t)是第(5)条中定义的替换函数。 (13)集合{a:a是形如wr(a→B)→ara→ⅥrB的公理}是原始递归的 (14)集合{a:a是形如φ→ryp的公理,其中x不在a中自由出现}是原始递归的。 (15)集合{a:a是形如x≈x的公理}是原始递归的。 (16)集合{a:a是形如x≈y→9→y的公理其中φ是一个原子公式且y是将y中的 若干个x替换成y而得到的}是原始递归的。 证明:a具有正确的形式当且仅当(彐x,y,b,c,p,p<a)[a是b→c、b是x≈y、c是p→p且x和y是 p是一个原子公式、h(p)=h(p)且<h(p)(p)=(()V()=xA(p)=y)]口 总结一下从(10)到(16)我们就有 (17)集合{a:a是一个逻辑公理}是原始递归的。 证明:因为逻辑公理都是(1l)(16)中公式的全称概括 (18)令T为一个被集合X∈T所公理化的理论。根据公理化的定义,X必须是可判定 的,即集合Ⅹ是递归的。则谓词“b是一个T上的一个证明序列”是递归的 证明:“b是一个T上的一个证明序列”当且仅当b是一个有穷序列的哥德尔数、b≠1并 且k<h(b(b)k∈或(b)k是逻辑公理或(彐,j<k)(b)z=(b);→(b)k
第 9 章 哥德尔第一不完全性定理 第 2 节 语法的算术化 证明: 我们只验证 (A1) 的情形，即，α := ♮a 具有 (σ → (τ → σ)) 的形式且 σ 和 τ 为素公 式。 注意：一个公式 σ 是素公式当且仅当它的第一个符号不是左括号 (。所以，“s 是一 个素公式” 是原始递归的。 因此，a 是形如 (A1) 的公理 当且仅当 (∃s, t < a)，s 和 t 是素公式，且 a = (^s^→^(^t^→^s^)^)。 下面 5 条分别对应一阶逻辑的第 2 到第 6 组公理： (12) 集合 {a : a 是形如 ∀xφ → φ x t 的公理，其中 t 在 φ 中可以替换 x} 是原始递归的。 证明: （梗概）根据 (9) 我们只需原始递归地判断 a 具有 ∀xφ → φ x t 的形式即可。而 a 具有 正确的形式当且仅当 (∃x, p, t, b, c < a) [a 是 b → c 且 b 是 ∀xp 且 c = Sb(p, x, t) 且 t 在 p 中 可替换 x]；其中 Sb(p, x, t) 是第 (5) 条中定义的替换函数。 (13) 集合 {a : a 是 形如 ∀x(α → β) → ∀xα → ∀xβ 的公理} 是原始递归的。 (14) 集合 {a : a 是形如 φ → ∀xφ 的公理，其中 x 不在 a 中自由出现} 是原始递归的。 (15) 集合 {a : a 是形如 x ≈ x 的公理} 是原始递归的。 (16) 集合 {a : a 是形如 x ≈ y → φ → φ ′ 的公理 其中 φ 是一个原子公式且 φ ′ 是将 φ 中的 若干个 x 替换成 y 而得到的 } 是原始递归的。 证明: a具有正确的形式当且仅当 (∃x, y, b, c, p, p′ < a)[a 是 b → c、b 是 x ≈ y、c 是 p → p ′ 且 x 和y 是变元、 p 是一个原子公式、lh(p ′ ) = lh(p)、且 ∀j < lh(p)((p)j = (p ′ )j ∨((p)j = x∧(p ′ )j = y))]。 总结一下从 (10) 到 (16) 我们就有： (17) 集合 {a : a 是一个逻辑公理} 是原始递归的。 证明: 因为逻辑公理 都是 (11)–(16) 中公式 的全称概括。 (18) 令 T 为一个被集合 X ⊆ T 所公理化的理论。根据公理化的定义，X 必须是可判定 的，即集合 X 是递归的。则谓词“b 是一个 T 上的一个证明序列”是递归的。 证明: “b 是一个 T 上的一个证明序列”当且仅当 b 是一个有穷序列的哥德尔 数、b ̸= 1 并 且 ∀k < lh(b)[(b)k ∈ X 或 (b)k 是逻辑公理 或 (∃i, j < k)(b)i = (b)j → (b)k。 15