哥德尔不完备性定理——从数学危机到哲学危机共12页

1、哥德尔不完备性定理一一从数学危机到哲学危机一、哥德尔不完备性定理的基本内容一个普遍公认的事实是，哥德尔不完备性定理在数理逻辑中占有极其重要的地 位，是数学与逻辑发展史中的一个里程碑。哥德尔关于形式系统的不完备性定理，首次发表在他的论文论数学原理及有 关系统中不可判定命题中。不完备性定理是关于不可判定命题存在的一般结果，如 果仅就算术系统而言，这个定理可以简单地表述为：定理：如果形式算术系统是 00无矛盾的，则存在着这样一个命题，该命题及其 否定在该系统中都不能证明，即它是不完备的。罗塞尔（Rosser）对上面的定理进行了如下改进：定理：如果形式算术系统是无矛盾的，则它是不完备的。具体说就是一一

2、定理：如果一个含有自然数论的形式系统 S是无矛盾的，则S中存在一个逻辑 公式A,使得在S中A是不能证明的，同时|A （|为否定连接词一一笔者注）也是 不能证明的。作为不完备性定理证明思想的一个关键之处在于映射原理的应用，哥德尔是通过一种十分新颖的映射形式来构造他的命题的。映射是数学研究中极为重要的一种研 究方法，其基本思想就是借助一一对应使得某一领域内的对象之间的某种关系得以在另一领域内的对象之间的关系得到表现。哥德尔的方法是：把算术系统（记为N）中的符号、表达式和表达式的序列都映射为数通过引进“哥德尔数”而实现了对象 的数化手续。这样处理的结果，对于数理逻辑和其他有关分支来说，在研究方法上就

3、提供了一种数字化工具，能够方便地把一些讨论对象（如符号、公式）转换为自然数 或自然数的函数，能够用自然数的理论来讨论有关问题。其次，哥德尔又通过“递归 函数”的引进证明了所有元理论中关于表达式的结构性质命题，都可以在算术系统中 得到表达。映射原理的应用和递归函数的引进，使元理论中的命题都映射为了算术系 统中的命题，算术系统也因此获得了元数学的意义。哥德尔在阐述自己的证明思想时说过：“我们可以注意到一个形式系统的公式 在形式上都表现为基本符号（变量、逻辑常项、括号或中断号）的一个有限序列，而 且人们容易精确地去指明基本符号的那些有限序列是有意义的公式和那些不是有意义 的公式。类似地，从形式的观点

4、看，所谓证明实际上就是公式的一个有限序列。对于 元数学来说，究竟用什么东西来作为基本符号当然是没有关系的。我们不妨就用自然 数来作为基本符号，如此，一个公式就是一个自然数的有限序列，而证明便是一个有 限的自然数序列的有限序列。据此，元数学的概念（命题）也就变成了关于自然数或 他们的序列的基本概念（命题），从而就可以（至少是部分地） 在（对象）系统本身 的符号中得到表示，特别是人们可以证明公式'、证明'、可证公式'等都可 在对象系统中加以定义。”哥德尔按照上述的证明思想，为不完备性定理的证明在对象系统内构造了这样一个命题G,使其元数学的意义为“G 是不能证明的”（作为元数

5、学的命题一一我们记 为G ,这里G为G的映射。）。哥德尔指出：一旦构成这样的命题，定理的证明就完成了，因为G正是需要的不可判定的命题。对此，这里仅作简单描述：前提：（a）凡是可证明的命题必然是真的（从直观上看，这是任何一公理系统的必然要求）。（B）命题的真理性在映射下保持不变（特别是这里的G和G是同真假的）结论1： G是不能证明的证明：用反证法 设G是可以证明的（a）G 为真，（B）f G为真；由G的意义tG是不能证明的。矛盾，证毕结论2： | G也是不能证明的。证明：由结论1可知，G是不能证明的，由 G的意义t G为真；（B）TG为真，Dft |G为假，（a）T | G是不能证明的，证毕。由

6、结论1和结论2可知G是不可判定的，也就是说系统是不完备的上述的证明，可以定性地概括如下：（1）一个包括初等数论的形式系统 P,如果这个系统是一致的，那么它就是不 完备的。这条称为第一不完备性定理。（2）如果一个包括初等数论的形式系统 P是一致的，那么它的一致性在本系统 中是不能得到证明的。这条称为第二不完备性定理。哥德尔不仅详细检验了他的论证，而且进一步断定：如果要证明一个系统 S 的 一致性，那么在元理论中所使用的推理工具绝不能弱于系统S中所使用的推理工 具。因此，可以看出，希尔伯特的方案，即用有穷观点证明自然数论甚至整个数学的一致 性是绝对行不通的。这一点也说明了形式系统有局限性。哥德尔定

