哥德尔不完备定理

出自 MBA智库百科(https://wiki.mbalib.com/)

哥德尔不完备定理(Godel's Incompleteness Theorem)

　　在数理逻辑中，哥德尔不完备定理是指库尔特•哥德尔于1931年证明并发表的两条定理。简单地说，第一条定理指出：任何相容的形式系统，只要蕴涵皮亚诺算术公理，就可以在其中构造在体系中既不能证明也不能否证的命题（即体系是不完备的）。

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

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

　　任何相容的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明它本身的相容性。这个结果破坏了数学中一个称为希尔伯特计划的哲学企图。大卫•希尔伯特提出，像实分析那样较为复杂的体系的兼容性，可以用较为简单的体系中的手段来证明。最终，全部数学的兼容性都可以归结为基本算术的兼容性。但哥德尔的第二条定理证明了基本算术的兼容性不能在自身内部证明，因此当然就不能用来证明比它更强的系统的兼容性了。

　　要充实对证明要点的描述，主要的问题在于：为了构造相当于“p是不可证明的”这样的命题p，p就必须包含有自身的引用，而这很容易陷入无穷循环。将要介绍的哥德尔巧妙的把戏，后来被艾伦•图灵用于解决决定性问题。

　　首先，每个公式或者说可形式化的命题都被我们的系统赋予一个唯一的数，称为哥德尔数。这要通过一种可以方便地在哥德尔数和公式之间（机械地）来回转换的方式来完成。因为系统足以表述“数”的概念，因此也就足以表述公式的概念了。公式可以为命题形式、命题或其他。命题形式的哥德尔数数值不同于命题的哥德尔数数值。

　　像F(x)这样的公式含有一个自由变量x，它们称为命题形式。一旦x被一个特定的数代替，它就马上变成一个真正的特定命题，于是它要么是在系统中可证明的，要么不。命题形式自身并不是命题，因此不能被证明也不能被否证。但每一个命题形式F(x)都有一个哥德尔数，可用G(F)表示。自由变量的选择与G(F)的赋值无关。

　　通过小心地分析系统的公理和推理规则，可以写下一个命题形式P(x)，它表示x是系统中一个可以证明的命题的哥德尔数。形式描述如下：如果x是一个可证明命题对应的哥德尔数，P(x)就可被证明，而其否定~P(x)则不能。

　　现在，哥德尔的把戏来了：一个命题形式F(x)称为不可自证的，当且仅当把命题形式F的哥德尔数G(F)代入F中所得的命题F(G(F))是不可证明的。这个定义可以形式化，于是可以构造一个命题形式SU(z)，表示z是某个不可自证命题形式的哥德尔数。SU(z)的形式描述如下：

　　对某个命题形式F(x)有z = G(F)，而且设y是命题F(G(F))的哥德尔数，则有~P(y)成立。

　　现在我们所要的语句p就可以如下定义：

　　p = SU(G(SU))

　　直观上，当问到p是否为真的时候，我们是在问：“不可自证这个特性本身是不可自证的吗？”这很容易让人联想到理发师悖论，那个理发师只替那些不替自己理发的人理发：他替自己理发吗？

　　现在让我们假定公理系统是相容的。

　　如果p可以证明，于是SU(G(SU))为真，根据SU的定义，z = G(SU)就是某个不可自证命题形式的哥德尔数。于是SU就是不可自证的，根据不可自证的定义，SU(G(SU))是不可证明的。这一矛盾说明p是不可证明的。

　　如果p = SU(G(SU))的否定是可以证明的，则根据SU的定义，z = G(SU)就不是不可自证命题形式的哥德尔数。这意味着SU不是不可自证的。根据不可自证的定义，我们断定SU(G(SU))是可以证明的，同样得到矛盾。这说明p的否定也是不可证明的。

　　因此，p既不可在系统内证明也不可在系统内否证。

　　令p是如上构造的不确定命题，且假定系统的兼容性可以在系统内部证明。我们已经看到，如果系统是兼容的，则p是不可自证的。这个证明过程可以在系统内部形式化，因此命题“p是不可证明的”或者“~P(p)”可以在系统内证明。

　　但是最后一个命题就等价于p自己（而且这种等价性可以在系统内部证明），从而p就可以在系统内证明。这一矛盾说明系统是不相容的。

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

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

　　哥德尔的第一条不完备定理表明任何一个允许定义自然数的体系必定是不完全的：它包含了不能在此体系内以一阶谓词逻辑形式证明的命题，并且该命题的否命题也不能在该体系内以一阶谓词逻辑的形式证明。

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

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

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

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

　　哥德尔的第一条定理有不少误解。我们就此稍作说明：

　　 该定理并不意味着任何有趣的公理系统都是不完备的。例如，欧几里得几何可以被一阶公理化为一个完备的系统（事实上，欧几里得的原创公理集已经非常接近于完备的系统。所缺少的公理是非常直观的，以至于直到出现了形式化证明之后才注意到需要它们）

　　 该定理需假设公理系统可以“定义”自然数。就算这些系统拥有包括自然数作为子集的模型，也不一定就能定义自然数。必须透过公理和一阶逻辑，在系统中表达出x是一个自然数这个概念才行。有许多系统包含自然数，却是完备的。例如，塔斯基（Tarski）证明了实闭域都是完备的一阶公理化系统。

　　 这理论用在人工智能上，则指出有些道理可能是我们能够判别，但机器单纯用一阶公理化系统却无法得知的道理。不过机器可以用非一阶公理化系统，例如实验、经验。

　　不完备性的结论影响了数学哲学以及符号逻辑（使用形式符号描述原理）中的一些观点。我们可以将第一定理解释为“我们永远不能发现一个万能的公理系统能够证明一切数学真理，而不能证明任何谬误”。以下对第二定理的另一种说法甚至更令人不安：

　　如果一个（强度足以证明基本算术公理的）公理系统可以用来证明它自身的兼容性，那么它是不兼容的。

　　于是，为了确立系统S的兼容性，就要构建另一个系统T，但是T中的证明并不是完全可信的，除非不使用S就能确立T的兼容性。举个例子，自然数上的皮亚诺公理的兼容性可以在集合论中证明，但不能单独在自然数理论范围内证明。这对大卫•希尔伯特的著名的未解决的23个数学问题中的第二个给出了一个否定回答。

　　理论上，哥德尔理论仍留下了一线希望：也许可以给出一个算法判定一个给定的命题是否是不确定的，让数学家可以忽略掉这些不确定的命题。然而，对可判定性问题的否定回答表明不存在这样的算法。

　　要注意哥德尔理论只适用于较强的公理系统。“较强”意味着该理论包含了足够的算术以便承载对第一不完备定理证明过程的编码。基本上，这就要求系统能将一些基本操作例如加法和乘法形式化，例如在鲁宾逊算术Q中那样。有一些更弱的公理系统是兼容而且完备的，例如Presburger算术，它包括所有的一阶逻辑的真命题和关于加法的真命题。

　　公理系统可能含有无穷条公理（例如皮亚诺算术就是这样），但要哥德尔定理生效，必须存在检验证明是否正确的有效算法。例如，可以将关于自然数的所有在标准模型中为真的一阶语句组成一个集合。这个公理系统是完备的；哥德尔定理之所以无效，是因为不存在决定任何一条语句是否公理的有效算法。从另一方面说，这个算法的不存在正是哥德尔定理的直接结果。

　　另一个哥德尔定理不适用的特殊情况是：将关于自然数的所有语句首先按长度然后按字典顺序排序，并从皮亚诺公理集开始，一个一个遍历列表，如果发现一条语句既不能证明又不能否证，就将它作为公理加入。这样得到的系统是完备的，兼容的，并且是足够强大的，但不是递归可枚举集的。

　　哥德尔本人只证明了以上定理的一个较弱版本；以上定理的第一个证明是罗梭（Russel）于1936年给出的。

　　基本上，第一定理的证明是通过在形式公理系统中构造如下命题

　　p = “此命题是不可证明的”

　　来完成的。这样，它可以看成是说谎者悖论的一个现代变种。

　　如果公理系统是兼容的，哥德尔证明了p（及其否定）不能在系统内证明。因此p是真命题（p声称它不可证明，而它确实不能），尽管其证明不能在系统内形式化。请注意将p作为公理加入系统并不能解决问题：扩大了的系统中会有另一个哥德尔语句出现。

　　罗杰•彭罗斯声称“可被机械地证明的”和“对人类来说看起来是真的”的这一区别，表明了人类智能在本质上不同于机械过程。这一观点未被普遍接受，因为正如Marvin Minsky

　　所指出的，人类智能有犯错误和理解不相容和谬误句子的能力。但Marvin Minsky透露说库尔特•哥德尔私下告诉他，他相信人类有一种到达真理的直觉方法，但因为跟计算机式的方法不同，人类可以知道为真的事情并不受他的定理限制。

　　对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点，也可以作如下评论：我们其实不知道p是真是假，因为我们并不（也无法）知道系统是否是兼容的。因此实际上我们并不知道系统之外的任何真理。我们所确知的只有这样一个命题：

　　要么p在系统内部无法证明，要么该系统是不相容的。

　　这样的命题之前已经在系统内部被证明。实际上，这样的证明可以如下给出。

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

　　在1973年，同调代数中的怀特海问题被证明是集合论中的不确定命题。

　　1977年，Paris和Harrington证明了组合论中的一个命题，拉姆赛理论的某个版本，在皮阿诺公理给出的算术公理系统中是不确定的，但可以在集合论的一个更大体系中证明为真。

　　在计算机科学中用到的克鲁斯克尔算法的树问题，也是在皮亚诺公理中不确定而在集合论中可证明的。

　　Goodstein定理是一个关于自然数的相对简单的命题，它在皮亚诺算术中是不确定的。

　　Gregory Chaitin在算法信息论中构造了一个不确定命题，即Chaitin随机数Ω的第n个字节是否为0这样的命题在ZFC内是不可判定的。

　　计算逻辑中的停机问题不可解，亦是哥德尔不完备定理的一种表现形式。