[科普中国]-哥德尔不完全性定理

简介

哥德尔是奥地利裔美国著名数学家，不完备性定理是他在1931年提出来的。这一理论使数学基础研究发生了划时代的变化，更是现代逻辑史上很重要的一座里程碑。该定理与塔尔斯基的形式语言的真理论，图灵机和判定问题，被赞誉为现代逻辑科学在哲学方面的三大成果。哥德尔证明了任何一个形式系统，只要包括了简单的初等数论描述，而且是自洽的，它必定包含某些系统内所允许的方法既不能证明真也不能证伪的命题。

哥德尔是20世纪最伟大的数学家和逻辑学家。在逻辑学中的地位，一般都将他与亚里士多德和莱布尼兹相比；在数学中的地位，爱因斯坦把哥德尔的贡献与他本人对物理学的贡献相提并论。1952年6月美国哈佛大学授予哥德尔荣誉理学学位时，称他为“20世纪最有意义的数学真理的发现者”。在哥德尔所发现的被称为“20世纪最有意义的数学真理”当中，最杰出、最具有有代表性、最有震撼力的是哥德尔不完全性定理1。

内容第一定理任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。

第二定理如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。

引入悖论就是逻辑上的自相矛盾。

最古老的悖论是两千多年前的“说谎者悖论”，若你说它是假命题的话，就可推出它是真命题，反之亦然。其最简形式就是：

本命题是假命题

这种悖论属于语义悖论。悖论的种类还有循环悖论等。此处从略。

由来20世纪，一小部分聪明人才隐约觉察到，在悖论中有着一些深刻的数学理论。

事情要从崇尚理性的文艺复兴时期谈起，当时的学者如笛卡儿、莱布尼茨等都想创造一个理论解决一切问题。莱布尼茨甚至设想把逻辑学用数学符号表示，以后每逢争论，拿支笔一算就见分晓了。事实证明，莱布尼茨的对符号逻辑的建立起了很大作用。

莱布尼茨太超前了，没能完成他的夙愿。又过了200年，著名学者康托尔提出集合论，为统一数学提供了一线希望。

集合论的出现，为近代数学的发展提供了有力的工具。就在数学家踌躇满志的时候，集合论中出现了悖论。康托尔自己就发现了康托尔悖论（包含一切集合的集合是否存在？），更严重的是罗素悖论，其中涉及的是以自己为元素的集合。这被称为“第三次数学危机”。后来这种定义被公理排斥掉了，危机得以解决。

20世纪20年代，在集合论不断发展的基础上，大数学家希尔伯特向全世界的数学家抛出了个宏伟计划，其大意是建立一组公理体系，使一切数学命题原则上都可由此经有限步推定真伪，这叫做公理体系的“完备性”；希尔伯特还要求公理体系保持“独立性”（即所有公理都是互相独立的，使公理系统尽可能的简洁）和“无矛盾性”（即相容性，不能从公理系统导出矛盾）。

值得指出的是，希尔伯特所说的公理不是我们通常认为的公理，而是经过了彻底的形式化。他们存在于一门叫做元数学的分支中。元数学与一般数学理论的关系有点像计算机中应用程序和普通文件的关系。

希尔伯特的计划也确实有一定的进展，几乎全世界的数学家都乐观地看着数学大厦即将竣工。正当一切都越来越明朗之际，突然一声晴天霹雳。1931年，在希尔伯特提出计划不到3年，年轻的哥德尔就使希尔伯特的梦想变成了令人沮丧的噩梦。哥德尔证明：任何无矛盾的公理体系，只要包含初等算术的陈述，则必定存在一个不可判定命题，用这组公理不能判定其真假。也就是说，“无矛盾”和“完备”是不能同时满足的！这便是闻名于世的哥德尔不完全性定理。

误解由于哥德尔的第一条定理有不少误解。我们举出一些例子：

该定理并不意味着任何有意义的公理系统都是不完备的。该定理需假设公理系统可以“定义”自然数。不过并非所有系统都能定义自然数，就算这些系统拥有包括自然数作为子集的模型。例如，欧几里得几何可以被一阶公理化为一个完备的系统（事实上，欧几里得的原创公理集已经非常接近于完备的系统。所缺少的公理是非常直观的，以至于直到出现了形式化证明之后才注意到需要它们），塔尔斯基（Tarski）证明了实数和复数理论都是完备的一阶公理化系统。这理论用在人工智能上，则指出有些道理可能是我们能够判别，但机器单纯用一阶公理化系统断却无法得知的道理。不过机器可以用非一阶公理化系统，例如实验、经验。

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

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

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

理论上，哥德尔理论仍留下了一线希望：也许可以给出一个算法判定一个给定的命题是否是不确定的，让数学家可以忽略掉这些不确定的命题。然而，对可判定性问题的否定回答表明不存在这样的算法。（此处的算法为严格定义，要求对任何输入都能在有限时间内停机）

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

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

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

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

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

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

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

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

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

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

影响哥德尔不完全性定理一举粉碎了数学家两千年来的信念。他告诉我们，真与可证是两个概念。可证的一定是真的，但真的不一定可证。某种意义上，悖论的阴影将永远伴随着我们。无怪乎大数学家外尔发出这样的感叹：“上帝是存在的，因为数学无疑是相容的；魔鬼也是存在的，因为我们不能证明这种相容性。”

但是哥德尔不完全性定理的影响远远超出了数学的范围。它不仅使数学、逻辑学发生革命性的变化，引发了许多富有挑战性的问题，而且还涉及哲学、语言学和计算机科学，甚至宇宙学。2002年8月17日，著名宇宙学家霍金在北京举行的国际弦理论会议上发表了题为《哥德尔与M理论》的报告，认为建立一个单一的描述宇宙的大统一理论是不太可能的，这一推测也正是基于哥德尔不完全性定理。

有意思的是，在现今十分热门的人工智能领域，哥德尔不完全性定理是否适用也成为了人们议论的焦点。1961年，牛津大学的哲学家卢卡斯提出，根据哥德尔不完全性定理，机器不可能具有人的心智。他的观点激起了很多人反对。他们认为，哥德尔不完全性定理与机器有无心智其实没有关系，但哥德尔不完全性定理对人的限制，同样也适用于机器倒是事实。

哥德尔不完全性定理的影响如此之广泛，难怪哥德尔会被看作当代最有影响力的智慧巨人之一，受到人们的永恒怀念。美国《时代》杂志曾评选出20世纪100个最伟大的人物，在数学家中，排在第一的就是哥德尔。