数理逻辑 (5) 哥德尔不完备性定理

语言的算术化 哥德尔编码。 令<x,y,z,…>=2x3y5y…。 定义#为逻辑符号到自然数上的函数： #()=1, #()=2, #(∨)=3，#(¬)=4, #(＝)=5,#(()=6,#())=7。 #(xi)=8+2i, #(ci)=9+2i。 #可以通过<>扩展为公式到自然数的一个单射。 在这个意义下，每一个公式都是一个自然数。

语言的算术化 对于每一个公式φ，＃（φ）称为φ的哥德尔数。 通过哥德尔编码，每一个证明是一个自然数的有穷序列。 因为每一步证明都是通过链接起来的两个公式，因此一个证明可以写成一个公式，因此一个证明也是一个自然数。 因此存在从φ到ψ的证明等价于存在一个自然数n,我们可以通过哥德尔编码把它解码成φ到ψ的证明。

不动点定理 假设对于每一个公式φ（x0,x1,…）以及自然数n0,n1,…,我们有： PA┠φ（n0,n1,…)当且仅当(ω,+,,<,0,1) ㅑφ（n0,n1,…)。 则令函数f(n,m)=#(#-1(n)(m))。右边的m应当理解为m次＋1。 那么f(n,m)=k可以被一个公式θ(x,y,z)定义。 对于任意一个公式β(z),令q=#(z(θ(x,x,z) β(z))), 令σ为z(θ(q,q,z) β(z))。则f(q,q)=#(σ)。 即PA┠z(θ(q,q,z) z=#(σ))。

不动点定理 因此PA┠β(#(σ)) z(θ(q,q,z) β(z))。 因为PA┠θ(q,q, #(σ))，因此σ┠β(#(σ))。

一个矛盾 假设对于每一个公式φ（x0,x1,…）以及自然数n0,n1,…,我们有： PA┠φ（n0,n1,…)当且仅当(ω,+,,<,0,1) ㅑφ（n0,n1,…)。 定义f(n)=1 如果PA证明¬#-1(n)(n),否则f(n)没有定义。则有一个公式φ （n）使得f(n)有定义当且仅当(ω,+,,<,0,1) ㅑφ（n)。 如果PA┠φ（#(φ)),则f(#(φ))有定义，因此PA证明¬φ（#(φ)）。 如果PA┠¬φ（#(φ))，则(ω,+,,<,0,1) ㅑ¬φ（#(φ))。因此f(#(φ)) 没有定义，则PA┠φ（#(φ))。

可表示性 一个关系R(x,y,z,…)是可表示的，如果存在一个公式φ（x,y,z,…）使 得对于任何自然数n0,n1,n2,…都有 PA┠φ（n0,n1, n2…)当且仅当R（n0,n1, n2…)。

原始递归函数 常数函数都是原始递归函数。 f(x)=x+1是原始递归函数。 f(x0,…,xi,…,xn)=xi原始递归函数。 如果f(x0,…,xn),g0,…,gn都是原始递归函数，则f(g0,…,gn)也是。 如果f(x0,…,xn),g(y,z,x0,…,xn)是原始递归函数，则函数h(0, x0,…,xn)=f(x0,…,xn),h(y+1)=g(y, h(y,x0,…,xn), x0,…,xn)也是。

一般递归函数 所有原始递归函数都是一般递归函数 如果g(x0,…,xn,y),h是一般递归函数且处处有定义，则函数 f(x0,…,xn)=h(min{y|g(x0,…,xn,y)=1}＝μ（y）g(x0,…,xn,y)=1)是 一般递归函数。 注意一般递归函数并非处处有定义。

递归关系 一个关系R(x,y,…)是递归的如果存在一个一般递归函数f使得 R(x,y,…)当且仅当f(x,y,…)=1. 如果一个集合的特征函数是递归的，则它称为递归的。 注意任何递归集合的补集也是递归的。

