上次提到了一个叫pq的形式系统，并且讨论了相容性是什么玩意，那么这次就来讲讲形式系统的另一个重要概念——完备性。

还记得我们给pq系统赋予的加法解释么？当时我说这个系统形式化了正整数的加法，那么笼统的说加法行不行？行，但是却不够准确，因为0=0+0这个简单的加法在pq系统里就没有办法表示，更别提非整数的加法了。像这样，如果在某个系统里不能表示我们想表示的所有结论，那么这个系统我们就称其为不完备的。就比如pq系统，其在加法的意义下是不完备的，但是在正整数加法的意义下却是完备的。可见完备与否取也决于我们想让一个形式系统有何等的能力。

那么回到最初的问题，数学家希尔伯特的想法是，弄出一个数学上的形式系统，这个形式系统足够强大，并且是相容的，是完备的，这样我们就可以机械的通过符号上的演算来得出各种定理与结论。由于它足够强大，所以我们可以从中获得非常多的定理。并且由于相容性的保证，我们得出的定理都是真的，又由于完备性的保证，所有我们想要得到的定理我们都可以得到。这大概就是所谓的让所有人的活在新闻联播的世界里的想法。不过希尔伯特提是提出来了，但是据坊间谣传说其本人相比于推导数学更喜欢帮人打官司，特别是遗产官司，这样可以在打完官司后大肆获利一笔。于是他本人并没在这上面花太多心思。不过这种想法听上去还是非常诱人，也吸引了不少人去研究，可惜此等美梦被哥德尔给打破了，哥德尔证明了：当有人活在新闻联播中的时候，必须有另外一群人活在今日说法之中，这就叫一国两制。一个足够强大的系统，不可能同时具有相容性和完备性。也就是说，一个系统如果足够强大，那么要么它能推出所有你想得到的结论，但是随之而来的其必定能推出另外一些你不想得到的——也就是错误的结论。（完备的但是是不相容的）要么其所有的结论都是正确的，但是其却必定不能推出你所有想要得到的所有结论。（相容的但却不是完备的）鱼和熊掌不能兼得。这就像电影社交网络的某个海报上写的那样——You Don’t Get To 500 Million Friends Without Making a Few Enemies.

在说哥德尔的证明之前先来问问大家一个问题吧：证明和计算是一回事么？对于我来说，之前一直认为这两件东西不是一回事，就像水和米饭虽然都是吃的但是不是一回事一样。不过哥德尔似乎不这么想，他认为计算和证明差不多，于是就有了哥德尔配数。那么举个例子来说明哥德尔配数是什么东西吧。首先我们来证明 4=1+3是pq系统中的定理：

1. – – q – p –               公理
2. – – – q – p – –           推理规则
3. – – – – q – p – – –   推理规则

这就是4=1+3在pq系统中的证明过程，如果这时我们用0代表q，00代表p，每个横杠用一个1来代表，那么整个证明过程可以写为：

1. 1101001                     公里
2. 111010011                 推理规则
3. 11110100111             推理规则

这个过程可以称之为数字化，而每个字母对应的数字就被称为哥德尔配数。要说明的是，配数的方法是不定的，只要保证一一对应就可以了，也就是说需要每一个数都能够被恢复成原始的字符串。此时我们就可以说证明是由一步步的算数运算得出的了（虽然这个运算的步骤和方法可能看上去莫名其妙）。这样我们就把证明转换为了数字上的计算。

那么在最后进入哥德尔不完备性定理之前，先揪出来一个之前说了无数遍却从没明确过的概念吧：一个足够复杂的系统。这是一个什么样的系统？这里的足够复杂是什么意思？详细的解释会比较麻烦，所以简单点来说就是：当这个系统可以形式化自然数时，这个系统就是一个足够复杂的系统。自然数是一个从小学起我们就开始接触的概念了，想必大家都认为这个很简单。但是即使是这样的系统，也不能做到两全，这听上去还真是可惜。除此之外，我们还要求这个系统里的所有能推出的结论都是一定能在有限步数中能推出的，这个应该好理解，毕竟我们需要这个系统给我们提供结论，如果他提供结论的过程有可能花费无限的时间（无论这个可能性有多低），那么其对我们而言就是没有意义的。另外虽然你可能觉得如果需要1亿年才能提供结论的话，虽说这是有限的，但是也没有意义。话虽如此，我们在这里并不限制推理所用的时间，100亿年也无妨，只要不是无限即可。

那么哥德尔最后就是证明了，下列四点不能同时成立：

1. 系统足够复杂
2. 系统相容
3. 系统完备
4. 系统的公设集递归

最后一点其实就是说的其推出结论只需要有限步骤，我们在这里用递归来表示有限步骤得结论这个性质。

下一篇就会切入哥德尔定理的证明，通过构造一个自指的命题，来证明希尔伯特的想法是不现实的，那么下次再说吧～