哥德尔不完全性定理

大家好，欢迎来到IT知识分享网。

第一定理

任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。（另外一种简单表达：一个不弱于初等数论的形式系统，如果一致则必不完全。）

第二定理

如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。（另外一种简单表达：这样的系统如果一致，则一致性无法再系统内证明。）

所谓初等数论，必然是包含了自然数及加减乘除等基本运算的一个形式系统。

而似乎所有的数学都包含了自然数以及加减乘除这种最简单运算。

要注意哥德尔理论只适用于较强的公理系统。“较强”意味着该理论包含了足够的算术以便承载对第一不完备定理证明过程的编码。

当然也有极少数例外，例如Presburger算术，它包括所有的一阶逻辑的真命题和关于加法的真命题。

完备性：对于一个公理系统，不需要加入其它的东西，那么通过该公理系统，就可以推导出任何命题的真假。

相容性：一个公理系统不能通过形式推演得到一个自相矛盾的命题，即该命题既是真又是假。

为什么可以说相容和完备只能取其一？

首先哥德尔定理适用于包含算术系统的一阶形式系统，对于这样的系统，哥德尔指出，一定有一个命题我们无法证明真伪。对于这样的系统，如果无矛盾，但我们无法再该系统内证明其无矛盾性。

这就指出了，如果我们想构造一个包含算术系统的完备的形式系统，即任何命题都能证明其真伪，那么系统内部就必然存在矛盾性。如果我们想保证一个包含算术系统的形式系统的无矛盾性，就必然不能保证其完备性。所以说相容性和完备性只能保证其一，但是需要记住，只适用于包含算术系统的形式系统。

至于相关的证明论述，可以查看其它相关资料，例如哥德尔的论文，我只是一个数理逻辑的初学者。实际上哥德尔构造出了一个命题，说“本公式不可证”，（一下一段话引用自知乎）

为表达对哥德尔的敬意,把表达了“本公式不可证”的系统内公式记作G。显然, G为真当且仅当G不可证, G为假当且仅当G可证。PM系统的可靠性是毋庸置疑的一没有 数学家会使用不可靠的系统。因此G是绝对不能为假的,因为这意味着G可证,即PM系统推出了假命题,这违反了可靠性。因此, G为真,但这恰好说明G不可证,这也就是说存在不可证的真公式,因此PM系统是不完全的。
以上是对第一不完全性定理的证明。

上述的是哥德尔第一不完全性定理,实际上还有一个第二不完全性定理。 这个第二定理是让希尔伯特非常头疼的定理，。众所周知，希尔伯特提出 了23个希尔伯特问题,其中第二 个问题就是算 术系统的一致性问题。一致性,即系统不会推出矛盾。矛盾能推出一切。事实上，上述定理的证明中隐含的使用了PM系统的一致性一如果PM系统不一 致,那它就能推出一切公式,也包括G。因此，上述定理实际上证明的是,如果PM是一致的,那么存在G为真但它不可证。因此,如果PM系统能证明它自身的一致性,那么实际上就已经证明了G为真,而这就违反了上述第一不完全性定理一PM证不出G。因此可以得出结论: PM无法证明自身的一致性。

这应该是非常简单的概述，并没有很严格的证明过程，是一个简单的介绍性的东西。

以下内容来自百度百科：

不完备性的结论影响了数学哲学以及形式化主义（使用形式符号描述原理）中的一些观点。我们可以将第一定理解释为“我们永远不能发现一个万能的公理系统能够证明一切数学真理，而不能证明任何谬误”

以下对第二定理的另一种说法甚至更令人不安：

如果一个（强度足以证明基本算术公理的）公理系统可以用来证明它自身的相容性，那么它是不相容的。于是，为了确立系统S的相容性，就要构建另一个系统T，但是T中的证明并不是完全可信的，除非不使用S就能确立T的相容性。举个例子，自然数上的皮亚诺公理的相容性可以在集合论中证明，但不能单独在自然数理论范围内证明。这对大卫·希尔伯特的著名的未解决的23个数学问题中的第二个给出了一个否定回答。

理论上，哥德尔理论仍留下了一线希望：也许可以给出一个算法判定一个给定的命题是否是不确定的，让数学家可以忽略掉这些不确定的命题。然而，对可判定性问题的否定回答表明不存在这样的算法。（图灵给出了该问题的否定回答，尽管他回答的是所有的数都是可计算的吗？这个问题，但是我们却可以通过编码使命题成为一个数，这样就使得可判定性问题与数的可数的可计算机）（此处的算法为严格定义，要求对任何输入都能在有限时间内停机）

要注意哥德尔理论只适用于较强的公理系统。“较强”意味着该理论包含了足够的算术以便承载对第一不完备定理证明过程的编码。基本上，这就要求系统能将一些基本操作例如加法和乘法形式化，例如在鲁宾逊算术Q中那样。有一些更弱的公理系统是相容而且完备的，例如Presburger算术，它包括所有的一阶逻辑的真命题和关于加法的真命题。

公理系统可能含有无穷条公理（例如皮亚诺算术就是这样），但要哥德尔定理生效，必须存在检验证明是否正确的有效算法。例如，可以将关于自然数的所有在标准模型中为真的一阶语句组成一个集合。这个公理系统是完备的；哥德尔定理之所以无效是因为不存在决定任何一条语句是否公理的有效算法。从另一方面说，这个算法的不存在正是哥德尔定理的直接结果。

另一个哥德尔定理不适用的特殊情况是：将关于自然数的所有语句首先按长度然后按字典顺序排序，并从皮亚诺公理集开始，一个一个遍历列表，如果发现一条语句既不能证明又不能否证，就将它作为公理加入。这样得到的系统是完备的，兼容的，并且是足够强大的，但不是递归可枚举的。

哥德尔本人只证明了以上定理的一个较弱版本；以上定理的第一个证明是罗梭(Russel)于1936年给出的。

基本上，第一定理的证明是通过在形式公理系统中构造如下命题

p = “此命题是不可证明的”来完成的。这样，它可以看成是说谎者悖论的一个现代变种。

如果公理系统是相容的，哥德尔证明了p（及其否定）不能在系统内证明。因此p是真命题（p声称它不可证明，而它确实不能），尽管其证明不能在系统内形式化。请注意将p作为公理加入系统并不能解决问题：扩大了的系统中会有另一个哥德尔语句出现。

罗杰·彭罗斯声称“可被机械地证明的”和“对人类来说看起来是真的”的这一区别表明人类智能不同于自然的无意识过程。这一观点未被普遍接受，因为正如Marvin Minsky所指出的，人类智能有犯错误和理解不相容和谬误句子的能力。但Marvin Minsky透露说哥德尔私下告诉他，他相信人类有一种到达真理的直觉方法，但因为跟计算机式的方法不同，人类可以知道为真的事情并不受他的定理限制。

对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点也可以作如下评论：我们其实不知道p是真是假，因为我们并不（也无法）知道系统是否是相容的。因此实际上我们并不知道系统之外的任何真理。我们所确知的只有这样一个命题：

要么p在系统内部无法证明，要么该系统是不相容的。这样的命题之前已经在系统内部被证明。实际上，这样的证明已经给出。