7、理的证明思想来源于对悖论的分析，可见深入研究悖论问题对数学和逻辑学 都有着极为重要的意义。而哥德尔定理的另一个重大意义在于：系统一致性和完备性的不相容性，仅仅存在于数学系统中，还是普遍存在于所有系统中呢（自然科学系统， 社会科学系统，等等）？所以，哥德尔定理已经超越了数学和逻辑学，提出了无法回避的哲学问题；在 20 世纪对数学的基础研究中，对数学哲学基础的研究成了十分重要 的一个方面，和哥德尔定理的发现是有着直接关系的。二、悖论与数学史上的三次数学危机在漫长的数学发展史中，曾有过三次危机：无理数的发现；微积分的创立，集 合论的悖论。 这三次危机，使数学与逻辑学、哲学的联系不断加深，也使人类对各

8、种第5页事物的认识不断得到深化。因此，深入了解数学史上的三次危机有助于了解数学发展 的全貌。公元前 5 世纪，毕达哥拉斯学派的希帕索斯发现了等腰直角三角形的直角边与 斜边不可通约，从而导致了数学的第一次危机。对于这个问题，可以进行如下的证明：设等腰直角三角形斜边与一直角边之比为a：B，并设这个比已经表达成最小整数之比：a：B = 1 ：2 2 ；aV 2 = B （ 1）将上式（1）两端平方后得：B 平方二2a平方。由于B平方是偶数，B 必然 也为偶数；因为任一奇数的平方必是奇数，而a：B是既约的，所以a必然是奇数。B既是偶数，可以设为 B =2丫；于是B平方二4 丫平方二2 a平方。因此，a

9、 平 方二2 丫平方，这样a平方是个偶数，所以 a也是偶数了，但a同时又是奇数，这 就产生了矛盾。在毕达哥拉斯学派深信数是万物的本原，因此数是绝对和谐的不可能有任何矛 盾的，宇宙的一切现象都能归结为整数或整数比，所以希帕索斯的发现就成了荒谬的、 “反常”的事情，这个发现也因此构成了数学史上的第一次危机。这次危机，迫使数 学家去认识和理解自然数及其比（有理数）不能包括一切几何量，毕达哥拉斯学派也 被迫承认这一悖论并提出单子概念去解决这一悖论。单子概念是一种如此之小的度量单位，以至于本身是不可度量的却要保持为一种单位，这应该看成是企图通过无限来解决有限问题的最早努力。但是，毕达哥拉斯学派的努力却又

10、遭到了古希腊诡辩学派的著名代表芝诺的质疑，他认为：一个单子或 者是 0 或者不是 0，如果是 0，就是无穷多个单子相加也产生不了长度；如果不是0，那么无穷多个单子组成的有限长线段就应该是无限长的，无论如何都会产生矛盾。所 以，连同著名的芝诺悖论在内， 都被列为第一次数学危机的组成部 分。需要说明的是， 毕达哥拉斯学派的单子论，对哲学的影响远远超过了对数学的影响，黑格尔受单子论的启发把物质的运动解释为“在与不在的矛盾统一 运动本身就是矛盾”，而莱布尼茨在深入研究单子论的基础上创立了微积分并最早提出了建立数理逻辑的设想 他因此被看成是数理逻辑的创始人。可以说：与莱布尼茨相比，黑格尔把单子论引向 了

11、“神秘主义”和“诡辩论”，辩证法因此被称为“通向诡辩的桥梁”是有其道理的。希帕索斯悖论和芝诺悖论的出现，促使数学家从依靠直觉、经验转向了依靠证 明，从而导致了公理几何学与逻辑学的诞生。同时，哲学家也开始深入研究数学，从 数学中吸取建立哲学方法论的材料。如果说第一次数学危机使数学从“有限”进入了“无限”，那么第二次数学危 机则是“有限”与“无限”矛盾的集中反映。一般来说，人们把 18 世纪微积分 的诞 生以来在数学界出现的混乱局面称为第二次数学危机。虽然在整个 18 世纪微积分在各 个领域都得到了广泛应用，但微积分的理论基础却是含糊不清的“无穷小量”概念，因此遭到了来自各方面的责难与攻击。大家都

12、知道，英国的贝克莱主教对微积分的攻击是最为激烈的，他的名字几乎微积成了“反微积分”的代名词。贝克莱对微积分的批判，主要是依据牛顿所创立的 分，而不是莱布尼茨的微积分：牛顿是按照“流数法”来建立微积分的，而莱布尼茨是把单子论的哲学思想用于数学实践之中，因此两者还是有所区别的。贝克莱批判了 牛顿的许多论点，例如，在求曲边形的面积一文中，牛顿辩解说自己避免了“无 穷小量”，他给x以增量0,展幵（x + 0） n次方，减去x的n次方；再除以0,求出 x的n次方的增量与x的增量比，然后扔掉0的项，从而得到x的n次方的“流数”。 贝克莱说牛顿首先给 x 一个增 量，然后让它是 0，这违背了背反律，至于导数

