第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