哥德尔不完备定理

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

这是形式逻辑中的定理，容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上并不是。具体实例见对哥德尔定理的误解。

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

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

形式系统：完备性、一致性和有效公理化
不完备性定理适用于足够复杂，可以表示自然数算术的形式系统，而这种形式系统是自洽的，可以被公理化的。这些概念的详细含义会在后面给出。尤其是在一阶逻辑的语境中，形式系统也被称为"形式定理"。一般地，一个形式系统被定义为含有一组特定公理集合以及符号变换规则(或者是推导规则)的演绎工具。这样的一个形式系统的例子是一阶算术系统，在这个系统中，所有变量都代表为自然数。而在其他系统中，例如集合论，只有部分属于形式系统的表述才表示了自然数算术。不完备性理论是关于这些形式系统中的形式可证明性，而不是关于非形式意义上的"可证明性"。

形式系统可能具有的性质如下，完备性、一致性和有效公理化的存在性。不完备性定理则表明任何蕴含皮亚诺算术公理的形式系统不能同时具有这三个性质。

有效公理化
如果形式系统中的定理集是递归可列举的集合(Franzén 2004, p. 112)，那么该形式系统是"有效公理化的"(也被称为“生成定理的有效性”)。

这意味着，在原则上计算机程序能够列举出系统中所有的定理，而不列出任何非定理的陈述。皮亚诺公理和策梅洛-弗兰克尔集合论 (ZFC) 都是有效生成定理的例子。

现在被称为真算术的理论不仅有皮亚诺算术中关于整数的正确陈述，而且是自洽和完备的，并有足够的运算公理。但是它的定理集不是递归可列举的集合，因此也不满足不完备定理的假设。

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

 含义 
哥德尔巧妙地利用了命题的“真值为真”和“含义为真”的区别，从而构造出了含义为真而真值不可证的命题，又避免了悖论的陷阱。形式逻辑系统的命题本身是没有含义的。命题只有真值而没有含义。公理命题的真值为真。其它命题的真值为真当且仅当该命题可以被证明，为假当且仅当该命题的非可以被证明。当形式逻辑系统被实际应用时，系统中的符号都被映射到实际概念上，从而有了语义。这种映射叫做一个模型。有了模型，命题就有了含义（语义）。例如，在ZF公理化集合论中，系统中的对象（object）被影射到“集合”这一概念，∈被映射到“属于”这一概念就是模型的一个例子。而ZF公理化系统本身即使没有模型也可以成立。如果换一个模型，形式系统没变，只是它不再是集合论了。当然，ZF公理化系统是为了集合论量身打造的，很适合于集合论。如果换一个模型，很难找到可理解的语义。但这说明了“真值为真”和“含义为真”是有区别的。

在常见情况下，命题的“真值为真”和“含义为真”是一致的。例如，设A为一命题,则命题A↔¬A的含义是“本命题A为假”，这时A的真值为真和含义为真是一致的，结果形成了否定循环而构成了悖论。而逻辑系统不能含有悖论，所以这样的A应该是构造不出来的。哥德尔定理证明的巧妙之处就在于将悖论的“为假”改为了“为不可证”使得真值为真和含义为真成为不一致（含义为真是不可证，而真值为真或假都是可证），因而产生了自我否定又避免了循环的效果，也就避免了悖论。

理解了这一点，就可以理解哥德尔定理不是说存在真值为真又不可证这种自相矛盾的悖论命题（实际上应该构造不出来），而是存在含义为真但不可证（即真值不可知）的命题。哥德尔定理也不只是说存在既不可证真，也不可证伪的命题，这样的命题有很多，哥德尔定理的重要之处在于它还说了该不可证的命题是含义为真的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 对哥德尔定理的一些误解 
以下列出的误解都是针对第一条定理而产生的。

 该定理并不意味着任何公理系统都是不完备的。例如，欧几里得几何可以被一階公理化为一个完备的系统（事实上，欧几里得的原创公理集已经非常接近于完备的系统。所缺少的公理是非常直观的，以至于直到出现了形式化证明之后才注意到需要它们）。
 该定理需假设公理系统可以“定义”自然数。就算這些系統擁有包括自然數作為子集的模型，也不一定就能定义自然数。必須透過公理和一階邏輯，在系統中表達出「x是一個自然數」這個概念才行。有許多系統包含自然數，卻是完備的。例如，塔斯基（Tarski）证明了实数和复数理论都是完备的一階公理化系统。

 讨论和推论 

不完备性的结论影响了数学哲学以及形式化主义（使用形式符号描述原理）中的一些观点。第一定理可以被解释为：“不存在一个万能的公理系统，使得其既能够证明一切数学真理，又能证伪任何谬误。”
以下对第二定理的另一种说法甚至更令人不安：

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

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

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