13、被当作 y与x消失了的增量之比，即dx与dy之比；贝克莱认为dx与dy既不是有限量也不是 无限量，但又不是 “无”，dx与dy只能是“消失了量的鬼魂”。微积分中的“鬼魂 论”就是著名的“贝克莱悖论”。针对贝克莱悖论，柯西建立了严格的极限论，戴德 金则在实数 论的基础上证明了极限论的基本定理；此外，康托尔和魏尔斯特拉斯也加 盟了进来，为微积分寻找牢固的基础。普遍认为，由于严格的微积分理论的建立，上述的两次数学危机已经解决了。但事实上，建立严格的数学分析理论是以实数理论为基础的，而建立严格的实数理论又必须 以集合论为基础；在集合论的发展过程中，却又出现了一系列悖论，由此构成了更大的危机。人们把集合

14、论悖论的出现称之为第三次数学危机，应该说是很恰当的。从本 质上看，第三次数学危机是前两次数学危机的发展和深化，因为集合论悖论所涉及的问题更加深刻，涉及的范围也更广阔。在集合论悖论中，最著名的就是罗素悖论。为了避免过分的专业化，只能将罗 素悖论简单地加以描述：集合可以分为两种：一种是本身分子集，例如，一切概念所组成的集，由于它 本身也是一个概念，所以必为该集自身的一个元素。又如一切集合所组成的集合 也是 一个本身分子集。另一种非本身分子集，例如，自然数集合 N决不是某个自然数n。这 样，任给一集M,它不是本身分子集就是非本身分子集，不应有其他例夕卜；现在考虑一切非本身分子集的集"，试问

15、刀是哪一种集合？若设刀为本身分子集，则刀为自身 的一个元素，而刀的每一个元素皆为非本身分子集，所以刀也应该是一个非本身分子集；再设刀为非本身分子集，而一切非本身分子集皆在刀之中，所以刀也应该在其中， 因此刀又是一个非本身分子集；不管哪种说法都会导致矛盾。这就是罗素悖论。罗素悖论也称为“说谎者悖论”，就如同下面的悖论：古希腊时代一个克里特岛上的人说：“克里特岛上的人都是说谎者。”如果这 句话为真，那他自己（是克里特岛人）就是在说谎，所以他的话就是假的；如果这句 话为假，那就是克里特岛人不说谎，那他的话就是真的了。因此，无论怎么解释，都 会导致矛盾。不难看出，数学史上的三次危机，都是与悖论联系在一

16、起的。而悖论最终导致 了哥德尔不完备性定理的证明，这使现代数学不仅和逻辑学融为了一体，也和哲学有 了无法割舍的联系。三、不完备性定理与哲学1. 不完备性定理与辩证法哥德尔定理被许多人解释为是“系统与自身方法之间的矛盾”，完备性与一致 性的不相容、一致性与证明的不相容，促使数学家和哲学家都不得不思考：逻辑悖论， 真是辨证法所说的那种“对立统一”关系吗？辩证法如果它是逻辑的话，那这个逻辑的自身结构应该是什么呢？按照唯 物主义的解释，就是“自然界，人类社会，思维过程”，这种概括包括了三个系统： 自然界，人类社会，思维过程。那么，三个系统能够在辩证法的基础上彼此相容吗？ 如果每一个系统都遵循哥德尔定理

17、的话，那么辩证法所概括的“系统”也必然遵循这 个定理，结果必然是：辩证法本身就是非逻辑的悖论，而这个悖论的内在表现就是无 法使自身形式化，因此在“辩证法”中没有实质性的内容，它不能逻辑地判断一个命 题的“真假”，因此无法使人认识真理。在这里，辩证法遇到了无法解释的自身的悖论。所以，逻辑悖论问题不是“对 立统一”的表现，而是“逻辑自身不能证明自身”、“概念自身不能包括概念” 的表 现，目前是通过“系统扩张”或者“概念增加”来解决悖论的；但是“系统扩张”与 “概念增加”有没有极限呢？到了极限会是什么局面呢？这，似乎是向人类 智慧进行 挑战的极其复杂的问题。2. 数学的真理与哲学的真理塔尔斯基证明了

18、下面的定理：定理：对于无穷阶的形式语言来说，如果相应的元理论中可证明命题是无矛盾的，那么就不可能在元语言中构造出一个在约定意义下是充分的关于真理的定义。这是一个关于真理概念的可定义性的定理，值得注意的是塔尔斯基对定理的证 明与哥德尔在方法上有类似之处。真理与命题之间的矛盾，似乎是悖论的必然表现。这个表现的本质在于，证明 了“真理”本身的相对性，而“绝对真理”只能建立在体系完备的基础上，哥德 尔定 理证明这是不可能的。因此，当人追求“绝对真理”时，就已经偏离了追求“真理” 的正确道路，其结果必然是：发现“绝对真理”就是绝对的悖论。因此，20 世纪的哲学终于摆脱了“绝对真理”的庞杂体系，开始了自身的变革。虽然，哲学不再充当“科学的教父”，“意识形态的总司令”，但它自身却变的更加 接近真理而远离了谬误。这就是 20 世纪的数学，对人类文明最大的贡献，其影响也是 非常深远的。哥德尔的这个成果，在应用上确实有条件限制。在人文系统，这个定理的应用是有困难的。例如一个伦理系统，它的完备性性与无矛盾性是不