[敬请读者注意] 本人保留本文的全部著作权利。如果哪位读者使用本文所描述内容，请务必如实引用并明白注明本文出处。如果本人发现任何人擅自使用本文任何部分内容而不明白注明出处，恕本人在网上广泛公布侵权者姓名。敬请各位读者注意，谢谢！

“PM及相关系统的形式不可判定命题”（2）- 哥德尔不完全性定理的涵义及有效范围

程京德

本文试图澄清哥德尔不完全性定理的涵义及有效范围，说明哥德尔的工作究竟断定了什么以及没有断定什么。

哥德尔证明的两个重要定理的原始陈述如下[1-4]：

命题IX/第一不完全性定理：在命题VI中言及的所有形式系统中，都存在有受限谓词演算的不可判定问题（亦即，受限谓词演算的逻辑式，其普遍有效性以及其反例的存在性都不可证）。

命题XI/第二不完全性定理：如果c是一个给定的递归且一致的逻辑式类，则表达“c是一致的”之内容的命题逻辑式不是c-可证的；特别地，P的一致性在P中不可证，在假设P是一致的前提下（如果不是，那么当然，任何言明都是可证的）。

下面，对这两个定理的涵义及有效范围做一些解释性说明。

似乎没有历史记录显示哥德尔本人自称命题IX及命题XI为“不完全性定理”或“第一/二不完全性定理”（由此也显示出哥德尔一贯的严谨作风）。所谓“不完全性定理”，是他人在哥德尔的工作发表之后对其两个定理的称呼，严格地说，这样的称呼是多少有些问题的（详见下面的说明）。

自古希腊以来，为知识提供基础的基础主义方法论(the foundationalism methodology)一直都试图把所有人类知识通过 
  （1）明确地为真的基本知识，以及（2）无可争议的知识扩展过程， 
来建立在坚实的基础之上[5]。形式化逻辑系统及基于形式化逻辑系统的形式系统/理论就是基础主义方法论在逻辑学中的典型应用。

任何逻辑学、数学、以及众多科学理论都必然地基于一些基本假设或者第一原理而构建的，数理逻辑当然也不例外。经典数理逻辑是建立在下面4个基本假设之上的：

经典抽象(the classical abstraction)：命题对逻辑学来说唯一重要的性质是它的形式和真值。

弗雷格假设/可拓性原则(the Fregean assumption / the principle of extensionality)：任何一个命题的真值只取决于它的形式和其组成成分的真值，而不取决于它们的内容意义。

两值原理(the principle of bivalence)：真值正好有两个，真(TRUE)和假(FALSE)。每个命题都有其一个或另一个真值，但不是两者都有。

有效性的经典解释（the classical account of validity, CAV）：一个论证是有效的，当且仅当不可能它的所有前提都是真的而它的结论却是假的。

和两值原理相关的还有一条逻辑原则，排中律(the law/principle of excluded middle)， 对于任意命题P，其自身或其否定必有一真，亦即，(P or ¬P)必为真。

基于上述基本假设形式化的经典数理逻辑是爆发的(explosive)形式逻辑系统，亦即，从一对矛盾的（亦即，不一致）命题可以推出任意命题作为结论。任何基于经典数理逻辑形式化的形式系统/理论也同样是爆发的。因此，讨论任何有意义的基于经典数理逻辑形式化的形式系统/理论时，通常都需要假设该形式系统/理论是一致的、无矛盾的。这就是哥德尔的两个定理中作为前提条件之一要求对象形式系统/理论是一致的、无矛盾的之根本原因。哥德尔还在命题XI的陈述里专门注释了一句“（如果不是，那么当然，任何言明都是可证的）”。

一个基于经典数理逻辑形式化的形式系统/理论被称为是经典完全的(classically complete)，当且仅当该系统/理论的任意一个逻辑式，其本身或其否定的两者之一必然在该系统/理论中可证。从逻辑哲学的角度来说，经典完全性的定义是隐含地基于排中律的。定义一个形式系统/理论的完全性，是意图对是否把该系统/理论的对象领域中所有应该被认可的事实或经验律都已经全部包含进该系统/理论中来做一判定，全部包含了就是完全的，否则是不完全的。如果遵循两值原理和排中律，那么既然任意命题P其自身或其否定必有一真（应该被认可），则任意命题P其自身或其否定必有一个在一个形式系统/理论中可证就给出了完全与否的判定标准。

