戈德尔不完备定理

戈德尔不完备定理     戈德尔(Kurt G?del) 于1931年发表了他的「不完备定理」(Incompleteness Theorem)，至今正好六十年。为此，在戈德尔的求学地维也纳，特别召开了一个会议，讨论戈德尔这个定理所带来的影响。的确，这六十年来，常在不同的领域内，发现到这个定理的影响，而这个定理在不同领域中的应用，甚至引起了相当的争议。 哈佛大学于1952年授与戈德尔荣誉科学博士学位，称他为「本世纪最重要数学真理的发现者」，这里所指的数学真理即为「不完备定理」。虽然当时是1952年，但已宣称此定理是本世纪最重要的数学真理，可见此定理的重要性，不仅可说是空前，亦可称为绝后了。「不完备定理」到底是一个什么样的定理？本文将简介此定理的背景、证明及它对数学、计算机和哲学的影响，盼望大家对这个定理能有较深入的认识与体会。 背景   自第十九世纪后期，「集合」的观念被提出后，数学家们逐渐的感到， 各个不同的数学领域，似乎皆可建立在同一个根基上，就是「集合论」，但是不幸的，过不久逻辑学家们即发现以「集合」这么简单，而且直觉上认为「真」的概念，却会产生「反论」(antinomy)，即「集合」的概念会产生矛盾， 这使得数学家们重新思考数学的基础到底是什么？数学会不会出错？如何面对一个直觉上为真，却会导致矛盾的概念？是放弃「集合」的概念呢？或是如当时顶尖的数学家希伯特(Hilbert) 所宣称的： 「没有人能将我们逐出集合论的乐园！」。若是如此，又将如何面对矛盾呢？ 以总共不到17页的三篇 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 ，一个年轻的荷兰数学家布饶儿(Brouwer) 对以往古典逻辑的确实性提出挑战，特别是对所谓的排中律(Law of the excluded middle)，即对任一命 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 「A」，A或A之否定命题必有一为真， 他认为我们不可无条件的接受，布饶儿坚持有其他的可能性， 因此也就有了数学哲学中的直观主义(Intuitionism) 学派，若接受了此一说法，连带的，数学中许多的证明将不再被接受，特别是所谓存在性的证明。例如，要证明某一微分方程式有解，则必须给出一个 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，把这个解找出来， 而不可仅证明「若无解会导致矛盾」，而这却是一般数学家们所常用的方法。希伯特不赞成布饶儿的看法，他认为若是如此数学的牺牲实在太大了， 那么要如何使数学能立在一个坚固的基础上呢？为此他提出所谓的「希伯特计划」(Hilbert program)， 即以有限性(finitary)、组合式(combinatorial) 的方法，由简单的理论开始， 先证明「数论」有一致性(consistency) ，即「数论」中不包含矛盾， 再以「数论」为基础证明??「分析」有一致性，再一步步往前推， 至终证明数学中不包含矛盾，只要能证明即使使用排中律也不会产生矛盾， 那么尽可放心大胆的去使用排中律，不必像布饶儿那样束手束脚。 「希伯特计划」是一个很好的计划-如果能成功的话。在讨论此计划的成败之前， 我们先介绍另一个观念，上文我们说明了一致性。的确，一致性可说是对任一公设系统，最基本的要求，若一个系统内包含矛盾，其他的也就不用再谈了， 对公设系统我们另一个希望有的性质就是完备性(Completeness) 。我们用自然数1,2,3,……来说明这个观念。我们要证明有关自然数的定理， 如「质数有无穷多个」，我们若要将证明整个一步步写下来，我们必须从某一个公设系统出发，其实任一个证明，都必须从某一个公设系统出发。对于自然数我??们最常用的公设系统就是皮亚诺公设(Peano Axioms)， 这些公设中最复杂而且困难的，（不仅对一般的高中，大学生如此，对逻辑学家亦如此），就是大名鼎鼎的「数学归纳法」。借着数学归纳法及其他的公设， 我们可证明「质数有无穷多个」，问题是「是否所有有关自然数的叙述，只要是对的，就可由皮亚诺公设出发，而得到证明呢？ 」也就是「皮亚诺公设是否完备?」 若皮亚诺公设具有完备性，那么所有有关自然数的叙述，若是对的， 就可由皮亚诺公设证明。 由戈德尔不完备定理而得的一个结论，就是「皮亚诺公设是不完备的！」有些关于自然数的叙述是对的，但皮亚诺公设无法证明它，戈德尔的证明也的确告诉我们如何找到这个叙述。事实上，由戈德尔的证明，我们可得一个算则，给我们一个公设系统，我们就可按此算则，而得到一个算术句型，再经过适当的编译(compile)，即可成为此系统内的一个句型，而此句型在此系统内为真，却无法在此系统内被证明，所以也许我们会觉得皮亚诺公设不具有完备性，这是它的缺点，我们应当找另一个具有完备性的公设系统来代替它，但不完备定理告诉我们，「任何一个具有一致性的公设化系统皆是不完备的！」这也就是为什么虽然大家明知皮亚诺公设是不完备的，但这个公设系统仍是被普遍的使用，因为任何其他系统，也都是不完备的。也许我们再退一步，皮亚诺公设固然不具有完备性，我们至少可要求它具有一致性吧！也就是皮亚诺公设所证明的，一定是真的，可惜，这一点也做不到，由不完备定理可得另一个结论就是「在皮亚诺公设系统内将无法证明它的一致性！ 」从某一方面来说，你须要假设比「皮亚诺公设是一致的」更强或相等的假设，你才能证明皮亚诺公设的一致性，当然我们若须要更强的假设，也就须要更大的信心去相信它是对的。同样的，皮亚诺公设也没那么特殊，就像不完备性的结果一样，由戈德尔不完备定理，任一个足够强的公设系统，皆无法证明它本身的一致性，所以要证明数学具有一致性，即数学中不会产生矛盾，你将无法由数学中得到，你必须靠数学以外的东西，也许是你个人的哲学或神学，来相信数学是有意义的，这可说是粉碎了「希伯特计划」，难怪当希伯特由他的学生伯内(P. Bernay)处听到戈德尔的这个定理时，他对这一个定理感到生气  ，因为他将无法回应布饶儿的挑战了，但在真理面前，人人都须低头。 叙述与证明   以上简述了不完备定理的背景，现在我们来叙述不完备定理，一般所谓的不完备定理，分为两个部份： 第一不完备定理  任何一个足够强的一致公设系统，必定是不完备的。 即除非这个系统很简单，(所以能叙述的不多)，或是包含矛盾的， 否则必有一真的叙述不能被证明。 第二不完备定理  任何一个足够强的一致公设系统，必无法证明本身的一致性。 所以除非这个系统很简单，否则你若在此系统性，证明了本身的一致性，反而已显出它是不一致的。 戈德尔的证明过程相当复杂，而其中最核心的概念，是古典希腊哲学中一个有名的诡论(paradox)：说谎者诡论。纪元前6世纪希腊时代的一个诗人哲学家Epimenides 说了一句很有名的话：「所有的克里特岛人都是说谎的。」这句话有名倒不是因为它是真理，正好相反，因为它一定是错的，为什么是错的呢？因为说这句话的人Epimenides 就是克里特岛人，同样一句话，别人说也可能是对的，（希望不致冒犯了克里特岛人），但是由克里特岛人来说，就一定是错的，为什么呢？若这句话是真的，则Epimenides 没有说谎，和这句话矛盾，所以这句话是假的。我们再举一个例子来说明这个诡论。 A：B这句话是真的。  B：A这句话是假的。 我们可能会认为A(或B)这句话非真即假，且让我们来看看是否如此，假设A这句话是真的，即表示B这句话是真的，故「A这句话是假的」是真的，故A这句话是假的，和假设矛盾。我们现在假设A这句话是假的，则「B这句话是真的」是假的，故B这句话是假的，所以「A这句话是假的」是假的，即A这句话是真的，这又和我们的假设矛盾，结论是，A不论是真是假都得到矛盾，大家若有兴趣，不妨从B句开始，亦得到相同的结果，这就是它之所以被称为诡论的缘由。 戈德尔是如何利用这个概念呢？若说：「这句话是假的。」 那么利用前面的论证，这句话是矛盾的，所以任何一个一致的公设系统都无法说出这句话来，而戈德尔将上面的这句话改为「这句话不能被证明。」 注意，「真」和「能被证明」并不相等，同样「假」和「不能被证明」亦不相等。戈德尔证明了在皮亚诺公设内，（其实不需要用到这么强的公设）可以说出「这句话不能被证明」，若愿意接受这件事，我们即可证明不完备定理了，为证明方便，我们称「这句话不能被证明」为A，若在此系统内A被证明了，则由A的意义，即A不能被证明，知道「A」是假的，而在此系统内证明了一个假的叙述，表示此系统是不一致的，故若此系统是一致的，则A不能被证明，则由A的意义得知A是真的，因它说它不能被证明，因此我们也就找到了一个叙述，即为A，它是真的，却无法被证明。任何一个公设系统若能说出「这句话不能被证明」则此系统若非不一致，就是不完备。为了确知是否清楚了这个概念，读者不妨作一个测验，「没有真理！」是真的吗？     对数学的影响   何谓数学?对这个问题，不同的人会有很不同的答案，但是每一个数学家所努力的， 都是要找到「证明」，从大家所接受的公理或公设出发，找出对某一个题目的证明。从希腊时代，就留下了许多的问题，有许多的问题，经过了数学家们的努力， 我们已知道了答案，也就是我们找到了「证明」，如所谓的几何三大难题， 而有些至今尚未解决，如「双生质数是否无限多？」任何一个问题， 我们总是盼望找到「证明」，不论是证明它是真的，或是证明它是假的都可以， 不论是证明「双生质数是无限多」，或是证明「双生质数是有限的」， 都将是一个非常轰动的结果。若是找不到证明，则认为也许是自己才智不够， 或是时间尚末成熟，真的是如此吗？ 1930年希伯特接受Konigsberg 赠予荣誉市民时，发表了一个著名的演说， 演说辞的最后两句话为 「我们必须知道，我们将会知道」(Wirmussenwissen. Wirwerdenwissen.) 当年希伯特的演讲所灌制的唱片，现在仍然保存着，我们若仔细听，仍依悉可听到希伯特讲完这句话时，得意的笑声  。对着数学抱着如此的信心，相信是极大部份的数学家所共有的，希伯特清楚且有力的表达出来，只可惜这个信心是没有根据的，而且没有多久，就被证明如此乐观的信心是错的，因为1930年11月17日， 《Monatshefte fur Mathematik und Physik》这个期刊接受了当年25岁的戈德尔所投的稿，证明了不完备定理，有些命题是真的，但无法被证明，数学家也许有信心（事实上由不完备定理可知这个信心是无法证实的）说： 「被证明的就是真的」，但再也无法说：「真的一定会被证明。」 自戈德尔证明了不完备定理之后，许多数理逻辑学家们即努力去找一个数论中为真，但无法用皮亚诺公设证明的叙述，花了将近半个世纪都没有找到，因此也就有人说戈德尔所指的「为真但无法证明」的命题，可能和真正的数学无关，即一个真正研究数学，而非研究逻辑的数学家，将永远不会遇到这样的命题，不完备定理是逻辑上的一个有趣的定理，但对数学没有影响，所有的数学问题，如「双生质数是否无限多？」，我们仍迟早会知道答案。1978年Paris和Harrington终于找到了组合学Ramsey理论中的一个命题，它是真的，但无法用皮亚诺公设证明，后来其他的学者又陆续发现了许多这样的命题，（有兴趣的读者可参阅笔者〈数学归纳法〉一文）。对任何一个数学命题，我们当然要想法子证明它是真的，或找反例证明它是错的，若是都不成功的话，也许该听听不完备定理所给的建议，尝试去证明「此命题无法被证为真」，或「此命题无法被证明为假」，以往数学家只有两条路可走，证明是真的，或证明是假的，如今又多了两条路，不能被证明是真的，和不能被证明是假的。要提醒大家注意的，就是第三条和第四条路彼此并不相斥，集合论中有名的「连续统假说」(Continuum Hypothesis)，即被证明以现有的集合论公设，无法证明它为假（戈德尔1936年的结果），亦无法证明它为真（Paul Cohen 1963年的结果）。 对电脑的影响   戈德尔于193l年发表了不完备定理时，还没有现今所谓的电脑，对于电脑如何发明的，至今仍众说纷纭，我们引用普林斯顿高等研究院1978-1979年度 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 中所摘录曾任美国国家科学院副院长的Mac Lane的一段话：「戈德尔伟大而抽象的逻辑工作，有个令人惊异的结果。在分析戈德尔所描述的何者可被一步步程序所得的正式方法中，年轻而聪明的英国逻辑家图林(Alan Turing)定出了这程序所得的结果，即一般递归函数(general recursive functions)，这也正是一台机器所可能计算的，借着这个分析，及其在John Von Neumann等人身上的作用，以致现代计算机的理论观念及分析得以开展，直至今日，对于何者可被计算的理论描述，及至更深入的分析，我们可正确的说，仍然根植于戈德尔于1931年所发表的数理逻辑论文中。」  我们再举两个较近的例子：电脑病毒与人工智慧。对于电脑病毒，几乎所有使用电脑的人都遇到过，人人闻之色变，因为感觉防不胜防，事实上，的确如此。我们不时看到警告，又有某种新的病毒出现了，然后解毒专家们再 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一个新的解毒程式来破解它，在广告中常看到说某种解毒程式如何如何有效，可解多少多少种病毒，脑筋动的快的人，也许会想，为什么不设计一种万灵丹？可解所有已知及未知的毒，别的不说，钱肯定是可赚得不少，当然也可能有些人会想设计出一种病毒是杀不死的，戈德尔不完备定理告诉我们的是， 「没有万灵丹」，也「没有杀不死的病毒」，对任何解毒程式，我们皆可设计出一种病毒，使得这个解毒程式杀不死它，同样对任何病毒，我们都可设计出一个解毒程式，把这个病毒杀死。总之，不论是放毒或解毒的人，都不会没事干，我想这是个坏消息，也是个好消息  。 电脑能不能跟人脑一样？电脑和人脑的差别在那里？这是常被提出的问题。使电脑跟人脑一样，这是人工智慧学家努力的目标。英国剑桥大学的数学物理学家，亦为皇家学会的院士Roger Penrose 对这个问题，写了一本出乎他自己意料之外畅销的书《皇帝新脑》（The Emperor's New Mind）。1990年7月2日的时代杂志也报导了这本书， 而时代杂志用了一个唯恐天下不乱的标题〈那些电脑都是笨蛋！〉 (Those computers are dummies)。的确，此书一出又引起了正反双方的论战， Penrose 当然提出许多论证来支持他的论点，即人工智慧是有其限度， 他最重要的论证即根据戈德尔不完备定理，事实上，这个论证早就被提出过， 另外一本使戈德尔较为人所知的书，即为得1979年普立兹奖(Pulitzer Prize) 的书《戈德尔，艾叟，巴哈》(Godel, Escher , Bach)，作者Hofstadter 分别以艾叟的画，巴哈的音乐来阐述戈德尔的定理，就像Penrose 的书，这本书也是介绍人工智慧， 夹议科学哲学的书，Hofstadter 同样以不完备定理说明人工智慧所会受到的限制， 但Hofstadter 对人工智慧的发展是乐观的。 对哲学的影响   现今人类发现似乎有太多的问题无法解决，有各式各样的「危机」，如能源危机、道德危机、人口爆炸危机等等，而常有「无力感」，但在本世纪初期，人类展望二十世纪是充满了盼望与信心，当然当时也有许多问题有待解决，但面对未来大家都是乐观的，特别是对「理智」的信心非常强，相信凭着理智所有的问题都可解决，数学不就是个明显的例子吗？十八、十九世纪数学的成就是惊人的，如从希腊时代就留下来的所谓「几何三大难题」，竟然一次就都被解决了，也难怪希伯特对科学说：「我们必须知道，我们将会知道」，自然须交出它所有的问题，而人类必将所有的问题一一克服，所以当不完备定理一出来，对许多人来说仿如晴天霹雳，Kline 写了一本书，书名为《数学：确定性的失落》(Mathematics: The Loss of Cerntainty) 很能描绘出这个心情，人们认为找到了数学的基础，却发现这个基础是海市蜃楼，而且不完备定理似乎告诉人们，我们将永远无法找到这个基础，连数学这号称最精确的科学尚且如此，其他所有的知识又如何立足呢?不完备定理告诉我们，有些事情是真的，但我们无法证明它，若是如此，人要如何面对没有被证明的事？既无法全部接受，亦不该全部否决，如何决定取舍呢？这似乎是人人都可以也应当思考的问题， 而不仅仅是哲学家所必须面对的问题。 不完备定理的发现至今已超过六十年了，这个定理的重要性，不仅未随时间、历史背景的改变而减退，人们在不同的领域中，正逐渐发现它的意义与影响，只可惜由于国内对逻辑的研究者不多，至今尚没有一本合适的中文书证明或阐明此定理，对此定理证明有兴趣的读者可参考HB Enderton 所著的《A Mathematical Introduction to Logic》。 今年亦为国内的数理逻辑的前辈刘世超博士的七十岁生日，谨以此文敬贺刘教授七十岁，亦盼望逻辑此一领域在大家继续的努力下，在国内能生根，开花，结果。