今天终于初步明白了哥德尔定理的证明思想。

哥德尔第一不完备定理的内容是：“任何一个相容的数学形式化理论中，只要它强到足以在其中定义自然数的概念，就可以在其中构造既不能证明也不能证否的命题。”

哥德尔这一定理解决了希尔伯特的第二问题。希尔伯特规划的思想是，对于任何定义好的数学领域，去找一条足够广泛的公理和步骤法则的表，是的所有适合于该领域的正确的数学推理的形式都可以编入。

现在来看哥德尔的证明思想。

• 首先，哥德尔把行驶系统的个别步骤法则以及不同公理的使用实际地编码成算术运算。就相当于图灵机中把一个特定的指令编码成唯一的01串。这里比如说把&、|、~等符号编码成01101 …等等，这样一个关于变量w的命题譬如~P就可以被编码成一系列的01串。适当选择编码方案（当然很复杂很困难但却不是主要的思想），可以使每一个命题都有唯一的编号。当然有些命题显然是没有实际意义的，但不影响。由此可以设所考察的形式系统S中关于w的第n个命题是P_n(w).
• 然后，考虑到每一个证明都是由一系列命题按一定顺序组合得到的，我们可以设所有的证明的集合是[II],[II]_n是其中第n个证明。

准备工作都做好了，现在真正有趣的地方来了。

命题f：[II]中不存在证明P_w(w)的元素。

注意到，这个命题也是关于w的一个命题，所以也有一个唯一的编号。由于编码方式不唯一，总会有一种编码方式使得命题f实际上就是P_w(w)!也就是说，关于w的第w条命题P_w(w)说的是，不存在P_w(w)的一个证明。（这就好像以前听烂的“我说的话是谎话”，“理发师只给不给自己理发的人理发他该不该给自己理发”。但不同的是由这些悖论我们什么也得不到，而哥德尔这个构造却证明了不完备定理。） 我们假设P_w(w)是可以在S中找到证明的，即P_w(w)为真。这时就出现了矛盾：它的内容恰恰是S中不存在它的证明。由此P_w(w)不存在证明，将是错的，就是说它存在S中存在证明。但我们假设S是强到足够包含算术的系统，显然不容许我们证明本身是错误的证明。最后的结论只能是，P_w(w)为真，但在S中无法证明。

~P_w(w)呢？由于P_w(w)为真，它必定为假。所以在S中也无法给出~P_w(w)的证明。 至此，我们在S中找到了命题P_w(w),它既不能被证明也不能被证伪。

参考资料：《皇帝新脑》