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

哥德尔不完全性定理的内容和有效范围 (1) 哥德尔断定了什么？

程京德

在人类社会知识宝库的众多成果当中，关于基于经典数理逻辑的一类数学形式系统（亦即，PM及相关系统）之完全性给出否定性断定的“哥德尔不完全性定理” [1-3] 大概是被误解甚至被歪曲的最多的定理了。笔者由于工作领域的关系，在许多场合不知多少次地听到过或者看到过专业人士或非专业人士对哥德尔不完全性定理的各种各样误解和误用。相关或者相近专业人士的误解之缘由不在这里讨论；实际上，非专业人士对哥德尔不完全性定理的内涵理解不足从而造成误解，从根本上说，应该是源于专业人士对哥德尔不完全性定理的介绍和解释存在着的模糊或者不足之处。

本系列文章试图先对哥德尔不完全性定理给予尽可能准确的通俗解释，然后对一些关于哥德尔不完全性定理的经典介绍和解释指出其有可能造成误解的地方，并且列举一些对哥德尔不完全性定理的典型误解实例，剖析这些误解实例为什么、在哪里是不对的，以期帮助非专业一般人士更准确地理解哥德尔不完全性定理的内涵。

对数理逻辑本身，对逻辑哲学和数学哲学来说，哥德尔不完全性定理无疑是一个十分重要的定理。但是，我们将会看到，哥德尔不完全性定理有其清晰地严谨地定义了的概念基础和严格地限定了的有效范围，它并非是一个可以用来指导有关逻辑学和数学（甚至人工智能）之一切的、“放之四海而皆准的绝对真理”。另一方面，由于哥德尔不完全性定理是一个否定性的定理，把误解了它的人们从实际上并不存在的否定性断定的桎梏中解放出来，将会促进大家萌发出更多创新研究的想法，这正是笔者花费时间来写这篇科普文章的根本目的。

首先做几点说明：（1）因为本文想定的读者对象是科学网读者，所以，仅限于对中文文献（包括译作）的考察。（2）即便是仅限于中文文献，笔者也无足够时间来考察所有文献，所以，将仅选择有代表性的经典文献为考察对象（本人觉得这样做就已经足够了，因为众多普通文献中对哥德尔不完全性定理的解说往往是对经典文献中的说法稍作改动甚至原封不动抄来的）。（3）本文将以渐进集成方式来完成，随时补充随时修改。

