科学网—准确地理解哥德尔不完全性定理“关于PM及相关系统的形式不可判定命题”(1)
精选
已有 3592 次阅读
2024-6-26 08:18
| 个人分类: 数理逻辑 | 系统分类: 科普集锦
[敬请读者注意] 本人保留本文的全部著作权利。如果哪位读者使用本文所描述内容，请务必如实引用并明白注明本文出处。如果本人发现任何人擅自使用本文任何部分内容而不明白注明出处，恕本人在网上广泛公布侵权者姓名。敬请各位读者注意，谢谢！
准确地理解哥德尔不完全性定理“关于PM及相关系统的形式不可判定命题”(1) - 背景及内容
程京德
[关于文章题目的说明：为了准确地介绍哥德尔的重要工作“关于PM及相关系统的形式不可判定命题(On formally undecidable propositions of Principia Mathematica and related systems)”的内容和恰当地（亦即，非夸大地）说明其重要意义，笔者曾经在科学网博客和本公众号上已经发表过几篇科普文章，但是总觉得采用的题目不是很贴切。再三综合思考的结果，决定采用上题。]
序言
在人类社会知识宝库的众多成果当中，哥德尔(Kurt Friedrich Gödel, 1906-1978)于1930-1931年证明的、关于基于经典数理逻辑的一类数学形式系统（亦即，PM及相关系统）的形式不可判定命题的两个重要定理[1-3]，俗称“哥德尔不完全性定理”，大概是被误解甚至被歪曲的最多的定理了。笔者首先想澄清的一件事情是，似乎没有历史记录明白地显示哥德尔本人自称过其工作为“不完全性定理”或“第一/第二不完全性定理”（由此也显示出哥德尔一贯的严谨作风）；所谓“不完全性定理”，是其他人在哥德尔的重要工作发表之后对其两个定理的称呼。严格地说，“哥德尔不完全性定理”这样的称呼是多少有些问题的，也是造成对哥德尔的重要工作有众多误解误用的原因之一。
笔者由于工作领域的关系，在国内外众多媒体和场合不知多少次地看到过或者听到过各种专业或非专业人士（其中不乏世界级著名学者）对“哥德尔不完全性定理”的各种各样误解误用和过度夸大宣传，并且这种状况至今仍然在持续，造成大众对 哥德尔 该项重要工作的混乱认识。
大众 对 “哥德尔不完全性定理” 的理解不足从而造成误解 误用 ，究其根本原因，应该是源于数理逻辑及数学基础论专业人士对 哥德尔 该项重要工作 的介绍和说明存在着的模糊不清之处。
本系列文章试图先准确地解释“哥德尔不完全性定理”的历史背景及内容，恰当地（亦即，非夸大地）说明其可以应用的外延范围以及不可随意扩展到的范围，以及清晰地概括 其重要意义， 然后对一些关于 “哥德尔不完全性定理” 的经典介绍和解释指出其有可能造成误解的地方，并且列举一些对 “哥德尔不完全性定理” 的典型误解实例，指出这些 实例到底 误解 在哪里 、 为什么 是不对的，以期帮助非数理逻辑及数学基础论专业的读者能够准确地理解 “哥德尔不完全性定理” 的内涵及其应用范围。
对于数理逻辑本身，以及逻辑哲学和数学哲学来说， “哥德尔不完全性定理” 无疑是十分重要的定理。但是，我们将会看到， “哥德尔不完全性定理” 有其清晰地严谨地定义了的概念基础和严格地限定了的有效范围（哥德尔本人的研究及写作风格是极其精准清晰的），它并非是一个可以用来指导有关逻辑学和数学（甚至一部分学者们常说的哲学、计算机科学与人工智能！）之一切的“放之四海而皆准的绝对真理”。所有对 “哥德尔不完全性定理” 超出其有效范围的扩大解释和夸大宣传都是完全不正确的。另一方面，由于 “哥德尔不完全性定理” 是一个否定性定理，把误解了它的人们从实际上并不存在的否定性断定的桎梏 中解放出来 （粗略地说，任何逻辑学和数学问题的解决，只要不牵涉到形式系统或者可计算 性 / 可 判定性，都不会受到 “哥德尔不完全性定理” 在原理上的限制，至于逻辑学及数学以外的所有其它领域就更是如此），将会促进人们萌发出更多创新研究的想法，这正是笔者花费时间和精力来写这篇科普文章的根本目的。
哥德尔的工作之背景
首先，让我们来介绍一下哥德尔的工作之历史背景。
希尔伯特(David Hilbert, 1862-1943)在1899年给出了几何的抽象公理化[4]，并在1900年表明几何的一致性问题可以归结为实数系统的一致性问题，进而可以通过利用戴德金(Julius Wilhelm Richard Dedekind,1831-1916)的结果归结为算术的一致性问题。1900年在巴黎举行的第二次世界数学家大会上希尔伯特提出的数学问题中的第二个问题，就是算术公理的一致性问题[5]。希尔伯特1904年在海德堡举行的第三次世界数学家大学上提出基于有穷观点来证明算术的一致性[6]，从而形成其著名的“希尔伯特计划(Hilbert's program)”[7,8]。
希尔伯特计划试图通过一系列基础（形式化）工作来奠定数学的基础，使得数学在形式化基础上是一致的、无矛盾的；更准确地说，希尔伯特希望用形式化公理方法来形式化所有数学，并以基于不假定实无穷的有穷观点的能行方法（有穷方法）来证明数学公理是一致的。这样就可以保证从数学中排除那些已知的悖论，而且还保证建立在形式化基础之上的数学根本不可能出现悖论。
哥德尔在1929年以证明一阶谓词逻辑完全性的工作[9]于1930年1月6日获得了维也纳大学博士学位之后，还需要用一篇论文来申请执教资格，所以他需要找到一个合适的题目来作为其执教资格论文的题材[10]。哥德尔选择的问题就是希尔伯特提出的算术公理的一致性问题。在当时，希尔伯特的学生阿克曼(Wilhelm Friedrich Ackermann, 1896-1962)和冯诺依曼(John von Neumann,1903-1957)已经使用有穷方法为皮亚诺算术(Peano Arithmetic, PA)的一个受限子系统找到了一致性证明，似乎再克服一些技术上的困难，成功指日可待[11]。哥德尔选择了比皮亚诺算术更强的系统，亦即，怀德海(Alfred North Whitehead, 1861-1947)和罗素(Bertrand Arthur William Russell, 1872-1970)的名著、三卷本《数学原理》(Principia Mathematica, PM)[12]中陈述的系统去证明其一致性。PM以（陈述不完全的）经典一阶谓词逻辑为基础形式逻辑系统，构建了（基于罗素类型论的）集合论、基数、序数、以及实数的形式理论[7,12,13]。
从上述历史背景可知，哥德尔的工作之原始目的是要证明PM系统的一致性，并非其完全性或不完全性。
哥德尔的工作之内容
接下来，让我们来准确地解释，哥德尔究竟证明了什么？
首先，需要说明一下哥德尔严格地描述并用于证明其主要结果的对象系统：形式系统P。哥德尔本人陈述：“P本质上是通过把PM的逻辑（数作为个体，后继关系作为未定义的基本概念）叠加在Peano公理之上得到的系统(P is essentially the system obtained by superimposing on the Peano axioms the logic of PM ( numbers as individuals, relation of successor as undefined basic concept).)。” “与系统PM中所做的所有其他更改一样，添加Peano公理仅起到简化证明的作用，原则上可以省去 (The addition of the Peano axioms, like all the other changes made in the system PM, serves only to simplify the proof and can in principle be dispensed with.)。”
哥德尔证明的两个重要定理的原始陈述如下 [1-3] 。
“ 命题IX：在命题VI中言及的所有形式系统中，都存在有受限谓词演算的不可判定问题（亦即，受限谓词演算的逻辑式，其普遍有效性以及其反例的存在性都不可证）。”
“命题XI：如果c是一个给定的递归且一致的逻辑式类，则表达“c是一致的”之内容的命题逻辑式不是c-可证的；特别地，P的一致性在P中不可证，在假设P是一致的前提下（如果不是，那么当然，任何言明都是可证的）。”
命题IX所言及“命题VI中言及的所有形式系统”，是指称所有由脚注53所说明的系统：“从系统P通过添加了一个递归可定义 公理 类所得到的ω一致的形式系统(These are the ω-consistent systems derived from P by addition of a recursively definable class of axioms.)。”[1-3] 亦即，所有满足如下条件的形式系统/理论：基于经典一阶谓词演算的、至少包含了初等数论的、ω一致的形式系统 /理论 。
哥德尔在其证明中给出了在P中构造出命题IX所言及的不可判定命题的具体方法。
罗瑟(John Barkley Rosser Sr., 1907-1989)在1936年显示，哥德尔原始陈述中的前提条件“ω一致的”可以修改为“（经典）一致的”[14,15]。
正确理解命题IX之断言有两个关键，一是正确理解断言所针对的对象系统（亦即，断言的适用范围），二是正确理解“可证/不可证”这个概念。这里的“可证”是指在形式系统中可证，亦即，针对要证明的目标能够 在形式系统中 找到一个形式证明有穷序列；而目标的“不可证”就意味着 在形式系统中 不可能找到针对该目标的一个形式证明有穷序列。
命题IX通常被俗称为“第一不完全性定理”。一个形式系统/理论具有“经典完全性(classical completeness)”是说，对于该系统/理论的任意一个逻辑式，其本身或其否定的两者之一必然在该系统/理论中可证。请注意，从逻辑哲学的角度来说，经典完全性的定义是隐含地基于排中律的。既然PM及相关系统中存在有不可判定命题，那么这些系统依据经典完全性的定义就都是不完全的。所以，严格地说，PM及相关系统的不完全性应该是命题IX的一个（隐含地基于排中律的）推论。笔者认为，正是由于把命题IX称为“第一不完全性定理”，一旦人们对命题IX本身的前提条件以及对“可证/不可证”概念及“完全性”概念的理解有误，那么就会误解或者曲解命题IX的原本断定。
命题XI注明“在假设P是一致的前提下（如果不是，那么当然，任何言明都是可证的）”是因为P的形式化基础逻辑是经典一阶谓词逻辑，是一个爆炸的形式逻辑系统。
命题XI通常被俗称为“第二不完全性定理”，是命题IX的一个推论（只需在P中构造出一个不可判定命题使其内容为“P是一致的”），哥德尔只给出了证明框架，真正的形式化证明是1939年由希尔伯特和贝纳斯(Paul Isaak Bernays, 1888-1977)在他们的著作《数学基础》第二卷中所完成的 [7,10,16] 。
命题XI/第二不完全性定理显示了：对于一个基于经典一阶谓词逻辑的、递归的、一致的形式系统，表达其一致性的命题在该系统中不可证。于是，希尔伯特计划按照其原本的要求（亦即，限定于有穷方法）是不可能实现的。
关于哥德尔工作的原始陈述，参阅笔者的“哥德尔不完全性定理的原始陈述”[17]应该足够了。对于本文中涉及到的数理逻辑学专业术语不熟悉不了解的读者，请参阅笔者在本 微信 公众号及科学网博客上同步发表的 逻辑学 科普文章。
参考文献
[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 1930a), “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 (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,” in S. Feferman, et al. (Eds.), “Kurt Gödel: Collected Works,” Volume I, Publications 1929-1936, pp. 144-195, Oxford University Press, 1986.
[4] D. Hilbert, “Grundlagen der Geometrie,” Teubner, 1899.
[5] D. Hilbert, “Mathematisc he Probleme,” Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Math.-Phys. Klasse, pp. 253–297，1900 (in German) (Lecture Delivered before the International Congress of Mathematicians at Paris in 1900)
[6] D. Hilbert,“über die Grundlagen der Logik und der Arithmetik”, in Verhandlungen des dritten Internationalen Mathematiker-Kongresses in Heidelberg, 1904.
[7] 王宪钧, “数理逻辑引论 第三篇 数理逻辑发展简述”，北京大学出版社，1982, 1998.
[8] R. Zach, “Hilbert’s Program,” The Stanford Encyclopedia of Philosophy, Center for the Study of Language and Information (CSLI), Stanford University , 2003-2023.
[9] K. Gödel, “über die Vollständigkeit des Logikkalküls,” “On the completeness of the calculus of logic,”Doctoral Dissertation, University of Vienna, 1929, Repringted and translated in S. Feferman, et al. (Eds.), “Kurt Gödel: Collected Works,” Volume I, Publications 1929-1936, pp. 60-101, Oxford University Press, 1986.
[10] J. Dawson, “Logical Dilemmas: The Life and Work of Kurt Gödel,”A. K. Peters, 1997, 2005. 中译(唐璐译):“哥德尔：逻辑的困境”，2009.
[11] M. Davis, “Engines of Logic – Mathematics and the Origin of the Computer,” W.W. Norton, 2000. 中译(张卜天译):“逻辑的引擎”，2005.
[12] A. N. Whitehead and B. A. W. Russell, “Principia Mathematica,” Vol.1, 1910(1 ed.), 1925(2 ed.), Vol.2, 1912(1 ed.), 1927(2 ed.), Vol.3, 1913(1 ed.), 1927(2 ed.), Cambridge University Press.
[13] B. Linsky, “Principia Mathematica,” The Stanford Encyclopedia of Philosophy, Center for the Study of Language and Information (CSLI), Stanford University, , 1996-2021.
[14] J. B. Rosser, “Extensions of some theorems of Gödel and Church,” Journal of Symbolic Logic ， Vol. 1，No. 3, pp. 87-91, 1936.
[15] E. Mendelson, “Introduction to Mathematical Logic,” Chapman & Hall, 2015 (6th Edition)
[16] D. Hilbert and P. Bernays,“Grundlagen der Mathematik”, Vol. 1, 1934, Vol. 2, 1939.
[17] 程京德，“哥德尔不完全性定理的原始陈述”，微信公众号“数理逻辑与哲学逻辑”，2023年3月13日。
微信公众号“数理逻辑与哲学逻辑”
转载本文请联系原作者获取授权，同时请注明本文来自程京德科学网博客。 链接地址： https://blog.sciencenet.cn/blog-2371919-1439739.html
上一篇： 相关逻辑 (4) - 形式语言 下一篇： 自动定理发现领域的创始者 - 沃斯