要证明 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 的不完全性证明。