命题IX既然断定了PM及相关系统中存在有不可判定命题，那么这些系统依据经典完全性的定义就都是不完全的。所以，严格地说，PM及相关系统的经典不完全性应该是命题IX的一个（隐含地基于两值原理和排中律的）推论。众所周知，直观主义逻辑/数学是不承认排中律的。希尔伯特在其计划中特别限定要以有穷方法来证明算术的一致性，就是为了避免来自直观主义逻辑学家的批评[6]。从逻辑哲学的观点来看，一方面遵从希尔伯特计划把方法论限定在有穷方法，另一方面却以隐含地承认排中律的前提下得到的经典不完全性推论为由把哥德尔陈述的原本命题IX称之为“第一不完全性定理”，实际上并不恰当。

命题XI的内容与形式系统/理论的完全性并不直接相关，被称为“第二不完全性定理”就更不恰当。

通俗地但是严谨地说，命题IX/第一不完全性定理（以及罗瑟的改进）仅仅断定了在一类形式系统/理论（亦即，基于经典一阶谓词演算的、至少包含了初等数论的、一致的形式系统/理论）中必定存在有形式不可判定命题。所有由此定理衍生出来的其它命题，都仅仅是该定理的推论，并且这些衍生命题几乎都需要额外的前提条件。

正确理解命题IX/第一不完全性定理的有效范围有几个关键点。第一，该定理的断定针对的是形式系统/理论，凡不是形式化的形式系统/理论的任何体系，都不在该定理的有效范围之内。第二，该定理的断定针对的是基于经典一阶谓词演算形式化的形式系统/理论，一个形式系统/理论可以是基于各种不同的形式逻辑系统形式化的，凡不是基于经典一阶谓词演算形式化的形式系统/理论，都不在该定理的有效范围之内。第三，该定理的断定针对的是至少包含了初等数论的形式系统/理论（哥德尔工作的关键是通过哥德尔配数法(Gödel numbering)将每个一阶谓词逻辑概念/符号/逻辑式/形式证明表达成为一个自然数（亦即，哥德尔数(Gödel number)）），比这样的形式系统/理论“小”的形式系统/理论，都不在该定理的有效范围之内。第四，如前所述，该定理的断定针对的是一致的形式系统/理论，任何不一致的形式系统/理论，完全没有被讨论的意义。

另一方面，关于“必定存在有形式不可判定命题”，其含义是指在有穷方法的限定下，能够构造出其自身或者其否定都不是形式地可证（亦即，在所考查的对象形式系统/理论内不可能找到一个有穷的形式证明序列）的命题。 

命题IX/第一不完全性定理当然没有断定关于超出其考查对象有效范围的任何体系有无不可判定命题或者其完全性。

通俗地但是严谨地说，第二不完全性定理仅仅断定了对于一类形式系统/理论（亦即，基于经典一阶谓词演算的、递归的、一致的形式系统/理论），表达其一致性的命题在该系统中不可证。换言之，这类形式系统/理论的一致性（这其实是一种“元”性质）不可能被表达为一个在该系统/理论内可证的目标定理。

当然，在一个形式系统/理论内部不可能找到一个表达其一致性的目标定理的形式证明，并不意味着也必定找不到一个表达其一致性的元定理的元证明（未必是形式化的，未必遵循有穷观点和方法）。实际上，在希尔伯特放宽了有穷方法的限制之后，根岑(G. Gentzen, 1909-1945)就在1936年用超穷归纳法证明了初等数论的一致性[6]。

