首先，哥德尔需要用一组符号来表达一个强的算术系统。哥德尔用了12个常量，9个变量。因为符号少了，表达就必然复杂。比如说，常量中的数字只有一个0，如何表达自然数？办法是常量中还有一个表示“直接后继”的符号s，意义一看就懂：s0表达0的直接后继数1。以此类推，ss0为2, sss0为3，等等。可以想象，如果数字大到成千上万，那该有多长。因此请不要考虑“可操作性”问题。数学证明只考虑原则上是否可行。
其次，哥德尔需要一套方法来将一个算术系统中所有的公式编码。请注意，不仅是总共21个常量和变量，而且要将所有由这些量组成的公式全部编码。这里，就表现出哥德尔的天才。
他为每个常量或变量指定一个数，称为“哥德尔数”(Godel Number)，12个常量的哥德尔数就是1-12，9个变量的哥德尔数分别是13，17，19以及它们的平方、立方。
然后就可以编码了。他的编码方法被称为“哥德尔编码(Godel Numbering)”。每个符号都有了哥德尔数，比如0的哥德尔数是6，=是5，那么公式0=0是不是就编码为656？不是，下面要解释为什么这样编码不行。
哥德尔编码是，用素数2，3，5，7，9，11……来表示符号的在公式中的顺序，而用符号的哥德尔数作为其指数。因此，0=0，第一个位置上是0，0 的哥德尔数是6，因此在这个位置上的0就是2的6次方，根据同样原则=是3的5次方，第二个0 是5的6次方，这个公式的哥德尔编码就是它们的乘积: 2的6次方乘3的5次方乘5的6次方，这个数是243,000,000。这就是这条公式的哥德尔数。
这么简单的一条公式就得用这么大的数字来编码，那么复杂的公式用上了13次方，17次方甚至19次方，不是大到一个编码要写上几十页纸？
没有错，是这样。再提醒一下，不要考虑可操作性，没有人真的去做这样复杂的编码，这只是原则上可行的方法。
不难想象，只要知道0的哥德尔数是6，= 是5，从243,000,000可以唯一恢复为64乘以243乘以15625，进一步恢复为2的6次方、3的5次方、5的6次方，最后恢复为0=0。显然，单纯以哥德尔数来代替哥德尔编码，比如以656来编码0=0，就不具有唯一可恢复性。
这样，有了一套可以表征一个算术系统的符号、有了一种编码方法，可以将那个系统每一个的公式都编码成一个整数，而且这个整数可以唯一地恢复为原有的公式。哥德尔又定义了一系列规则。下面是他的少部分定义，对下文必不可少：
(1) 定义1 : 替代(x, v, y)
其中v是一个变量。意思是用y替代公式x中的v。大家已经明白，这里的x，v和y, 都是哥德尔数。当然，替代之后仍然得到一个哥德尔数。
所以下面的替代(y, 17, y)表示 “ 用 y 来替代公式y 中的哥德尔数是17 的变量 ” ；替代(n, 17, n)表示 “ 用 n 来替代公式n 中的哥德尔数是17 的变量 ” 。替代(n, 17, n) 是一种有意思的替代，称为 “自替代 ” 。
为什么要用 替代(x, v, y) ？
因为在算术系统 , 证明的过程经常是替代过程 ，如
(a) ~(sa= 0) 公理
(b) ~(s1= 0) 将1替代(a) 式中的 a
~ 是逻辑否定词 ，s 是 “直接后继”符号 ，a 是变量，是自然数（正整数）
-
和 (b) 构成一公式 组合 ，它由两个哥德尔数 k, l 系列组成，记为 B (w) , w 是指k或 l 。
替代(x, v, y)时，替代后公式x 不再包括v ，替代之后结果称为封闭公式。
(2) 定义2： 证明(u, B)
意思是公式u是公式B的一个证明。再提醒一下，u和B也都是哥德尔数。
(3) 定义3： 可证(B):(存在一u) 证明(u, B)
意思是“存在一哥德尔数u，u是哥德尔数B的证明”。更简单的陈述是“哥德尔数B可证。”
所谓证明(u, B) 就是在B的一系列公式中找出最后的公式，这里是 B(l) 。
现有一对数 p(x, y) 是真的，如果 x 是公式 B 的变量的哥德尔数 和 y 是公式 B 的证明的哥德尔数。
考虑公式：
对所有的 y ~ p(x, y)
设上述公式的哥德尔数是 m , 考虑封闭公式：
G = 对所有的 y ~ p(m, y) , （此式是在上述公式中用 m 自替代 x 后得到）
上述公式表明 G 是一个真公式，因為它是由封闭公式得到。封闭公式的意思是 G 或~G 是一组公式逻辑推导的结果。
但是 G 又不是 m 的任何证明。
所以，G 是一个真公式，但它不能被证明。
本文是在吴道平先生CND原文上改写而成，在此致谢。
更多我的博客文章>>>