值得注意的是，符合哥德尔不完备定理的系统，必须要蕴涵皮亚诺算术公理以承载对第一不完备定理证明过程的编码。基本上，这就要求系统能将一些基本操作例如加法和乘法形式化，例如在鲁宾逊算术Q中那样。有一些更弱的公理系统是相容而且完备的，例如，它包括所有的一阶逻辑的真命题和关于加法的真命题。

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

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

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

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

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

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

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

罗杰·彭罗斯声称“可被机械地证明的”和“对人类来说看起来是真的”的这一区别，表明了人类智能在本質上不同于機械过程。这一观点未被普遍接受，因为正如马文·闵斯基所指出的，人类智能有犯错误和理解不相容和谬误句子的能力。但马文·闵斯基透露说库尔特·哥德尔私下告诉他，他相信人类有一种到达真理的直觉方法，但因为跟计算机式的方法不同，人类可以知道为真的事情并不受他的定理限制。

对以上认为该定理揭示了人类具有超出形式逻辑之能力的这种观点，也可以作如下评论：p无法被证明，也无法被证伪，因为无法知道系统是否是相容的。因此实际上在此公理系统可证明范围以外的真命题不在考虑范围之内。于是可以说明一个命题：

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

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

 第一不完备定理的证明要点 

證明目標：在任何足夠強大且一致的遞歸可枚舉公理系統中，必定存在一個命題，它既不能被證明為真，也不能被證明為假。證明的核心步驟如下：

 1. 哥德爾編碼 
哥德爾的關鍵想法是：將數學命題、證明步驟和演繹規則轉換為數字，從而將數理邏輯轉化為數論問題。

 透過哥德爾編碼，可以把每個數學語句、證明、證明步驟用一個數字來表示，這些數字稱為哥德爾數（Gödel Number）。
 這樣一來，「某個語句有證明」的性質，就變成一個關於自然數的可計算性質。

 2. 構造自指命題 
哥德爾構造了一個特殊的命題 G，它的語意是：「本命題不可證明」形式化來說，這是利用"對角化法（Diagonalization）"構造出的命題，類似於「這句話是錯的」的悖論，但這次是在數學系統內嚴格定義的。

 具體而言，哥德爾引入了一個公式 Proof(x, y)，表示「數字編碼為 x 的命題由編碼為 y 的證明所證明」。
 透過對角化技術，哥德爾構造出一個命題 G，其含義為： ¬Proof(Go¨delNumber(G),y) 這表示 G 無法在系統內被證明。

 3. 分析命題 G 的真偽 
考慮兩種情況：

 假設 G 可證明：
 若系統可以證明 G，則 G 斷言「G 不能被證明」，產生矛盾。
 因此，G 不能被證明。
 假設 G 可證偽（即證明 ¬G）：
 如果系統能夠證明 ¬G（即 G 是假的），那麼這表示 G 是假的，這意味著 G 是可證的，矛盾！
 因此，G 也不能被證偽。

由以上可知，G 既無法被證明為真，也無法被證明為假，這證明了系統的不完備性。

 第二不完备定理的证明要点 

第二不完備定理是第一定理的延伸，主要說明：任何足夠強大且一致的系統都無法證明自身的一致性。大致證明思路：

 利用第一不完備定理，已知存在某個命題 G，它在系統內是無法證明的。
 如果系統能夠證明自身的一致性（即「系統無矛盾」），則可以藉由此推導出 G 是真的，從而證明 G。
 但 G 是不可證的，這導致矛盾，因此「系統能證明自身一致性」的假設不成立。

因此，系統無法證明自身的一致性，這表明如果想確認一個系統是無矛盾的，就需要依賴一個更強的系統，而不是該系統本身。

与不确定性原理的关系
有学者指出不完备定理和不确定性原理有某种联系。http://research.cs.queensu.ca/home/akl/cisc879/papers/SELECTED_PAPERS_FROM_VARIOUS_SOURCES/aqi4.pdf   Algorithmic Randomness, Quantum Physics,
and Incompleteness

 参见 
 相容性
 自我引用
 逻辑主义
 哥德尔定理
 哥德尔完备性定理
 ZFC系統無法確定的命題列表

 参考文献 

 外部链接 
 K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971.
 B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91
 Karl Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
 D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0-465-02685-0. (1999 reprint: ISBN 0-465-02656-7).
 Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: Gödel's Proof, revised edition (2002). ISBN 0-8147-5816-9.
 Hilbert's second problem（English translation）
 Norbert Domeisen, Logik der Antinomien. Bern etc.: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH

G
G
G
G