基础定义

哥德尔不完备定理

在数理逻辑中，哥德尔不完备定理是库尔特·哥德尔于1930年证明并发表的两条定理。简单地说，第一条定理指出：

任何一个相容的数学形式化理论中，只要它强到足以蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题。

这条定理是在数学界以外最著名的定理之一，也是误解最多的定理之一。形式逻辑中有一条定理也同样容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上是错误的。稍后我们可以看到一些对哥德尔定理的误解。

把第一条定理的证明过程在体系内部形式化后，哥德尔证明了他的第二条定理。该定理指出：

任何相容的形式体系不能用于证明它本身的相容性。

哥德尔不完备定理

这个结果破坏了数学中一个称为希尔伯特计划的哲学企图。大卫·希尔伯特(David Hilbert)提出，象实分析那样较为复杂的体系的相容性，可以用较为简单的体系中的手段来证明。最终，全部数学的相容性可以归结为基本算术的相容性。但哥德尔的第二条定理证明了基本算术的相容性不能在自身内部证明，因此当然就不能用来证明比它更强的系统的相容性了。

定理意义

哥德尔定理是一阶逻辑的定理，故最终只能在这个框架内理解。在形式逻辑中，数学命题及其证明都是用一种符号语言描述的，在这里我们可以机械地检查每个证明的合法性，于是便可以从一组公理开始无可辩驳地证明一条定理。理论上，这样的证明可以在电脑上检查，事实上这样的合法性检查程序也已经有了。

为了这个过程得以进行，我们需要知道手头有什么样的公理。我们可以从一组有限的公理集开始，例如欧几里德几何。或者更一般地，我们可以允许无穷的公理列表，只要能机械地判断给定的命题是否一条公理就行。在计算机科学里面，这被称为公理的递归集。尽管无穷的公理列表听起来有些奇怪，实际上自然数的的通常理论中，称为皮亚诺公理的就是这么一样东西。

哥德尔的第一条不完备定理表明任何一个允许定义自然数的体系必定是不完全的：它包含了既不能证明为真也不能证明为假的命题。

存在不完备的体系这一事实本身并不使人感到特别惊讶。例如，在欧几里德几何中，如果把平行公设去掉，就得到一个不完备的体系。不完备的体系可能只意味着尚未找出所有必须的公理而已。

但哥德尔揭示的是在多数情况下，例如在数论或者实分析中，你永远不能找出公理的完整集合。每一次你将一个命题作为公理加入，将总有另一个命题出现在你的研究范围之外。

你可以加入无穷条公理（例如，所有真命题）到公理列表中，但你得到的公理列表将不再是递归集。给出任意一条命题，将没有机械的方法判定它是否是系统的一条公理。如果给出一个证明，一般来说也无法检查它是否正确。

在计算机科学的语言中，哥德尔定理有另一种表述方式。在一阶逻辑中，定理是递归可枚举的：你可以编写一个可以枚举出其所有合法证明的程序。你可以问是否可以将结论加强为递归的：你可以编写一个在有限时间内判定命题真假的程序吗？根据哥德尔定理，答案是一般来说不能。

不确定命题的例子

哥德尔和保尔·科恩得出的一些结果结合起来给出了不确定命题（既不能证明也不能否证的命题）的一个实际例子：选择公理和连续统假设都是集合论的标准公理系统内的不确定命题。