第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