哥德尔定理及其哲学义蕴

《哥德尔定理及其哲学义蕴》由会员分享，可在线阅读，更多相关《哥德尔定理及其哲学义蕴（7页珍藏版）》请在金锄头文库上搜索。

1、哥德尔定理及其哲学义蕴1. 哥德尔其人 假如让人们列举出 20 世纪影响人类思想的十大伟人，恐怕爱因斯坦（Albert Einstein） 、图 灵（Alant Turing） 、哥德尔（Kurt Gdel）和凯恩斯（John Keynes）应榜上有名，事实上， 这四位也恰是 2002 年美国时代周刊上列出的“20 世纪震撼人类思想界的四大伟人”， 足见这四位大家思想之重要而深远。然而，对于物理学家爱因斯坦、理论计算机之父图灵， 以及经济学家凯恩斯的工作，一般人总还略知一二，但大多数人对作为数学家和逻辑学家 的哥德尔的思想就知之不祥，更知之不确了。 库尔特哥德尔 1906 年出生在摩拉维亚的布

2、尔诺城，是一个生活条件属中产阶级的奥地利 日尔曼裔家庭的第二个儿子，父亲是一家纺织厂的合伙经营人，母亲是受过良好教育的家 庭妇女。1924 年哥德尔入维也纳大学学习，最初主修物理和数学，后来在维也纳小组的激 励下开始学习逻辑。1930 年获哲学博士学位，1933 年获维也纳大学执教资格。1940 年迁 居美国任普林斯顿研究院研究员，1948 年加入美国国籍，1976 年退休，1978 年由于精神 紊乱死于拒绝进食造成的营养枯竭。 哥德尔的一生可以说是倾力献身基础理论研究的一生，他的学术贡献基本上是在数学、逻 辑和哲学领域。1929-1938 年间哥德尔作出数理逻辑领域三大贡献：证明一阶谓词演算

3、的 完全性；证明算术形式系统的不完全性；证明连续统假设和集合论公理的相对一致性，这 些结果不仅使逻辑学发生了革命，而且对数学、哲学、计算机和认知科学都有非常重大的 影响。特别是电子计算机诞生之后，哥德尔的不完全性定理的深刻性更加受到学界的关注。 只是稍稍出乎人们意料的是，作出这几个划时代结果后，自 1940 年以后，哥德尔除了继续 思考一些集合论问题，有 5 年时间热中相对论并得到一个受爱因斯坦赞赏的结果外，大部 分时间倾注了哲学问题的研究。他一生著述很少，极少公开演讲，只出版过一部著作，发 表文字不及 300 页，从未构造过任何完整的理论体系，甚至没有一个真正意义上自己的学 生，他的大部分思

4、想记录在手稿、私人通信和谈话记录中。 哥德尔曾被许多人看作带有神秘色彩的人物，一方面是因为他的不完全性定理的逻辑外衣 使大多数人难觅其思想的内在义蕴，另一方面也因为对于他的个性和精神状况流传着一些 坊间神话。但是可以肯定的，哥德尔不仅以精湛优雅的工作作出了令世人瞩目的科学贡献， 还以卓然深刻的思想为世人留下一笔丰厚的哲学遗产。哥德尔一生特立独行，始终如一地 将一流的人格品质、高远的科学鉴赏力、超凡的创造性和至为严谨的学风融为一体，倾其 全力献身基础理论研究工作，在这个充满竞争的世界上，他完全采取了一种“超然于竞争之 上”的生活态度。王浩曾将哥德尔与爱因斯坦相提并论，称他们是哲人科学家中的“稀有

5、品 种”。到目前为止，由一流数学家和逻辑学家组成的编委会负责编辑出版的哥德尔文集 已经于 1986、1990、1995 年出版了前三卷，其他各卷还将陆续出版，借助哥德尔文集 ， 我们必将逐步走进哥德尔的精神世界，进一步理解其思想的博大精深。 2. 哥德尔的不完全性定理 哥德尔思想最深刻地体现在为世人称道的不完全性定理之中。为了理解这一定理的深刻内 涵，我们首先了解一下一阶谓词逻辑的完全性问题。 我们知道，自然语言中包含着各种隐喻的成分和模糊之处，在使用中常常需要依赖于使用 语言的语境，用自然语言进行推理往往会产生歧义，带来意义的不确定性，因此在莱布尼 兹时代，逻辑学家们就希望引进一套意义单一明