王浩先生的“数理逻辑通俗讲话”[7] 大概是对哥德尔不完全性定理给予介绍和解说的最早的中文文献了，因此在国内的影响也比较广泛（笔者本人就不知多少次被朋友、同事、学生们问及此书中的相关内容）。王浩先生在“数理逻辑通俗讲话”中对哥德尔第一不完全性定理介绍道：“对任一数学的形式（形式化公理）系统 S 来说，在系统中构造不可判定的数论问题的方法是给定的 (A method is given of constructing, for any formal (formalized axiom) system S of mathematics, a question of number theory undecidable in the system)”。王浩先生在此通俗介绍的下文中对哥德尔第一不完全性定理本质上所依赖前提条件中的三个（请注意：笔者的这个表述“本质上所依赖前提条件中的三个”，与本文下面所引用的王浩先生自己的表述“本质上它只依赖于以下三个条件”并不完全相同）做了说明： “这是一个一般的结果，本质上它只依赖于以下三个条件：(a) 公理系统 S 真正是形式的；(b) 系统 S 足够丰富，以展开一个适量的数论；(c) S 是协调的。” 实际上，可能因为王浩先生本人是经典数理逻辑学家，又是在中国科学院做关于数理逻辑的通俗讲演，在上面三个前提条件的表述中，忽略了清晰明白地表述出所谓“形式的”和“协调的（亦即，一致的）”都应该是在经典一阶谓词演算的意义下所说的这一重要前提。王浩先生在“数理逻辑通俗讲话”中将哥德尔第二不完全性定理通俗地表述为：“没有一个古典数学形式系统能够证明它自己的协调性。或者，满足上面提到的 (a), (b), (c) 的一个系统 S 的协调性借助在 S 中的一个语句 Con(S) 而有自然的表示，但 Con(S) 不能是 S 的一个定理 (No classical formal system of mathematics can prove its own consistency. Or, the consistency of a system S satisfying (a),(b),(c) mentioned above has a natural representation by a sentence Con(S) in S but Con(S) cannot be a theorem of S.)。”

应该说，如果从严谨性来要求，那么王浩先生对哥德尔第一不完全性定理本质上所依赖前提条件的陈述是不完全的。由于经典一阶谓词演算作为形式化的基础逻辑的重要作用，把它作为哥德尔第一不完全性定理本质上所依赖前提条件之一清晰明白地陈述清楚才是严谨的，才能够清晰明白地界定哥德尔第一不完全性定理的有效范围。

现今，我们强调经典一阶谓词演算作为形式化的基础逻辑这一前提条件的重要性，还在于，如果我们选用非爆发的、準协调的形式逻辑系统，比如说準协调逻辑(paraconsistent logic)或者相关逻辑(relevant logic)来作为形式化的基础逻辑，那么所得到的形式理论也将是非爆发的、準协调的，就无需要求一致性这个前提条件了。

王宪钧先生（1937年春赴维也纳大学留学学习数理逻辑，是哥德尔的“集合论公理体系”课程唯一正式注册的学生[8]）在“数理逻辑引论”[6]中将哥德尔第一不完全性定理表述为：“一个包括初等数论的形式系统 P，如果是一致的那么就是不完全的。这被称为第一不完全性定理。” 将哥德尔第二不完全性定理表述为：“如果这样的形式系统是一致的，那么其一致性在本系统中不可证。这被称为第二不完全性定理。”

显然，王宪钧先生陈述的哥德尔第一不完全性定理并非原本的命题IX/第一不完全性定理，而是其推论。并且，把前提条件之一的一致性单独挑出来作为条件句前件的这种陈述方式，极其容易被误读误解（详见本系列文章的后续文章）。另外，与王浩先生同样，王宪钧先生也忽略了清晰明白地表述出经典一阶谓词演算作为形式化的基础逻辑这一本质上重要的前提条件，没有能够清晰明白地界定哥德尔第一不完全性定理的有效范围。

黄耀枢先生在“数学基础引论”[9]中将哥德尔第一不完全性定理表述为：“对于任一形式理论系统φ丰富到足以包括形式初等数论的所有公式，如果它是一致的，那么它是不完全的。” 将哥德尔第二不完全性定理表述为：“断定通过‘理论内部可形式化’的方法来证明φ的一致性的不可能性。”

显然，与王宪钧先生同样，黄耀枢先生陈述的哥德尔第一不完全性定理也并非原本的命题IX/第一不完全性定理，而是其推论。并且也采用了把前提条件之一的一致性单独挑出来作为条件句前件的这种陈述方式。因为在“数学基础引论”书中已经定义了：“φ作为一个一阶形式公理理论它包含两类公理：一类是带等号的一阶谓词演算公理，另一类是数学公理，它选取了φ的闭公式的某一集合，这些公理总是由这理论的数学内容提供的。例如，φ作为描写初等数论的一阶理论，它就包括皮亚诺公理。φ的推理规则，可证性和课推演性定义与一阶谓词演算相同。”，所以，黄耀枢先生对哥德尔第一不完全性定理本质上所依赖前提条件的陈述是完全的，能够清晰明白地界定哥德尔第一不完全性定理的有效范围。

