| 词条 | 哥德尔不完备性定理 |
| 释义 | § 哥德尔不完备性定理 § 正文 发表于1931年。它包括两个定理： 哥德尔 第一不完备性定理 设S 是包含算术系统在内的任意形式系统,则存在命题F使得F和它的否命题塡F都在S中不可证。这里的F也称为系统S内的不可判定句。 第二不完备性定理 在上述形式系统 S中不能证明它本身的协调性。 K.哥德尔最初想证明希尔伯特计划中企图证明的形式数论系统和形式实数系统的协调性。他的想法是：①证明形式数论系统的协调性；②证明形式实数系统对于形式数论系统的相对协调性。他认为①是容易证明的，因此首先考虑②的证明。在考虑②的过程中发现了第一不完备性定理，证明的方法主要是对角线方法。 希尔伯特想要在各个古典数学形式系统里，用有穷方法证明本系统的协调性。第二个完备性定理证明了即使在形式数论系统中希尔伯特计划也无法实现，需要另谋其他出路。希尔伯特猜测只要适当选择比系统内所含有工具更强的工具就可以证明形式数论系统的协调性。果然在1936年G.根岑实现了他的猜测。 哥德尔给出的上述S 内不可判定命题的直观意思是“F在S内不可证”，即它的直观是逻辑性质的。后来J.帕里斯给出了一个S内不可判定的命题,它是有明显的数学性质的真命题。在裴里斯之后一些数学家们又做出了不少有意义的工作，其中H.弗里德曼的工作很受人注意。 第一不完备性定理的证明方法对递归论的早期发展有很大影响。 § 从无限开始 第一个面对无限的现代思想家是伽利略(Galileo)。他试图用圆来解决。最后，他意识到，圆由一个无限多个无穷小多边形组成。但只要他这样做，他意识到这打开了一个可怕的不合逻辑的悖论。现在用一个无比尖锐的铅笔，从中心画无限多条锐利直线。他们中有无限多条，内圆应该足够。但现在延长这些直线一直交到外圆。现在，这些线是发散的……这意味着当你到达外圆，如果你仔细的看，会有空隙。还不够多。伽利略只是说：这讲不通。如果有无限多，那应该够了！在这一点上，他说：我们只是不明白无限！也许上帝可以，但我们有限的大脑，不能。 1866 年 2 月 6 日 ，不满 22 岁的玻尔兹曼完成了他的博士论文： “ 力学在热力学第二定律中的地位和作用 ” 。在论文中，他利用原子运动轨道闭合的假设，将熵的表示与力学的最小作用原理直接联系起来，试图从纯力学的角度证明热力学第二定律。 康托尔发表了：关于无穷大的第一篇突破性论文。如果先前无穷只是一个没完的、模糊的数，康托看到了全新的世界。康托尔做了新的一步，他说：一可以加一。好，为什么我不能无穷加无穷？ 悖论就是逻辑上的自相矛盾，似是而非，似非而是。注意，必须是逻辑上不同才是悖论。“先有鸡还是先有蛋”这句话就不是悖论，因为这个问题的关键在于如何定义鸡和蛋，和逻辑和悖论没一点关系。 最古老的悖论是两千多年前克里特岛的“说谎者悖论”，若你说它是假命题的话.就可推出它是真命题，反之亦然。其最简形式就是：本命题是不可证明的。 这种悖论属于语义悖论，悖论还有循环悖论等。此处从略。 § 哥德尔不完全性定理的由来 虽然与悖论打了几千年交道，可数学家们不觉得他们可怕，因为他们与数学无关。直到20世纪，一小撮聪明人才隐约觉察到，在悖论中有着一些深刻的数学理论。 事情要从崇尚理性的文艺复兴时期谈起，当时的学者如笛卡儿、莱布尼茨等都想创造一个理论解决一切问题。莱布尼茨甚至设想把逻辑学用数学符号表示，以后每逢争论，拿支笔一算就见分晓了。事实证明，莱布尼茨的对符号逻辑的建立起了很大作用。 莱布尼茨太超前了，没能完成他的夙愿。又过了200年，著名学者康托尔提出集合论，为统一数学提供了一线希望。 集合论的出现，标志着数学的诞生。有了集合论，人们就没必要（也不能）发明更广层次的理论了。 就在数学家踌躇满志的时候，集合论中出现了悖论。康托尔自己就发现了一个（包含一切集合的集合是否存在？），更严重的是罗素悖论，其中也出现了以自己为元素的集合。两个悖论搅得数学王国不得安宁，史称“第三次数学危机”。后来这种定义被公理排斥掉了，数学王国又恢复了平静。不过很快，人们就意识到，这不过是“虚假的繁荣”。 不识庐山真面目，只缘身在此山中。这两句话深刻地说明，只有站在更高的层次，才能看到更多的“风景”。那么，我们有望看到整个数学的风景吗？ 20世纪20年代，在集合论不断发展的基础上，大数学家希尔伯特向全世界的数学家抛出了个宏伟计划，其大意是建立一组公理体系，使一切数学命题原则上都可由此经有限步推定真伪，这叫做公理体系的“完备性”；希尔伯特还要求公理体系保持“独立性”（即所有公理都是互相独立的，以保持公理系统最简洁）和“无矛盾性”（即相容性，公理和公理之间不能是自相矛盾的）。 值得指出的是，希尔伯特所说的公理不是我们通常认为的公理，而是经过了彻底的形式化。他们存在于一门叫做元数学的分支中。元数学与一般数学理论的关系有点像计算机中应用程序和普通文件的关系。 希尔伯特是个乐观主义者，他的计划也确实有一定的进展，几乎全世界的数学家都乐观地看着数学大厦即将竣工。正当一切都越来越明朗之际，突然一声晴天霹雳。1931年，在希尔伯特提出计划不到3年，年轻的哥德尔就使希尔伯特的梦想变成了令人沮丧的噩梦。哥德尔证明：任何无矛盾的公理体系，只要包含初等算术的陈述，则必定存在一个不可判定命题，用这组公理不能判定其真假。也就是说，“无矛盾”和“完备”是不能同时满足的！这便是闻名于世的哥德尔不完全性定理。 § 哥德尔不完全性定理的影响 哥德尔不完全性定理一举粉碎了数学家两千年来的信念。他告诉我们，真与可证是两个概念。可证的一定是真的，但真的不一定可证。某种意义上，悖论的阴影将永远伴随着我们。无怪乎大数学家外尔发出这样的感叹：“上帝是存在的，因为数学无疑是相容的；魔鬼也是存在的，因为我们不能证明这种相容性。” 但是哥德尔不完全性定理的影响远远超出了数学的范围。它不仅使数学、逻辑学发生革命性的变化，引发了许多富有挑战性的问题，而且还涉及哲学、语言学和计算机科学，甚至宇宙学。2002年8月17日，著名宇宙学家霍金在北京举行的国际弦理论会议上发表了题为《哥德尔与M理论》的报告，认为建立一个单一的描述宇宙的大统一理论是不太可能的，这一推测也正是基于哥德尔不完全性定理。 有意思的是，在现在十分热门的人工智能领域，哥德尔不完全性定理是否适用也成为了人们议论的焦点。1961年，牛津大学的哲学家卢卡斯提出，根据哥德尔不完全性定理，机器不可能具有人的心智。他的观点激起了很多人反对。他们认为，哥德尔不完全性定理与机器有无心智其实没有关系，但哥德尔不完全性定理对人的限制，同样也适用于机器倒是事实。 哥德尔不完全性定理的影响如此之广泛，难怪哥德尔会被看作当代最有影响力的智慧巨人之一，受到人们的永恒怀念。美国《时代》杂志曾评选出20世纪100个最伟大的人物，在数学家中，排在第一的就是哥德尔。 § 对哥德尔定理的一些误解 由于哥德尔的第一条定理有不少误解。我们举出一些例子： 该定理并不意味着任何有意义的公理系统都是不完备的。该定理需假设公理系统可以“定义”自然数。不过并非所有系统都能定义自然数，就算这些系统拥有包括自然数作为子集的模型。例如，欧几里得几何可以被一阶公理化为一个完备的系统（事实上，欧几里得的原创公理集已经非常接近于完备的系统。所缺少的公理是非常直观的，以至于直到出现了形式化证明之后才注意到需要它们），塔斯基（Tarski）证明了实数和复数理论都是完备的一阶公理化系统。这理论用在人工智慧上，则指出有些道理可能是我们能够判别，但机器单纯用一阶公理化系统断却无法得知的道理。不过机器可以用非一阶公理化系统，例如实验、经验。 § 讨论和推论 不完备性的结论影响了数学哲学以及形式化主义（使用形式符号描述原理）中的一些观点。我们可以将第一定理解释为“我们永远不能发现一个万能的公理系统能够证明一切数学真理，而不能证明任何谬误” 以下对第二定理的另一种说法甚至更令人不安： 如果一个（强度足以证明基本算术公理的）公理系统可以用来证明它自身的相容性，那么它是不相容的。于是，为了确立系统S的相容性，就要构建另一个系统T，但是T中的证明并不是完全可信的，除非不使用S就能确立T的相容性。举个例子，自然数上的皮亚诺公理的相容性可以在集合论中证明，但不能单独在自然数理论范围内证明。这对大卫·希尔伯特的著名的未解决的23个数学问题中的第二个给出了一个否定回答。 理论上，哥德尔理论仍留下了一线希望：也许可以给出一个算法判定一个给定的命题是否是不确定的，让数学家可以忽略掉这些不确定的命题。然而，对可判定性问题的否定回答表明不存在这样的算法。 要注意哥德尔理论只适用于较强的公理系统。“较强”意味着该理论包含了足够的算术以便承载对第一不完备定理证明过程的编码。基本上，这就要求系统能将一些基本操作例如加法和乘法形式化，例如在鲁宾逊算术Q中那样。有一些更弱的公理系统是相容而且完备的，例如Presburger算术，它包括所有的一阶逻辑的真命题和关于加法的真命题。 公理系统可能含有无穷条公理（例如皮亚诺算术就是这样），但要哥德尔定理生效，必须存在检验证明是否正确的有效算法。例如，可以将关于自然数的所有在标准模型中为真的一阶语句组成一个集合。这个公理系统是完备的；哥德尔定理之所以无效是因为不存在决定任何一条语句是否公理的有效算法。从另一方面说，这个算法的不存在正是哥德尔定理的直接结果。 另一个哥德尔定理不适用的特殊情况是：将关于自然数的所有语句首先按长度然后按字典顺序排序，并从皮亚诺公理集开始，一个一个遍历列表，如果发现一条语句既不能证明又不能否证，就将它作为公理加入。这样得到的系统是完备的，兼容的，并且是足够强大的，但不是递归可枚举的。 哥德尔本人只证明了以上定理的一个较弱版本；以上定理的第一个证明是罗梭(Russel)于1936年给出的。 基本上，第一定理的证明是通过在形式公理系统中构造如下命题 p = “此命题是不可证明的”来完成的。这样，它可以看成是说谎者悖论的一个现代变种。 如果公理系统是相容的，哥德尔证明了p（及其否定）不能在系统内证明。因此p是真命题（p声称它不可证明，而它确实不能），尽管其证明不能在系统内形式化。请注意将p作为公理加入系统并不能解决问题：扩大了的系统中会有另一个哥德尔语句出现。 罗杰·彭罗斯声称“可被机械地证明的”和“对人类来说看起来是真的”的这一区别表明人类智能不同于自然的无意识过程。这一观点未被普遍接受，因为正如Marvin Minsky所指出的，人类智能有犯错误和理解不相容和谬误句子的能力。但Marvin Minsky透露说库尔特·哥德尔私下告诉他，他相信人类有一种到达真理的直觉方法，但因为跟计算机式的方法不同，人类可以知道为真的事情并不受他的定理限制。 对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点也可以作如下评论：我们其实不知道p是真是假，因为我们并不（也无法）知道系统是否是相容的。因此实际上我们并不知道系统之外的任何真理。我们所确知的只有这样一个命题： 要么p在系统内部无法证明，要么该系统是不相容的。这样的命题之前已经在系统内部被证明。实际上，这样的证明已经给出。 § 解集的概念。 (一) 集合 “集合”或集的描述：集这个概念，是不可以精确定义的数学基本概念之一，故只能作描述：凡具有某种特殊性质对象的汇集，其总合被称为集。 例：一组数(可能是无限的)，一群人，一栏鸡蛋。 在作数学上具体研究时，组成集的个体，被称为“元”的其他特殊属性，如鸡的特性，人的特性，数的特性，都不再考虑。于是，一个集合就被抽象成A，它的元被抽象成x。 我们有x 属于 A 我们也规定：A 不能属于 A 即A不能是A自己的一元，这个规定不是不合理的，例如，所有的书所组成的集不是书！ 所以所有书的集合不能是这个集合的一元。 A 的某一部份B也可自行构造出一集，被称为A之“子集”。 我们有B 含于 A 特殊情况：B可以等于A，B也可以没有元素，被称为“空集”，我们称这样两种情况叫住 A的“平凡”子集。 定义：对等 设A，B分别为两个集，如果A和B之间能建立1-1的对应关系，则我们称：A 对等于 B 反之亦然。 对等是集与集之间最基本的关系。若A和B都含有限个元，则两集之间要对等，当且仅当二者的元的数目相等。 如果A和B都是无限的，则也能/不能建立对等关系，如两个无限数列A和B： A：1，2，3，。。。 B：2，4，6，。。。 就能建立1-1对应，故A 对等于 B 可以证明，任何两个无限数列的集合都能对等。 但是，有些无限集之间却不能对等。 例：设实数轴0到1之间的所有有理数所组成的集为R，又设0到1之间所有的无理数所组成的集为I，则可证明(略)： 1.R和I之间不对等； 2.R对等于I中的一个非平凡子集，在这样的情况下， 综合1。，我们说 R 小于 I 3.R 对等于 一个自然数序列数目在无限大时候的推广。我们称上述A有“势”为可数势，意味着，A的元数目可以一个一个地数下去，虽然不一定能数完。于是，自然数序列集具有可数势，任何有限集合也有可数势，而且，由上面的3.可知有理数集也有可数势。 再从1.的结论可知，无理数的集有大于可数势的势，我们称这个势为“不可数势”！ (二) “康脱悖论” 设M是一个集，这个集的元是由集合X所组成，其中，X 不属于 X。 康脱悖论：M 不属于 M 同时 M 属于 M 事实上，如果M属于M，则由定义，M不属于M；反过来，如果M不属于M，则同样由定义，M属于M。 这就出现了悖论，这个悖论首先由康脱提出来， 它类似于“塞维尔村理发师悖论”，1902年，罗素又把它在叙述上修改了一下，把它作为一种悖论，用来说明集合论的形式公理体系建立的必要。 康脱悖论的发现，引起了十九世纪末的数学界很大的震动，原因在一切数学的推理和由推理得出的结论最终可以由“与、或、非”三种基本逻辑运算所构成的组合操作，而这些组合操作的集合本身构成了矛盾，于是所有数学成就的整个大厦开始动摇！ 其后，罗素等人提出了形式(逻辑)公理体系，试图甩掉那些悖论，让数学在无悖论的情况下发展(事实上，至今数学里还没有这样的悖论的干扰)。办法就是，如怀特海所说，当一个形式逻辑体系出现康脱悖论时，就用一个更大的逻辑体系去把它包了，换句话说，就是让原先那个逻辑体系作为更大的逻辑体系的子集合。当然这样做的结果，新的母体系又产生了不可避免的矛盾。怀特海问：就这样一层一层地包下去，以致于无穷，是否就可避免了矛盾？ (三) 哥德尔不完备性定理浅释 哥德尔不完备性定理的提出和证明就是为了解决怀特海上述猜想，它指出：使用层层外延法扩张形式逻辑体系并不能清除其总和的矛盾！ 哥德尔最妙的想法就是把一切逻辑运算视作一种二进制代码(CODE)，就例如，“与”可对应为1，“或”可对应为10，“非”可对应为11。但这些二进制数却被他再转换成小数，如0.1，0.01，0.11，组合逻辑运算不过是这三种码的组合，也就是更复杂的小数。 递归：逻辑运算里有一种调用自身的运算，称为“递归”。递归术语今天是编程算法里最基本的运算方法之一。递归有两种结局：1.终止于有限次数的操作；2.无限递归下去，在编程上被称为死循环。 当逻辑体系按照怀特海的办法延拓到一个新的，更大的逻辑体系时，旧的逻辑体系中的操作如果被新的体系调用，就会出现递归，递归有时是无限次数的(这是允许的，不象计算机运算不允许)，在此情况下，由二进制代码所代表的逻辑运算将出现无限循环的小数。 这样，哥德尔就用递归把每一次形式逻辑体系的外延后的操作，用有限小数和无限循环小数代表出来，而且他还证明了，这种代表是唯一对应的，也就是说，每一二进制有限小数或无限循环小数皆唯一对应于怀特海意义下的无限扩张逻辑体系下的某一逻辑操作。 二进制与十进制：二进制数与十进制数之间能建立起唯一对应关系，因之，实轴上0-1的一端(剃除掉两个端点，0、1)的所有小数都可以由二进制小数表出，而且，两种进位制里的有限小数和无限循环小数都对应。 有理数和无理数：任何有限小数和无限不循环小数都属于0-1之间的有理数。0-1数段的实数除了全部含于其中的有理数以外，还存在着无理数，例如2分之2的平方根。如果我们表0-1数段的所有有理数集合为Ro，表剩下的所有无理数集合为Io，则可证明： Ro 对等于 R; Io 对等于 I 这里的R、I见(一)中例的定义。因此，我们遂有Ro有可数势，而Io有不可数势。 哥德尔证明了：怀特海意义下的无限延拓形式逻辑体系的所有逻辑操作所组成的集合与Ro之间能够建立起1-1的对应关系，也就是说，这两个集合对等，因此，它们有相同的势。即都具有可数 势。 但是，如果我们把0-1间任意一个无理数对应成一个逻辑操作，因为它无限不循环，这个操作是我们不能确定的，但却能有限截断后知道的，我们就可以理解成不能用确定的逻辑操作去解决的，或者换个口吻，说成是矛盾。 于是，哥德尔就得出了结论，形式逻辑分析不能用来解决认识中的所有出现的矛盾，更有甚者，我们由Io的不可数势的性质看到，这样的矛盾远多于形式逻辑分析所能解决的数量！ 哥德尔定理证明的独到之处，在于用数学反过来证明逻辑分析问题，前面我们已经看到，数学上已经确定了的推理本来是可被拆成基本逻辑操作来推理的。罗素曾有个想法，认为所有数学的推理都可拆开成基本的逻辑运算去实现，好象是数学可以变成逻辑学似的，今天的哲学界数学界摈弃了罗素这个想法，认为这是不可能的。。 § 配图 § 相关连接 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。