6、确的人工符号，构造一套形式语言来严格、 清晰地整理日常推理和数学推理。为此目的，1879 年弗雷格（G.Frege）提出第一个初等逻 辑的形式系统（未完全形式化） ，1910 年罗素（B.Russell）在数学原理中给出了一阶 谓词逻辑的形式系统 PM，1928 年希尔伯特（D.Hilbert）和阿克曼（W.Ackerman）又引进了形式系统 HA，基本特征都是引进了一套人工语言代替自然语言。一般来讲，在一个形 式系统中，各种陈述都表示成有穷长度的符号串，系统的形成规则指明什么样的符号串是 合法的公式，一些符号串被当作公理。系统中还包括一系列推理规则，指明什么是系统中 定理的证明。一个证明就是

7、从公理出发对公式变形而形成的有穷长的公式序列，序列中的 每一个公式，或者是公理，或者是由在前的公式依照推理规则形成的公式，而且系统中每 一个定理都是这样经过有穷步骤得到的结果。到了 20 世纪 20 年代，这三个系统已经为逻 辑学家们所普遍接受。问题是，这样的形式系统是否能囊括所有的逻辑真理？于是，希尔 伯特 1928 年明确提出问题，证明一阶谓词逻辑系统具有完全性。 一年以后，哥德尔在他 1929 年完成的博士论文中证明，包括弗雷格、罗素和希尔伯特-阿 克曼的一阶谓词逻辑的形式系统，都具有一种语义完全性，即所有普遍有效式都可在一阶 谓词逻辑系统中作为定理得到证明，所谓普遍有效式，就是在一切论

8、域中都真的公式。这 一结果表明，一阶谓词逻辑系统在刻画那些逻辑真理方面是足够充分的。 既然一阶谓词逻辑具有如此强大的能力，逻辑学家们期望借助它构造整个数学的形式系统， 从而用形式化手段证明所有的数学真理。事实上，1900 年巴黎数学家会议上，希尔伯特遵 从“世界上没有不可知”， “人类理性提出的问题人类理性一定能够回答”的哲学信念，提出 23 个问题数学问题，其中的第二个问题就是建立整个数学的一致性（即无矛盾性或称协调性） ， 20 年代希尔伯特本人曾提出了一个使用有穷方法建立实数和分析的一致性的方案，称为希 尔伯特元数学方案。所谓有穷方法，粗略地说就是一套可操作的形式化程序，依照这样的 程序

9、可以一步一步地在有穷步骤内得到确切结果。1930 年获得博士学位之后，为了获得大 学授课资格，哥德尔开始沿着希尔伯特方案的路线着手解决希尔伯特第二问题。而不完全 性定理正是解决第二问题所得的结果。哥德尔最初是想寻此方案首先建立算术理论的一致 性，然后再建立相对于算术而言实数理论的一致性，但出乎意外的是，他得到了与希尔伯 特预期完全相反的结果，最终证明了形式算术系统的一致性不能用有穷手段证明。 哥德尔首先用一阶谓词逻辑的形式语言陈述皮亚诺算术的五条公理，同时将所形成的算术 形式系统记为 PA，在发表于 1931 年的论文论数学原理及有关系统中的形式不可判 定命题中，证明了如下两个重要结果： 哥德

10、尔第一不完全性定理：如果 PA 是一致的，则存在 PA 命题 P， P 在 PA 中不可证；如 果 PA 是 一致的，则 P 的否定P 在 PA 中不可证（1936 年罗塞尔（J.B.Rosser）证明可 以将条件“ 一致”改为“一致”） ，即系统 PA 是不完全的，这样的 P 称为不可判定命题（即 命题和命题的否定都不是系统的定理） 。 哥德尔第二不完全性定理：如果算术形式系统 PA 是一致的，则不可能在系统 PA 内部证 明其一致性。 哥德尔的两个不完全性定理可以更一般地表述为： 哥德尔第一不完全性定理：任何足以展开初等数论的数学形式系统，如果是一致的，就是 不完全的，即其中必定存在不可判

11、定命题； 哥德尔第二不完全性定理：任何足以展开初等数论的数学形式系统，如果是一致的，其一 致性在系统内不可证。 第二不完全性定理的另一种形式：任何足够丰富的数学形式系统，如果是一致的，那么它 不能证明表达它自身一致性的命题是定理。 哥德尔证明第一不完全性定理的思路是，先在形式系统中构造一个命题 P，这个命题形如 “P 在系统中不可证”， 进而指出，这个命题 P 和它的否定 P 都不是系统的定理，即这个 命题在系统中是不可判定的。依照经典逻辑，任何一个命题，或者为真，或者为假，二者 必居其一，二者只居其一，即命题和命题的否定必有一真，因此，系统中存在不可判定命 题，就意味着系统中存在真的但不可证