概括地说，凡是与基于经典一阶谓词演算的形式系统/理论无关的任何逻辑学、数学、计算、人工智能问题（比如，有关任何非形式化系统的问题），都与哥德尔不完全性定理的断定无关，哥德尔的结论并未断定有关这些问题的任何内容。更进一步说，因为经典数理逻辑是基于经典有效性标准和经典两值原理的，形式系统/理论中的可判定性是基于有穷观点的，所以，那些不满足或者超越了经典有效性标准、经典两值原理（包括甚至连逻辑真值都无严格定义的情形）、以及有穷步骤可判定性这些范围的所有问题（比如，有关任何非基于经典数理逻辑的形式系统/理论的问题），也都与哥德尔不完全性定理的断定无关，哥德尔的结论并未断定有关这些问题的任何内容。最后，从本质上来说，哥德尔的结论实际上揭示的是对于一个允许“实无穷”的数学形式系统/理论，有穷方法的局限性。因此，对于任何一个“有穷”形式系统/理论，其一致性及完全性应该在理论上是可以确认的，完全不需要应用哥德尔的结论。至于把哲学及人文社会科学等领域的问题也与哥德尔不完全性定理扯到一起讨论，应该都是基于对哥德尔不完全性定理的误读误解而产生的逻辑谬误，毫无学术价值。

最后，预告一下本系列文章的后续写作计划：

“PM及相关系统的形式不可判定命题”（3）- 正确地准确地认识哥德尔不完全性定理的意义 

“PM及相关系统的形式不可判定命题”（4）- 对哥德尔不完全性定理的误读误解 

“PM及相关系统的形式不可判定命题”（5）- 对哥德尔不完全性定理的误读误解实例 

参考文献

[1] K. Gödel, “über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik Physik, Vol. 38, pp. 173–198, 1931. (The summary of the results of this work, published in Anzeiger der Akad. D. Wiss. In Wien (math.-naturw. Kl.) 1930, No. 19.)
English Translation: B. Meltzer (Translation) and R. B. Braithwaite (Introduction), K. Gödel, “On formally undecidable propositions of Principia Mathematica and related systems I,” Basic Books, 1962, Dover Publications, 1992. 

[2] K. Gödel (1930b, 1931, and 1932b), “Some metamathematical results on completeness and consistency, On formally undecidable propositions of Principia Mathematica and related systems I, and On completeness and consistency,” in J. Van Heijenoort (Translation, Ed.), “Frege and Gödel: Two Fundamental Texts in Mathematical Logic,” pp. 83-108, Harvard University Press, 1970.  

[3] K. Gödel, “über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” “On formally undecidable propositions of Principia Mathematica and related systems I,” Repringted and translated (by J. Van Heijenoort) in S. Feferman, et al. (Eds.), “Kurt Gödel: Collected Works,” Volume I, Publications 1929-1936, pp. 144-195, Oxford University Press, 1986.  

[4] 程京德, “PM及相关系统的形式不可判定命题”（1）- 哥德尔不完全性定理的历史背景与内容，微信公众号“数理逻辑与哲学逻辑”，2023年5月23日。

[5] G. Sher, “The Foundational Problem of Logic,” The Bulletin of Symbolic Logic, Vol. 19, No. 2, pp. 145-198, 2013.  

[6] 王宪钧, “数理逻辑引论 第三篇 数理逻辑发展简述”，北京大学出版社, 1982年,1998年。

[7] H. Wang/王浩, “Popular Lectures on Mathematical Logic,” Science Press and Von Nostrand Reinhold, 1981; “数理逻辑通俗讲话”，科学出版社, 1981; “Popular Lectures on Mathematical Logic (added a postscript),” Dover Publications, 1993. 

[8] H. Wang, “Reflections on Kurt Gödel,” MIT Press, 1987. 中译：王浩著，康宏逵译， “哥德尔”，上海译文出版社，2002年。 

[9] 黄耀枢, “数学基础引论”， 北京大学出版社, 1987年。

微信公众号“数理逻辑与哲学逻辑”