随笔
随笔，聊天
首先，哥德尔需要用一组符号来表达一个强的算术系统。哥德尔用了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 是变量，是自然数（正整数）
(?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) 。
(4) 不可证(B); ~可证(B). (加一个逻辑否定词 ~ )
表示哥德尔数B不可证。
将定义(1)具体化，比如说，有
(5) 替代(y, 17, y), 这条公式表示“用y来替代公式y中的哥德尔数17”，
在哥德尔的证明中，y的哥德尔数就是17。
然后用(5)替换(4) 中的B，就得到
(6) 不可证(替代(y, 17, y))
意思是“用哥德尔数y替代公式y中的变量17, 不可证”。这是一条形式命题，包含
变量。请记住17 恰好是y的哥德尔数，这一点在证明中非常关键。
当然这个命题仍然是一个哥德尔数。令这个哥德尔数为n, 然后再一次
运用规则，用n (也就是公式(6)的哥德尔数) 来替代y, 得到：
(7) 不可证(替代(n, 17, n)), “用哥德尔数n替代公式n中的变量17, 不可证”。
我们把这个公式命名为G:
(8) G =不可证(替代(n, 17, n))
上述公式表明 G 是一个真公式，因為它是由封闭公式得到。封闭公式的意思是 G 或~G 是一组公式逻辑推导的结果。
请注意思考一下，从(6)到(7)，我们作了什么运算？我们正是运用了替代，以n代替
了n 中的变量y，即把n中所有的17(y的哥德尔数)，以n代替。因此G等于是说，
(9) G = 替代(n, 17, n)
然而 (7)说“替代(n, 17, n)不可证”，然而(9)告诉我们，G又等于“替代(n, 17, n)”，
于是
(10) G =不可证(G)
G 是一个真公式，但它不能被证明。
本文是在吴道平先生CND原文上改写而成，在此致谢。
