level 8
量子牛头
楼主
哥德尔定理是数理逻辑中的一个定理，1931年奥地利逻辑、数学家克尔特.哥德尔(Kurt Godel)发现并证明的，这个定理彻底粉碎了希尔伯特的形式主义理想。为理解这个定理及其意义，需要相当的数理逻辑和集合论知识。要把这些预备知识都在这里整理出来，工作太繁重了，这也就是我一直没敢动手写这篇东西的原因之一。这里仍然也不打算详细介绍这些东西，只是在必要的时候给些简单的说明，要想更深刻地理解，有兴趣的朋友可以自学相关课程。 哥德尔定理其实是两个定理，其中哥德尔第一不完备性定理是最重要、也是误解最多的，从这一定理的版本众多就可以看出。如： “如果一个形式理论T足以容纳数论并且无矛盾，则T必定是不完备的。” “任何一个相容的数学形式化理论中，只要它强到足以在其中定义自然数的概念，就可以在其中构造在体系中既不能证明也不能否证的命题。” “任何一个足够强的一致公设系统,必定是不完备的” 第二不完备性定理是第一定理的一个推论：“任何相容的形式体系不能用于证明它本身的相容性” 如果没有相关的知识基础，要理解这个定理真的是比较难。至于证明就更不容易看懂了。我偷点懒，跳过这些直接介绍其意义吧。 哥德尔定理是一阶逻辑的定理，在形式逻辑中，数学命题及其证明都是用一种符号语言描述的，在这里我们可以机械地检查每个证明的合法性，于是便可以从一组公理开始无可辩驳地证明一条定理。上世纪初，以希尔伯特为代表的形式主义派，希望能通过形式逻辑的方法，构造一个有关数论（自然数）的有限的公理集合，推出所有数论原理（完备性），且无矛盾（相容性），并以此出发构造整个形式主义的数学体系。而哥德尔第一不完备定理，粉碎了这一设想。这两个定理实际上表明，这样的公理系统要么不完备，要么有矛盾。数论的相容性为根茨（G.Gentaen，1909-1945）在1936年使用蕴涵着非演绎逻辑的超限归纳法所证明。 因而，该定理揭示在多数情况下，例如在数论或者实分析中，永远不能找出公理的完整集合。你可以在公理体系不断加入新的公理，甚至构成无穷的公理集合，但是这样的公理列表不再是递归的，不存在机械的判断方法判断加入的公理是否是该公理系统的一条公理。这对于计算机科学意义重大，在计算机语言中，一阶逻辑的定理是递归可枚举的，然而哥德尔第一不完备定理表明，无法编制这样的程序，通过递归的定理证明，可在有限时间内判断命题真假。彭罗斯的《皇帝新脑》中用停机问题描述了这一点，他甚至认为由此可知电脑永远不能超越人脑，甚至不可能达到人脑的水平。当然这点还不是定论，存在很大争议。 想说的简明一些，看来还是不行。还是结合对常见误解的分析，尽量来澄清模糊认识吧。 常见误解一：“所有的公理系统都是不完备的”。这是最常见的，甚至有人用这点来否定逻辑学，这是错误的。拿欧氏几何来说，就可以被公理化为一个完整的系统。 常见误解二：“所有包含到自然数的公理系统都是不完备的”。这个错误从上面的有些哥德尔定理的描述中都能看得出来。该定理仅假设公理系统能“定义”自然数。很多包含自然数的系统，例如“实数”和“复数”都有完备的公理化系统。 常见误解三：“因为不完备，我们永远无法证明一个公理系统无矛盾”。不，我们可以用其他方法证明，如上面提过的超限归纳法。其实该定理只表明我们不能从系统的内部证明相容性，不排除我们可以通过其他系统给出证明。例如，数论中的皮亚诺公理不能单独在数论范围内证明，但可在集合论中证明。 二 哥德尔定理主要还是在数学领域中应用的，至于在实际中的运用，很多都是基于错误的理解在盲目套用，论坛中的某些传教贴子中就多次出现。要想避免错误，还是应该真正的弄懂这个定理的意思，但矛盾的是，这的确需要相当的数学知识为基础，才可能，对于很多人来说，实在太难了。所以在文中我指出一些错误理解，进行了简单的分析，大家如果加以注意，就可以避免很多错误。下面我介绍一些实际运用的例子，只是我个人认为比较正确的应用，也许对帮助大家理解这个定理有帮助， 既然是数学定理，最直接的应用领域还是在数学里，尤其是数论。很多数论中的命题的证明，都需要用到哥德尔定理。这我就不多介绍了。这个定理表明，有些关于自然数的命题，本身可能是真命题，但是不能仅从自然数公理系统内证明或证否，需要其他的手段或者方法，如集合论等，才可以证明。曾经有人猜测，“哥德巴赫猜想”可能就是这样的一个命题。因此即便对于极为抽象和形式化的数学，数学家的直觉——也就是大量实践经验的积累——比纯形式的数学逻辑推理更基本，更可靠。但并不能就此说逻辑就毫无用处了，后者可以用来验证前者是否正确，也可以推导出一些新正确的命题，只是不能代表全部。而如前文所说，即便不能在形式系统内证明，还可以通过其他方法，或从其他系统中证明。另外，再次强调，“该定理仅假设公理系统能‘定义’自然数”，是一阶的逻辑定理，不要任意扩大。这里经常发生错误理解，还是建议有兴趣的朋友多了解掌握有关的基础知识。
2007年02月11日 06点02分
1
