哥德尔 G?del 不完备定理

什么是公理体系？读过高中的人，应该都知道公理体系。公理是无需证明而被认定为成立的命题。公理体系是指一组公理的集合。通过这些公理和基本的逻辑关系，可以推导出更多成立的命题，称为定理。最常见的，莫过于在欧几里德五条公理的基础上构建的整个欧式几何公理系统。从这五条公理出发，可以推出欧式几何的所有定理。

什么样的公理系统具有一致性？永远不允许“矛盾”出现的系统，就是一致的。矛盾就是，比如在某算术系统中，如果不同时允许1 > 2 和 1<=2，就说明该算术系统是“一致”的。

为什么需要一致性，或无矛盾的公理体系？设想一个公理体系，一会儿说“1+1=2”，一会儿又说“1+1不等2”，就不会有人把这个公理体系当回事。有矛盾的公理体系是无意义的。

什么样的公理系统具有完备性？如果一个系统中所有可以表达的命题，他们的真值都能被决定，要么真，要么假，那么我们就说这个系统是完备的。这里的完备，指的是“对于任何可在这个公理体系内描述的命题，都可以在这个公理体系内得到判定，要么是正确的，要么是错误的”。比如，在算术系统中，命题1>2 是假的，命题3>2是真的，命题1>3是假的。如果这样使用二阶逻辑，所有数字，和其比较符号构成的命题都能被决定真假，那么算术系统就是完备的。

在现代科学形成的过程中，通过定义一组公理再加上合理的逻辑推演，可以证明很多命题或结论。公理体系是当今数学研究和科学研究的基础，数学研究成果就是依赖于一组公理体系的推演，而其它科学研究除了依赖公理体系进行推演外，还需要通过系统的实验来进行验证。

以前数学家一直认为一个公理体系既是一致的，也是完备的。

哥德尔年仅25岁时发表的“哥德尔不完备定理”是针对公理体系的一项结论，它撼动了公理体系。这个定理说的是：一个足够复杂的公理体系，如果它是一致的，那么它就是不完备的。也就是说不可能同时具有“一致性”和“完备性”的公理系统。

通俗点说，一个没有矛盾的公理体系内，存在一些说不清楚对错的命题（这是指在这个体系内说不清楚，不是说永远都说不清楚）或者说命题是不可判定的。

什么命题具有如此神奇的性质呢？说白了就是悖论。我们可以轻易用自然语言构造出一个悖论，比如：“我说的话是假的。”如果这句话为真，那么它的内容又说它是假，互相矛盾。如果这句话为假，那么它的内容说明它不是假的，又互相矛盾。因此这句话既不真又不假，它是个悖论。这个著名的说谎者悖论其实已经触碰到了哥德尓不完备定理。

哥德尔定理的言外之意，有些命题是真的，但无法证明。这些无法证明的真的命题，可以作为公理。于是我们永远需要凭借直觉寻找新的公理。

只要一个系统表达力强到可以自指，那么就不可能是完备的，这对后来的人工智能领域产生了深远影响。

在计算理论里，哥德尔的发现启发了图灵证明停机问题：如果有一个程序P，P输入一个会终止的程序代码就无限循环，输入一个会无限循环的程序代码就终止；那么把P的代码输入给P，会发生什么？停机问题在图灵机上是不可判定问题。这是智能领域最早提出的决定性问题之一。