来源：http://episte.math.ntu.edu.tw/articles/mm/mm_15_4_11/#top 戈德尔不完备定理 董世平 1.背景 2.叙述与证明 3.对数学的影响 4.对电脑的影响 5.对哲学的影响 戈德尔 (Kurt Godel) 於1931年发表了他的「不完备定理」(Incompleteness Theorem)， 至今正好六十年。为此，在戈德尔的求学地维也纳，特别召开了一个会议，讨论戈德尔这 个定理所带来的影响。的确，这六十年来，常在不同的领域内，发现到这个定理的影响， 而这个定理在不同领域中的应用，甚至引起了相当的争议。 哈佛大学於1952年授与戈德尔荣誉科学博士学位，称他为「本世纪最重要数学真理的发现 者」 [注1] ，这里所指的数学真理即为「不完备定理」。虽然当时是1952年，但已宣称 此定理是本世纪最重要的数学真理，可见此定理的重要性，不仅可说是空前，亦可称为绝 後了。「不完备定理」到底是一个什麽样的定理？本文将简介此定理的背景、证明及它对 数学、计算机和哲学的影响，盼望大家对这个定理能有较深入的认识与体会。 1.背景 自第十九世纪後期，「集合」的观念被提出後，数学家们逐渐的感到，各个不同的数学领 域，似乎皆可建立在同一个根基上，就是「集合论」，但是不幸的，过不久逻辑学家们即 发现以「集合」这麽简单，而且直觉上认为「真」的概念，却会产生「反论」(antinomy) ，即「集合」的概念会产生矛盾，这使得数学家们重新思考数学的基础到底是什麽？数学 会不会出错？如何面对一个直觉上为真，却会导致矛盾的概念？是放弃「集合」的概念呢 ？或是如当时顶尖的数学家希伯特 (Hilbert) 所宣称的：「没有人能将我们逐出集合论 的乐园！」。若是如此，又将如何面对矛盾呢？ 以总共不到17页的三篇论文，一个年轻的荷兰数学家布饶儿 (Brouwer) 对以往古典逻辑 的确实性提出挑战，特别是对所谓的排中律 (Law of the excluded middle)，即对任一 命题「A」，A或A之否定命题必有一为真，他认为我们不可无条件的接受，布饶儿坚持有其 他的可能性，因此也就有了数学哲学中的直观主义 (Intuitionism) 学派，若接受了此说 法，连带的，数学中许多的证明将不再被接受，特别是所谓存在性的证明。例如，要证明 某一微分方程式有解，则必须给出一个方法，把这个解找出来，而不可仅证明「若无解会 导致矛盾」，而这却是一般数学家们所常用的方法。希伯特不赞成布饶儿的看法，他认为 若是如此数学的牺牲实在太大了，那麽要如何使数学能立在一个坚固的基础上呢？为此他 提出所谓的「希伯特计划」(Hilbert program)，即以有限性 (finitary)、组合式 (combinatorial) 的方法，由简单的理论开始，先证明「数论」有一致性 (consistency) ，即「数论」中不包含矛盾，再以「数论」为基础证明「分析」有一致性，再一步步往前 推，至终证明数学中不包含矛盾，只要能证明即使使用排中律也不会产生矛盾，那麽尽可 放心大胆的去使用排中律，不必像布饶儿那样束手束脚。 「希伯特计划」是一个很好的计划-如果能成功的话。在讨论此计划的成败之前，我们先介 绍另一个观念，上文我们说明了一致性。的确，一致性可说是对任一公设系统，最基本的 要求，若一个系统内包含矛盾，其他的也就不用再谈了，对公设系统我们另一个希望有的 性质就是完备性 (Completeness)。我们用自然数 1,2,3,……来说明这个观念。我们要证 明有关自然数的定理，如「质数有无穷多个」，我们若要将证明整个一步步写下来，我们 必须从某一个公设系统出发，其实任一个证明，都必须从某一个公设系统出发。对於自然 数我们最常用的公设系统就是皮亚诺公设 (Peano Axioms)，这些公设中最复杂而且困难 的，（不仅对一般的高中，大学生如此，对逻辑学家亦如此），就是大名鼎鼎的「数学归 纳法」。藉着数学归纳法及其他的公设，我们可证明「质数有无穷多个」，问题是「是否 所有有关自然数的叙述，只要是对的，就可由皮亚诺公设出发，而得到证明呢？」也就是 「皮亚诺公设是否完备?」若皮亚诺公设具有完备性，那麽所有有关自然数的叙述，若是 对的，就可由皮亚诺公设证明。 由戈德尔不完备定理而得的一个结论，就是「皮亚诺公设是不完备的！」有些关於自然数 的叙述是对的，但皮亚诺公设无法证明它，戈德尔的证明也的确告诉我们如何找到这个叙 述。事实上，由戈德尔的证明，我们可得一个算则，给我们一个公设系统，我们就可按此 算则，而得到一个算术句型，再经过适当的编译 (compile)，即可成为此系统内的一个句 型，而此句型在此系统内为真，却无法在此系统内被证明，所以也许我们会觉得皮亚诺公 设不具有完备性，这是它的缺点，我们应当找另一个具有完备性的公设系统来代替它，但 不完备定理告诉我们，「任何一个具有一致性的公设化系统皆是不完备的！」这也就是为 什麽虽然大家明知皮亚诺公设是不完备的，但这个公设系统仍是被普遍的使用，因为任何 其他系统，也都是不完备的。也许我们再退一步，皮亚诺公设固然不具有完备性，我们至 少可要求它具有一致性吧！也就是皮亚诺公设所证明的，一定是真的，可惜，这一点也做 不到，由不完备定理可得另一个结论就是「在皮亚诺公设系统内将无法证明它的一致性！ 」从某一方面来说，你须要假设比「皮亚诺公设是一致的」更强或相等的假设，你才能证 明皮亚诺公设的一致性，当然我们若须要更强的假设，也就须要更大的信心去相信它是对 的。同样的，皮亚诺公设也没那麽特殊，就像不完备性的结果一样，由戈德尔不完备定理 ，任一个足够强的公设系统，皆无法证明它本身的一致性，所以要证明数学具有一致性， 即数学中不会产生矛盾，你将无法由数学中得到，你必须靠数学以外的东西，也许是你个 人的哲学或神学，来相信数学是有意义的，这可说是粉碎了「希伯特计划」，难怪当希伯 特由他的学生伯内 (P. Bernay) 处听到戈德尔的这个定理时，他对这一个定理感到生气 [注2] ，因为他将无法回应布饶儿的挑战了，但在真理面前，人人都须低头。 2.叙述与证明 以上简述了不完备定理的背景，现在我们来叙述不完备定理，一般所谓的不完备定理，分 为两个部份： 第一不完备定理 任何一个足够强的一致公设系统，必定是不完备的。 即除非这个系统很简单，(所以能叙述的不多)，或是包含矛盾的，否则必有一真的叙述不 能被证明。 第二不完备定理 任何一个足够强的一致公设系统，必无法证明本身的一致性。 所以除非这个系统很简单，否则你若在此系统性，证明了本身的一致性，反而已显出它是 不一致的。 戈德尔的证明过程相当复杂，而其中最核心的概念，是古典希腊哲学中一个有名的诡论 (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，它是真的，却无法被证明。任何一个公设系统若能说出「这句话不能 被证明」则此系统若非不一致，就是不完备。为了确知是否清楚了这个概念，读者不妨作 一个测验，「没有真理！」是真的吗？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.5.64 ※ 编辑: popandy 来自: 140.112.5.64 (04/20 21:17)