定理7.6.1
要证明 Godel 不完全性定理,通常的办法是构造Z1的一个形式语句A,由于定理的前提是Z1是协调的,可以使用非负整数域N作为Z1的模型。语句A在N中的解释是说:A本身是不可证明的。(
通常这种方法叫做 self-reference 办法,也可以说是对角线法的一种特殊形式) 该语句及其否定,在Z1中是不可证明的,否则产生矛盾。
定理证明中的另一重要设置是所谓的 Godel 配数法,也就是编码。有很多种配数的方法,一种是先选择一个素数的集合P1,
基数大于 2 , 也可以是无穷的,作为表示公式的归纳形成过程; 令P2是N
- P1中
所有的素数全体,P2应该是无穷的。将P2一
一 分配给所有的L的符号,然后归纳地定义一个公式的
Godel 数。P1及P2是递归集合,即是说,它们的特征函数是递归的。可以令P1
= { p1< p2 < … < …},P2
= {q1< q2< …< … }
配数方法 任给一个公式A
, [A] 表A
的Godel 数。
(1) f(t) 是由Z1的语言L的符号集合LH到P2上的一个1
- 1 onto 影射。
(2) u, v 是常项或变元,则 [u=v] = p1f(u)p2f(=)p2f(v)
;
(3) u1,u2,…, uk是常项或变元,B是k元谓词,则[B(u1,u2,…,
uk)] = p1f(B)p2f()p3f(u1)….pk+2f(uk)pk+3f()
(4) 如果u1,u2,…, uk, uk+1是常项或变元,F是k元函词,则[F(u1,u2,…,
uk, uk+1)] 的定义同(3)。
(5) [A∧B]
= p1[A]
p2f(∧)p3[B] , [ A],
[A∧B],
[A→B],[A B]
的定义类似。
(6) [ xA(x)]
= p1f( )f(x)p2[A(x)]
(7) [ xA(x)]
的定义同 (6)。
可定义性 为区别Z1中的常项0、1与N中的元素0、1。将Z1中的0、1
分别写为 01, 11 。在Z1
中定义新的常项 21 = 11 + 11, (n+1)1 = n1
+ 11 。N上的一个关系R(x1,x2,…,xn)
是Z1中可定义的,如果对任意的N中的元素组
k1, k2, ….kn, 有Z1的公式
A(x1,x2,…,xn) 使得
N│= R(k1,
k2, ….kn) 当且仅当Z1│-
A((k1)1,
(k2)1, ….(kn)1)
依递归函数的概念,给出N上的任意递归函数
r(x1,x2,…,xn) = xn+1, 可以定义N上的一个
n+1 元关系Rr(x1,x2,…,xn,
xn+1) 使得
N│= Rr(k1,
k2, ….kn, kn+1)当且仅当N│=
r(k1, k2, ….kn) = kn+1
引理7.6.1
证明 施归纳于递归函数定义的各条款。由于任一给定的递归函数都是有穷次使用这些条款得到,每一次使用都是可以用一个在Z1
中可证明的公式来定义,这样便可得到有穷条公式,它们给出了Rr
的在Z1 中的定义。
N上的一个关系是递归的,如果它的特征函数是一个递归函数,即R(x1,x2,…,xn)的特征函数h(x1,x2,…,xn)
定义为
h(k1, k2, ….kn) = 1 如果N│=R(k1,
k2, ….kn), 否则h(k1, k2, ….kn)
= 0
引理7.6.2
由于有了 Godel 配数,作为一个一阶理论,Z1中的一切形式对象及形式关系、形式操作,包括Z1的公式集合,公理集合,形式规则集合,包括形成规则、推理规则、形式证明的集合等等,在该编码下,都对应于N上的关系,通过逐步地、但十分繁琐的验证,可知它们都是N上的递归关系。以下罗列这些关系,注意这些都是N上的关于整数的关系,但由于它们都是递归的,在Z1中都可以表达。
(1) n 是L的一个符号。
(2) n 是一个常项。
(3) n 是一个变元。n是一个项。
(4) n 是一个公式。
(5) n 是一个公理。
(6) n 是一个公式,m 是一个变元,m 在 n 中自由出现。
(7) n 是一个语句。
(8) n 是一个形为A(x)
的公式,只含 x 作为自由变元,m 是一个常项,c 是以 m置换 n 中的 x 得到的公式。 即 c = [A(cm)]
, cm 是 m 所代表的常项,此关系可记为 Sub( n, m ) = c ,这是N上的一个递归关系。
(9) n 是一个证明。
(10) n 是语句 m 的一个证明,记为 Pr(n,m) 。
说明 由(10) ,在 N 上,集合 " n 是 Z1的一个定理 "是递归可枚举集合,它的形式定义为{n│ m
Pr(m, n) }。如果一阶理论T的定理集合是递归的,则称该理论为可判定的。
引理7.6.3
证明 由 Sub (x,y) 的定义,然后依 A(x) , t 的公式复杂性归纳证明。
引理7.6.4
这里我们给出对角线定理的证明。
令β(x) = (Sub(x,x))
。 (此时β(x)称为 (x)
的对角线形。)又令 m = [β(x)]
, 同时我们令 y =β(m)
, y 显然是Z1的一个语句。我们要证:
Z1│-ψ ([y])
。
在 Z1中有
ψ β(m) (Sub(m,m))
 (Sub(
[β(x)] , m ))
( 由于 m = [β(x)]
)
 ([β(m)])
 ([ψ])
证毕。
考虑公式 zPr(z,
x ) , 只含一个自由变元 x , 它在 N 中的解释为 " x 是不可证明的"。令其为引理4中的 (x)
,β(x) = (Sub(x,x))
= zPr(z,
Sub(x,x)) ,ψ
=β(m), m = [β(x)]
由于Z1│-
ψ ([ψ])
。 语句ψ在N中就可以解释为ψ自己是不可证明的。
我们来证ψ及 ψ在Z1中都是不可证明的。
如果Z1│-ψ,则由引理4,Z1│- zPr(z,[y])
, 则在N中找不到 [y]
的证明z , 所以y 在Z1中是不可证的,矛盾。
如果Z1│-
ψ,
则Z1│-
  zPr(z,[y])
, 在N中存在[y] 的一个证明
z , 因而Z1│-ψ,也矛盾。
这就完成了 Godel 的不完全性证明。
|