哥德尔不完全性定理

哥德尔不完全定理，也称哥德尔不完备定理，是库尔特·哥德尔于1931年证明并发表的两条定理。哥德尔不完备定理破坏了希尔伯特计划的哲学企图。大卫·希尔伯特提出，像实分析那样较为复杂的体系的兼容性，可以用较为简单的体系中的手段来证明。最终，全部数学的兼容性都可以归结为基本算术的兼容性。但哥德尔的第二条定理证明了基本算术的兼容性不能在自身内部证明，因此当然就不能用来证明比它更强的系统的兼容性了。为数学的发展以及多学科理论的发展做出了伟大的推动。

意义

对基础的空前探讨是20世纪纯粹数学的趋势之一，而这种探讨的重要动因就是相容性问题。哥德尔不完全性定理，正是研究相容定理而提出的非常深刻的思维成果。1931年，奥地利数学家哥德尔发表论文《论<数学原理>及有关系统中的形式不可叛逆命题》，其中提出了哥德尔不完全性定理。

定义

哥德尔第一不完全性定理

任一足以包含自然数算术的形式系统，如果是相容的，那么一定存在一条不可叛逆命题，即存在某一命题A和它的否定在该系统中皆不可证。

哥德尔第二不完全性定理

在真的但不能由公理来证明的命题中，包括了这些公理是相容的（无矛盾的）这一论断本身。也就是说，一个包含自然数算术的公理系统是相容的，那么这种相容性在该系统内是不可证明的。

证明

• 只要证明了初等算数理论Π是不完全的，采用相同的方法就可以证明任何包含Π的形式理论都是不完全的
• 证明Π的不完全性的关键是在于构造出初等算数语言Ľ中的一个含义为真的语句Α，证明如果Α能被证明则将推出矛盾
• 包含初等算数理论的意义是它包含所有正整数（无穷元素）。而命题和证明都可以被映射到正整数。另一方面，它还支持归纳集，即及由一些初始元素及新元素构成的集合，而新元素都是由初始元素归纳（运算）而得的。形式理论由公理及定理构成，定理可以看作是公理及已知定理的归纳，因而形式理论本身可以表示成以某些正整数为初始元素的某种归纳集。这使得可证性变为算术命题
• 所构造的语句Α类似于“说谎者悖论”（即“这句话在说谎”），但Α是“本语句不可证”。对这一形式化的Α如果假设Α可证将推出矛盾，但假设Α不可证却不能推出矛盾，所以Α不是一个悖论。而Α的含义是它不可证，而它又被证明是不可证的，因此Α是个不可证的真命题
• Ľ不完全，那么包含Ľ的Π不完全，那么包含Π的形式系统不完全。得证。

应用

• 哥德尔在不完全性定理中提出“原始递归函数”概念，成为算法理论和计算机理论的起点。
• 哥德尔的结果极大的促进了希尔伯特“证明论”的发展。
• 在1973年，同调代数中的怀特海问题被证明是集合论中的不确定命题。
• 1977年，Paris和Harrington证明了组合论中的一个命题，拉姆赛理论的某个版本，在皮阿诺公理给出的算术公理系统中是不确定的，但可以在集合论的一个更大体系中证明为真。
• 在计算机科学中用到的Kruskal的树问题，也是在皮亚诺公理中不确定而在集合论中可证明的。
• Goodstein定理是一个关于自然数的相对简单的命题，它在皮亚诺算术中是不确定的。
• 古格里·钱顿（Gregory Chaitin）在算法信息论中构造了一个不确定命题，即“Chaitin随机数Ω的第n个字节是否为0”这样的命题在ZFC内是不可判定的。
• 计算逻辑中的停机问题不可解，亦是哥德尔不完备定理的一种表现形式。

哥德尔

生平

哥德尔1906年出生于捷克的布尔诺（原奥匈帝国），毕业于维也纳大学，1940年移民美国，任职于普林斯顿高等研究院（IAS）直至1976年退休。1978年，哥德尔于新泽西州的普林斯顿市去世。哥德尔自幼多病，而且从小就患了强迫症（疑病症）。他还患过抑郁症。后来他在普林斯顿的医院绝食而死，因为他认为那些食物有毒。

成就

• 大学时，哥德尔曾参加石里克小组的聚会。
• 1930年9月7日，他正式宣布其哥德尔不完备定理，引起当时重要数学家如冯·诺伊曼和希尔伯特等的重视。后来又钻研连续统假设，但未能完全解决该问题。

轶事

哥德尔的大部分手稿使用加贝尔斯贝格速记法写成。格言：“有些事实被认知为真，但不必然可证。”