出于本文的目的，关于哥德尔不完全性定理之内容，本文将直接基于哥德尔本人的原始陈述（英译）[1]，不在文中多次重复引用了（有兴趣的读者请参阅本人博文“哥德尔不完全性定理之原始陈述(http://blog.sciencenet.cn/blog-2371919-943124.html )”中给出的图片)。

本文第一句话中对哥德尔不完全性定理的通俗定性介绍为：“关于基于经典数理逻辑的一类数学形式系统（亦即，PM及相关系统）之完全性给出否定性断定”。如果我们清晰地解释清楚了下面这些问题，那么我们就可以准确地理解哥德尔不完全性定理的内涵，知道哥德尔不完全性定理实际上到底断定了什么了：“什么是形式系统？”，“什么是数学形式系统？”，“什么是基于经典数理逻辑的形式系统？”，“什么是经典数理逻辑？”， “什么是形式系统的完全性？”，“什么是形式系统的一致性？”，“哥德尔不完全性定理是针对哪一类形式系统的？”，最后，“哥德尔不完全性定理给出了怎样的否定性断定？”。

什么是形式系统？“形式系统”一词在形式化方法被广泛应用的今天，已经是一个多义词了（以当今形式系统一词的各种意义去理解哥德尔不完全性定理也是造成误解的原因之一），但是在数理逻辑领域，“形式系统”是一个有着严格定义的概念。德国逻辑学家数学家希尔伯特(David Hilbert)在19世纪末对几何基础的研究（这一研究工作开创了元数学）中首创并发展了形式公理化方法，形成了形式系统的概念。一个形式系统由其抽象符号系统（形式语言，字母表和文法规则）和形式证明系统（形式理论，公理和变换规则）这两部分构成；形式语言部分定义了可以作为初始符号的符号集合（字母表）和由符号合法地形成符号串（公式）的文法规则，形式理论部分定义了作为系统出发点的公理和从一组公式（前提）合法地变换为另一个公式（结论）的证明规则。因为形式系统概念是为了用来抽象地、形式地、“能行地”研究元数学问题，所以“有穷观点”是形式系统的本质特征：在任何形式系统中，任何一个证明（从前提公式群到结论公式的变换序列）必须是有穷的，对任何一个证明的正确性检查，必须能够在有穷步骤内完成。形式系统中的这一性质通常被称为（能行）可判定性。请注意，这里给出的仅仅是形式系统的一般定义，并没有定义一个具体的形式系统，依据所定义或采用的抽象符号系统和形式证明系统之不同，我们可以构造出形形色色的具体形式系统。

什么是数学形式系统？所谓“数学形式系统”，就是将某个数学领域或分支形式化之后得到一个具体形式系统。比如说，世界上第一个数学形式系统，由希尔伯特将几何学形式化之后得到的“几何形式系统”。

什么是基于经典数理逻辑的形式系统？基于经典数理逻辑的形式系统就是以经典数理逻辑的语言作为形式语言来定义初始概念和经验（亦即，非逻辑）公理、描述公式，以经典数理逻辑的证明系统作为证明系统而构成的各种具体形式系统，比如，基于经典数理逻辑的公理集合论形式系统，基于经典数理逻辑的自然数论形式系统，基于经典数理逻辑的几何形式系统。

什么是经典数理逻辑？“经典数理逻辑”就是在逻辑学或者计算机科学中也被称为经典谓词演算的逻辑系统，强调其“经典”，是因为它基于一些经典的基本原理或假设，这些原理或假设如下：经典有效性标准（一个论断或推理为真当且仅当其前提为真时其结论不为假），经典二值原理（仅承认和使用“真”与“假”两个逻辑真值，并且任何一个逻辑式的逻辑真值在任何一个形式语义模型解释之下必为“真”与“假”之一），经典抽象原理（命题的任何性质仅由其形式和逻辑真值决定），Fregean假说（命题的逻辑真值，仅由其形式和构成成分的语意性质决定）。经典数理逻辑的语言允许使用可数多（与自然数“一样多”）个个体常量，可数多个个体变量，可数多个函数符号，可数多个谓词符号，和“联言（与）”，“选言（或）”，“否定（非）”，“实质蕴含”，及“等价”这些逻辑联结词来构成复合逻辑式。经典数理逻辑的逻辑定理集合恰恰是由那些在其所有形式语意模型下被解释成为真的恒真逻辑式所构成的，不多也不少（健全性和完全性）。

什么是形式系统的完全性？形式系统概念是为了用来抽象地、形式地、“能行地”研究元数学问题的，考虑到任何具体数学领域中一般都有其有效范围，我们用形式系统的完全性来刻画这一性质。一个系统是（经典）完全的当且仅当对于其任何一个公式，公式本身或其否定的两者之一在该系统中必然可证。另一方面，尽管形式系统概念是为了用来抽象地、形式地、“能行地”研究元数学问题的，但是一个和具体数学领域毫无关联的形式系统是毫无实际意义的。要让一个具体形式系统具有实际意义，我们除了要用其形式语言定义某个数学领域的基本概念和经验公理之外，还必须为该系统定义一个形式语意模型，该模型应该严格定义何为逻辑真值以及何为一个系统公式在该模型下的语意解释。那么，在给定一个具体形式系统及其形式语意模型之后，如果系统中每个可证明的经验定理在模型下都被解释为真，我们说该系统是（语意）健全的，如果在该模型下被解释为真的公式在系统中都是可证明的经验定理，我们说该系统是（语意）完全的。

什么是形式系统的一致性？形式系统概念是为了用来抽象地、形式地、“能行地”研究元数学问题的，考虑到在任何具体数学领域中一般都不允许出现矛盾，我们用形式系统的一致性来刻画这一性质。一个系统是（经典）一致的当且仅当对于其任何一个公式，公式本身或其否定之两者不得在该系统中同时可证。

哥德尔不完全性定理是针对哪一类形式系统的？哥德尔不完全性定理讨论的是基于经典数理逻辑的、初等数论以及包含初等数论的形式系统，亦即，“PM”及其相关系统。“PM”是怀德海(Alfred North Whitehead)和罗素(BertrandArthur William Russell)在1910年至1913年间所著三卷本学术名著“Principia Mathematica”（罗素在1903年先写就了“Principlesof Mathematics”，然后与怀德海合作写就三卷本之后用意义相同的拉丁文命名，1903年计划的第四卷最终没有完成）的通用简称，也经常被用来简称该书中给出的初等数论形式系统。哥德尔在其1931年论文中的第一段及脚注2明白地说明了他考察的对象是“thesystem of Principia Mathematica (PM) and, on the other, the axiom system forset theory of Zermelo-Fraenkel (later extended by J. v. Neumann)”[1-3]。

哥德尔不完全性定理给出了怎样的否定性断定？哥德尔本人在其1931年论文中断定（哥德尔本人原始陈述中的Proposition IX，通称第一不完全性定理）：“对于所有基于经典数理逻辑的、包含初等数论的、ω一致的（本文至此还没有说明）形式系统，在系统中必定存在某些不可判定的命题，其本身或者其否定在系统中都不可证”。哥德尔在论文中给出了构造出这样的不可判定命题的具体方法。罗塞尔(John Barkley Rosser)在1936年把哥德尔原始结论陈述中的前提条件“ω一致的”进一步修改为“（经典）一致的”。另外，作为第一不完全性定理的一个推论，哥德尔还在一个系定理（哥德尔本人原始陈述中的Proposition XI，通称第二不完全性定理）中断定：“对于一个基于经典数理逻辑的、递归的、一致的形式系统，表达其一致性的命题在该系统中不可证”（哥德尔在论文中给出了证明框架，真正的形式化证明是1939年由希尔伯特和贝纳斯所完成的）。

至此，我们已经比较清晰地解释了哥德尔不完全性定理的内涵，说明了哥德尔不完全性定理实际上到底断定了什么。

参考文献

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.)
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 1930a), “Some metamathematicalresults on completeness and consistency, On formally undecidable propositionsof Principia Mathematica and related systems I, and On completeness andconsistency,” in J. Van Heijenoort (Ed.), “Frege and Gödel: Two FundamentalTexts in Mathematical Logic,” pp. 83-108, Harvard University Press, 1970.  

3.  K. Gödel, “über formal unentscheidbare Sätze der Principia Mathematicaund verwandter Systeme I,” “On formallyundecidable propositions of Principia Mathematica and related systems I,” in S. Feferman, et al. (Eds.), “Kurt Gödel: Collected Works,” Volume I, Publications 1929-1936, pp. 144-195, Oxford University Press, 1986.