12、的命题。事实上，哥德尔构造的命题 P 身就是一个真的但在系统中不可证的命题。 哥德尔证明第二不完全性定理的思路是，既然有事实，如果系统 PA 是一致的，则 P 在系 统 PA 中不可证，那么表达这个事实的论证可以在系统 PA 中形式化。例如， “系统 PA 是一 致的”可以表示为 Con（PA） ，同时把“P 在系统 PA 中不可证”就用 P 表示，相应论证就表 示成： Con（PA） P 根据前述，如果 Con（PA）可证，则有 P 即 P 在系统 PA 中可证。这显然与第一不完全性定律相矛盾。 哥德尔定理第一次向世人澄清了“真”与“可证”概念的本质区别。由于一个命题在一个形式 系统中可证，

13、就意味着遵循推理规则，能够一步接着一步地在有穷步骤内完成证明过程。 但哥德尔指出，即使限制在皮亚诺算术这样狭小的数学范围内，要想用形式化的有穷手段 证明它的无矛盾性这一真理都是不可能的。换句话说，任何丰富到足以展开初等数论的形 式系统，至少会遗漏一个数学真理，数学形式系统不能囊括所有的数学真理。那么，能不 能添加更强的公理扩充原有的系统穷尽所有的数学真理呢？哥德尔说，不行！因为，对于 新扩充的系统还会有新的数学真命题在其中不可证， 继续扩充，情形依然如此。实际 上，除非你把这种扩张过程持续到超穷，否则这种系统连最简单的算术真理都不能穷尽。 哥德尔本人谈及定理证明过程时曾说过， “我在数论形式系

14、统中构造不可判定命题的启发性 原则是将可证性和相对应的高度超穷的客观数学真理概念相区分”。看来，可证数学命题和 数学真理之间永远隔着一个超穷距离，仅仅使用有穷方法甚至没有希望逼近它。正如哥德 尔所说， “数学不仅是不完全的，还是不可完全的”，这一点也恰是哥德尔定理最深刻的哲学 义蕴。 3. 哥德尔定理在不同语境下的版本 显然，哥德尔定理与数学家的最初期望相去甚远，因为，一方面人们期望数学形式系统囊 括所有数学真理，一方面又分明知道总有数学真理不可证；一方面经验和直觉告诉人们数 学是一致的不含矛盾的，理性又教导人们数学不能证明它自身的一致性。因此，定理发现 之后，人们不得不重新调整自己的思维方式

15、。著名数学家外尔（H.Weyl）当时曾就此感慨 到， “上帝是存在的，因为数学无疑是一致的；魔鬼也是存在的，因为我们不能证明这种一 致性。 ”这段话形象地道出了当时处于两难境遇的数学家的困惑。甚至有人把哥德尔定理的 意义进一步引申：宇宙给了我们一种选择，就人类认知而言，我们要么拥有一本正确的但 却是极不完整的小书，要么拥有一本完整的但缺乏内在和谐的大书，我们可以选择完整也 可以选择和谐，但鱼和熊掌不可得兼。在我们看来，这些说法不过是哥德尔定理带给人们 的某些启示，事实上，哥德尔定理自图灵机概念诞生之后更加凸现其深刻和意义深远。 1930 年代，哥德尔、丘奇（A.Church） 、克林尼（G.J

16、.Kleene） 、图灵等一批数学家开始对 直观的“算法可计算”概念的数学刻画进行探索，相继提出了 -可定义、递归函数和图灵机 概念，并给出了影响广远的丘奇-图灵论题：一切算法可计算函数都是递归函数，一切算法 可计算函数都是通用图灵机可计算的函数，或者说，每个算法都可在一台通用图灵机上程 序化。虽然几种数学刻画是等价的，但是哥德尔最为赞赏图灵机概念，这其中最为重要的 是，图灵机概念第一次澄清了形式系统的真正内涵形式系统不过是一种产生定理的机 械程序，或者说图灵机的工作程序就是数学家在形式系统中进行工作的程序。有了图灵机 概念以后人们开始期望造出能证明所有数学定理的机器，但是，既然图灵机就等价于形式 系统，那么形式系统的局限就是图灵机的局限。于是，哥德尔的第一不完全性定理在给出 图灵机概念之后就有了如下几种等价说法： （1）没有数学形式系统既是一致的又是完全的。（2）没有定理证明机器（或机器程序）能够证明所有的数学真理。 （3）数学是算法不可完全的。 （4）数学是机器程序不可穷尽的。 （5）停机定理没有任何图灵机程序能判定