文档介绍：(董世平)
分类:形式语义和数理逻辑
哥德尔 (Kurt G?del) 于1931年发表了他的「不完备定理」(Incompleteness Theorem)，至今正好六十年。为此，在哥德尔的求学地维也纳，特别召开了一个会议，讨论哥德尔这个定理所带来的影响。的确，这六十年来，常在不同的领域内，发现到这个定理的影响，而这个定理在不同领域中的应用，甚至引起了相当的争议。
哈佛大学于1952年授与哥德尔荣誉科学博士学位，称他为「本世纪最重要数学真理的发现者」，这里所指的数学真理即为「不完备定理」。虽然当时是1952年，但已宣称此定理是本世纪最重要的数学真理，可见此定理的重要性，不仅可说是空前，亦可称为绝后了。「不完备定理」到底是一个什么样的定理？本文将简介此定理的背景、证明及它对数学、计算器和哲学的影响，盼望大家对这个定理能有较深入的认识与体会。
背景                                                       
自第十九世纪后期，「集合」的观念被提出后，数学家们逐渐的感到，各个不同的数学领域，似乎皆可建立在同一个根基上，就是「集合论」，但是不幸的，过不久逻辑学家们即发现以「集合」这么简单，而且直觉上认为「真」的概念，却会产生「反论」(antinomy)，即「集合」的概念会产生矛盾，这使得数学家们重新思考数学的基础到底是什么？数学会不会出错？如何面对一个直觉上为真，却会导致矛盾的概念？是放弃「集合」的概念呢？或是如当时顶尖的数学家希尔伯特 (Hilbert) 所宣称的：「没有人能将我们逐出集合论的乐园！」。若是如此，又将如何面对矛盾呢？
以总共不到17页的三篇论文，一个年轻的荷兰数学家布饶儿 (Brouwer) 对以往古典逻辑的确实性提出挑战，特别是对所谓的排中律 (Law of the excluded middle)，即对任一命题「A」，A或A之否定命题必有一为真，他认为我们不可无条件的接受，布饶儿坚持有其它的可能性，因此也就有了数学哲学中的直观主义 (Intuitionism) 学派，若接受了此一说法，连带的，数学中许多的证明将不再被接受，特别是所谓存在性的证明。例如，要证明某一微分方程式有解，则必须给出一个方法，把这个解找出来，而不可仅证明「若无解会导致矛盾」，而这却是一般数学家们所常用的方法。希尔伯特不赞成布饶儿的看法，他认为若是如此数学的牺牲实在太大了，那么要如何使数学能立在一个坚固的基础上呢？为此他提出所谓的「希尔伯特计划」(Hilbert program)，即以有限性 (finitary)、组合式 (combinatorial) 的方法，由简单的理论开始，先证明「数论」有一致性 (consistency)，即「数论」中不包含矛盾，再以「数论」为基础证明「分析」有一致性，再一步步往前推，至终证明数学中不包含矛盾，只要能证明即使使用排中律也不会产生矛盾，那么尽可放心大胆的去使用排中律，不必像布饶儿那样束手束脚。
「希尔伯特计划」是一个很好的计划-如果能成功的话。在讨论此计划的成败之前，我们先介绍另一个观念，上文我们说明了一致性。的确，一致性可说是对任一公设系统，最基本的要求，若一个系统内包含矛盾，其它的也就不用再谈了，对公设系统我们另一个希望有的性质就是完备性 (Completeness)。我们用自然数 1,2,3,……来说明这个观念。我们要证明有关自然数的定理，如「质数有无穷多个」，我们若要将证明整个一步步写下来，我们必须从某一个公设系统出发，其实任一个证明，都必须从某一个公设系统出发。对于自然数我们最常用的公设系统就是皮亚诺公设 (Peano Axioms)，这些公设中最复杂而且困难的，（不仅对一般的高中，大学生如此，对逻辑学家亦如此），就是大名鼎鼎的「数学归纳法」。借着数学归纳法及其它的公设，我们可证明「质数有无穷多个」，问题是「是否所有有关自然数的叙述，只要是对的，就可由皮亚诺公设出发，而得到证明呢？」也就是「皮亚诺公设是否完备?」若皮亚诺公设具有完备性，那么所有有关自然数的叙述，若是对的，就可由皮亚诺公设证明。