定理7.6.1 
  要证明 Godel 不完全性定理,通常的办法是构造Z1的一个形式语句A,由于定理的前提是Z1是协调的,可以使用非负整数域N作为Z1的模型。语句AN中的解释是说:A本身是不可证明的。( 通常这种方法叫做 self-reference 办法,也可以说是对角线法的一种特殊形式) 该语句及其否定,在Z1中是不可证明的,否则产生矛盾。
  定理证明中的另一重要设置是所谓的 Godel 配数法,也就是编码。有很多种配数的方法,一种是先选择一个素数的集合P1, 基数大于 2 , 也可以是无穷的,作为表示公式的归纳形成过程; 令P2N - P1中 所有的素数全体,P2应该是无穷的。将P2一 一 分配给所有的L的符号,然后归纳地定义一个公式的 Godel 数。P1P2是递归集合,即是说,它们的特征函数是递归的。可以令P1 = { p1< p2 < … < …},P2 = {q1< q2< …< … }
  配数方法 任给一个公式A , [A] 表A 的Godel 数。
  (1) f(t) 是由Z1的语言L的符号集合LHP2上的一个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) [AB] = p1[A] p2f(∧)p3[B] , [A], [AB], [AB],[AB] 的定义类似。
  (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 + 11N上的一个关系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 的不完全性证明。