几个例子 加法，乘法，指数函数等常见数论函数都是原始递归的。 奇数集合，偶数集合都是原始递归的。 {#(φ)|ϕ∈PA}是原始递归的。 阿克曼函数是递归但不是原始递归的:

表示定理 定理：一个关系是可表示的当切仅当它是一般递归的。 证明：首先“证明”可以表示成原始递归函数。存在一 个证明可以表示成一个一般递归函数。则如果R是可 表示的，那么它就是一般递归的。 如果R是一般递归的，则按照归纳定义，可以证明它是 可表示的。 QED

一个例子 令Prov(x,y)为y是x的一个证明的编码。则关系 Prov(x,y)是一般递归的。因此有一个公式定义φ使 得PA┠φ(x,y)当且仅当Prov(x,y)。我们仍然用 Prov(x,y)表示φ。

算术公式的分层 Σ0的公式集合是最小的满足下述性质的公式集合A： (1)原子公式在A中；(2)如果φ(n)在A中，则n<mφ(n), n<mφ(n)都在A中;(3)如果φ,ψ在A中，则φ∨ ψ, ¬φ都在A 中。 Π0=Σ0=Δ0 一个公式φ是Σn+1的,如果存在一个Πn公式ψ(n)使得 φ↔nψ(n)。 一个公式φ是Πn+1的,如果存在一个Σn公式ψ使得 Φ↔¬ψ。 Πn+1∩Σn+1=Δn+1。

递归函数的逻辑刻画 定理：一个函数是一般递归的当且仅当它是Δ1可定义的。

不动点定理 前面关于不动点定理证明涉及函数均为一般递归函数，因此不动点 定理证明有效。 因此存在一个公式φ,PA┠φ↔¬yProv(#(φ),y)。

ω-协调性 一个理论T称为ω-协调的如果不存在公式φ（x）使得T┠nφ（n） 但是对所有的n, T┠¬φ（n)。 如果(ω,+,,<,0,1) ㅑT，则T是ω-协调的。

哥德尔第一不完备性定理 定理：如果PA是ω-协调的，则存在一个句子φ使得它和它的否定 都不能被PA证明。 证明：令φ使得PA┠``φ↔¬yProv(#(φ),y)。” 如果PA┠φ，则存在φ的一个证明，因此PA┠yProv(#(φ),y)。 如果PA┠¬φ，则PA┠yProv(#(φ),y)。由表示性定理，对于所有 n, PA┠¬Prov(#(φ),n)。则PA不是ω-协调的。 QED

罗瑟 1907-1989, USA 定理：如果PA是协调的，则存在一个句子φ使得它和它的否定都不 能被PA证明。 证明：令φ使得PA┠φ↔¬（y（Prov(#(φ),y) ∧z<y(¬Prov(#(¬φ),z))））。 如果PA┠φ，则存在φ的一个证明，因此存在一个自然数n编码φ 的证明。所以PA┠y （Prov(#(φ),y)∧z<y(¬Prov(#(¬φ),z))）。 如果PA┠¬φ，则存在一个自然数n编码¬φ的证明。因为PA 是协调 的，所有φ的证明必定大于n。因此PA┠y（Prov(#(φ),y)   z<y(Prov(#(¬φ),z))，矛盾！ QED

塔司基真值定理 定理：没有一个公式φ(x)使得对所有自然数n, (ω,+,,<,0,1) ㅑφ（n）当且仅当(ω,+,,<,0,1) ㅑ#-1(n)。 证明：如果存在这样一个公式。由不动点定理，存在一个自然数n 使得(ω,+,,<,0,1) ㅑ¬φ（n）当且仅当(ω,+,,<,0,1) ㅑ#- 1(n)。矛盾! QED

元数学与形式化 如果PA┠φ，则存在一个公式ψ它是PA的有穷子集的合取使得 ψ┠φ。这可以形式化为PA┠ψφ。因此由表示定理，我们有 PA┠yProv(#(φ),y）。 以及：PA┠``yProv(#(φψ),y) （y0Prov(#(φ),y0) y1Prov(#(ψ), y1)））”。

元数学与形式化(2) 引理：PA┠``yProv(#(φ),y)zProv(#(yProv(#(φ),y）),z）” 证明： 如果PA┠Prov(#(φ),x)，则PA``知道”x是一个证明，因此 PA┠zProv(#(Prov(#(φ),x）),z）。 从而PA┠``Prov(#(φ),x) zProv(#(Prov(#(φ),x）),z）”。 显然PA┠``Prov(#(φ),x) yProv(#(φ),y)”。 因此 PA┠`` zProv(#(Prov(#(φ),x）),z） zProv(#(yProv(#(φ),y）),z）”。 从而PA┠``Prov(#(φ),x)zProv(#(yProv(#(φ),y）),z）”。 因为x并不自由出现在结论中，我们有 PA┠``yProv(#(φ),y)zProv(#(yProv(#(φ),y）),z）” QED 注意这并不意味着PA┠φ yProv(#(φ),y)。

哥德尔第二不完备性(1) 令Con(PA)为¬yProv(#(0＝1),y)。 定理：如果PA是协调的，则PA不能证明Con(PA)。 证明：由不动点定理，存在一个公式φ使得 PA┠φ↔¬yProv(#(φ),y)。 则PA┠φ（yProv(#(φ),y) 0＝1）。 于是PA┠zProv(#(φ（yProv(#(φ),y) 0＝1),z))。 则PA┠z0Prov(#(φ）,z0)) z1Prov(#(yProv(#(φ),y)） 0＝ 1）,z1)) 因此PA┠z0Prov(#(φ）,z0)) (z1Prov(#(yProv(#(φ),y), z1) ¬Con(PA))))。

哥德尔第二不完备性(2) 因此 PA┠z0Prov(#(φ）,z0)) ¬Con(PA)。 如果PA┠Con(PA)，那么PA ┠ ¬ z0Prov(#(φ）,z0)) 。 因此PA ┠ φ 这意味着PA不协调。 所以PA不能证明Con(PA)。 QED.

哥德尔定理的一些推广 PA的任意递归协调扩张都不完备，实际上对于任何递归协调扩张理 论T，T不能证明Con(T)。 不完备性甚至可以扩张到非数论语言的递归公理系统，只要这些公 理系统足够强到“解释”PA。例如ZF。

习题 证明存在一个公式ϕ(x)使得(ω,+,,<,0,1) ㅑxφ （x),但PA并不证明xφ（x). 给出一个非ω-协调的协调理论。 证明PA┠Con(PA)  ¬yProv(#(Con(PA)),y)。即 Con(PA)是第二不完备性证明中的不动点。

阅读材料 《Godel‘s Incompleteness Theorems》，Raymond Smullyan, 1991. Oxford Univ. Press.