哥德尔的两个不完备定理是上世纪逻辑学中最重要的定理，拜科普读物所赐，同时也是受误解最多的定理。本文试图讲清哥德尔不完备定理到底在说什么并澄清一些误解。为了不把本文写成数理逻辑教材，我会尽量使用自然语言叙述[0]。本文第一部分简单介绍不完备定理的历史和内容。第二部分采用问答体，力求解释一些常见的问题。其实第二部分才是本文重点，如果觉得第一部分太枯燥可以直接跳过。 I. 简介1. 形式系统 最早的数学定理都是用自然语言写的，但随着数学的内涵越来越丰富，自然语言在表达数学概念时显得越来越啰嗦（比如本文= =）。为了简化表达，数学家们开始越来越多地用符号来表达数学概念，这种情况发展到极端后自然语言被彻底地抛弃，数学完全的符号化，这种语言就被称为形式语言。比如『对任意自然数n，n都大于等于0』，用一阶语言形式化之后变成 ∀n∈N.n>=0 。 数学家又发现人的推理过程是可以看做符号变换的。比如『已知命题A，又已知命题A能推出B，那么B成立』这条规则可以抽象为 A, A→B |- B [1]。这样一来数学证明可以完全变成机械的符号变换游戏，哪怕你不懂这些符号什么意思，只要你记住规则，就能证明出一个个数学定理。这听起来非常诱人，于是数学家制定了形式语言的语法，把符合语法的句子称为命题，又选出一组命题称为公理，最后制定了一组推理规则，这样给你公理，根据推理规则，你就可以推出许多被称为定理的命题。这套系统就被称为形式系统。从公理推出定理的过程就被称为证明，推出命题否定形式的过程自然就被称为证伪。 仔细想想，这里面其实有个问题：我们怎么确定这套推理系统是对的呢？换句话说，我们怎么知道推出的命题是真命题呢？理论上说，数学可以完全无视现实世界，从任意的公理出发推出任何命题，但我们还是希望我们研究的数学能解决现实问题，所以我们要确保我们的形式系统确实是在描述我们想要的数学理论。为了解决这个问题，数学家为形式语言建立了语义，换句话说，就是把形式语言的符号翻译成我们已知的东西[2]，这样如果推出的命题翻译过来是错的，那么我们就需要修改推理规则，直到其语义符合预期。而符合语义的命题我们就称为真命题。后来逻辑学家发现，一种叫一阶语言的形式语言有非常好的性质，用一阶逻辑表达的形式系统，不管你给公理什么语义，只要公理都为真，那么所有能推出的命题都是符合这个语义的真命题[3]，所以现在大部分形式化的数学理论都用一阶语言表达，包括目前数学的基础：ZFC公理集合论[4]。 2. 希尔伯特计划 既然形式系统这么好，那么能不能把所有数学都形式化呢？以后也不用费脑子证明了，直接扔给机器穷举，一吨吨的数学定理就造出来了。 希尔伯特觉得：能！ 他畅想了一个美好的未来，所有的数学理论全都用一种形式语言来描述，并且这套系统满足如下四个性质—— 完备性：任意一个符合这个形式系统语法的句子，也就是一个命题，都能证明或证伪。 一致性：这个系统不会同时推出一个命题和它的否定。 可判定性：如果给定任意定理，可以用算法在有限步内判定真伪。 保守性：证明可以不依赖『理想对象』（比如不可数集合）。 而且更重要的是，这四个性质还要在这个系统内被证明。 这个想法倒是非常美好，但就在希尔伯特退休后一年，即1931年，哥德尔的两条不完备定理直接宣判了希尔伯特计划的死刑。 3. 哥德尔不完备定理 我们先来看不完备定理说了什么—— 第一不完备定理 一个包含皮亚诺算术的形式系统如果是一致的那么是不完备的。 第二不完备定理 对于一个包含皮亚诺算术的形式系统，该系统的一致性不能在系统内部证明。 我先来解释一下皮亚诺算术是什么。皮亚诺算术是一套用一阶语言描述的形式系统，它被用来刻画自然数以及基本的自然数算术，比如加法、乘法和乘方。那『包含皮亚诺算术的形式系统』是什么意思呢？直观上理解，就是说从这个形式系统中，可以推出一组命题，这些命题可以描述自然数以及算术。比如ZFC集合论就是包含皮亚诺算术的系统，你可以用 Φ、{Φ}、{Φ,{Φ}}...来表示1、2、3……，用集合操作来模拟自然数上的运算，所以有些命题是不能在ZFC中证明或证伪的，ZFC也不能证明自己是一致的；再比如图灵机也是一个包含自然数的形式系统，而停机问题可以理解为这个系统里无法被证明和证伪的命题。 哥德尔的两个不完备定理直接戳破了希尔伯特的梦想：包含算术的形式系统不可能完备，而且这个系统本身的一致性不能在系统内被证明。后来图灵的停机问题又摧毁了希尔伯特对可判定性的期待。 II. 一些澄清1. 所有的理论都是不完备的吗？ 显然不是的。比如平面几何，你不能从平面几何推出皮亚诺算术，因为平面几何是个完备的理论。而且哥德尔给出的『包含皮亚诺算术』的限制其实都很强了，给一个弱得多的限制，理论依然是不完备的。哥德尔提出第一不完备定理后不久，Rosser就给出了一个更强的（更强的意味着限制更弱）不完备定理：一个系统只要包含罗宾逊算术就足以产生不完备性了（罗宾逊算术只有加法和乘法）。哥德尔当时强调皮亚诺算术（原文其实更模糊，是『基本算术』），主要是针对希尔伯特计划。希尔伯特想把所有数学都形式化成一套系统，然后把证明归结成基本的自然数算术，再在这个系统内证明自然数算术是一致的，这样就完成整个数学的形式化，结果被哥德尔无情打脸。 另外，哥德尔不完备定理其实还有个隐藏限制，那就是形式语言的公式集必须是递归集合，换言之，你的公式必须可以从有限个符号经过有限步构造出来[5]。如果你用像实数那么多的符号来表示，哥德尔不完备定理就失效了，但这毫无意义，因为人类没办法写出这种语言。同样的，如果你能造出『实数计算机』，那停机问题也可以解决了。 2. 那我不用形式语言描述理论，是不是可以避免不完备性？ 这么说倒也没错。哥德尔的证明是先把形式语言编码成自然数，然后证明『所有自然数代表的公式集合』是比『能推出的所有公式的编码集合』更大的集合[6]，所以总有公式是证明不出来的。如果理论用自然语言描述，自然语言没有确定的语法，也就无法编码了。但是如果你不能精确定义语言，你也无法精确定义『证明』、『真』这样的概念，又怎么保证你证明得对呢？而且用形式语言和用自然语言描述的理论本质是一个东西[7]，这就好比一个命题不管你用汉语说还是英语说，真假都一样。所以形式系统的不完备性也可以当做直觉上数学理论的不完备性。 另外用形式语言可以起到区分元理论和对象理论的作用。元理论是指描述这个形式语言的理论，而对象理论是用这个形式语言来描述的理论。其实我刚才说『一个命题不管你用汉语说还是英语说，真假是一样』是不准确的，比如『这句话是汉语』这句话，翻译到英语就是假的，但是这句话其实是一个元理论的命题，它描述了写『这句话是汉语』的语言本身，所以它不是汉语这个系统内的命题。再比如上一段中『哥德尔的证明是先把形式语言编码成自然数，然后证明「所有自然数代表的公式集合」是比「能推出的所有公式的编码集合」更大的集合』这句话，句中的『证明』和形式系统里的『证明』就不是一个层面的词。如果数学命题都用自然语言描述，就会出现很多元理论和对象理论混淆的情况。 3. 哥德尔不完备定理用了哪些公理呢？ 根据哥德尔在他自己的论文On Formally Undecidable Propositions of Principia Mathematica and Related System中所说，他是在罗素和怀特海一起创立的PM形式系统里进行证明的[8]，用到的元数学概念是自然数算术。 4. 不完备定理依赖算术又说算术是不完备的，这不是循环论证吗？ 这得从哥德尔本人的哲学立场说起。哥德尔是个柏拉图主义者，在柏拉图主义者眼里，数学对象都是永恒存在于独立于现实世界的理念世界里的。既然数学天然存在，那推理就不是数学定理存在的前提，而是发现数学的工具。这就好比人们根据天王星的轨道偏差推理出海王星的存在，不能说海王星因为人的推理而存在。所以，虽然哥德尔用了算术知识来证明不完备定理，但不能说不完备定理依赖算术而存在。这只表示哥德尔相信他用的知识是必然正确的，他用这些知识推理出一个对数学世界普遍成立的规律。 但很多数学家认为数学就是从公理中推出来的，是人类思维的创造。如果站在这个立场，那哥德尔确实有循环论证之嫌：他在算术里讨论了一个元算术的性质。所以这个定理更多地被视为哲学或逻辑学定理而不是数学定理[9]。注意这不是说哥德尔证错了，只是说哥德尔已经到数学和哲学之间模糊的边界了，甚至可以说他是在数学外观察数学。至于到底什么是数学，现在没人能回答得了，大部分数学家也不在乎这个问题，ZFC作为数学基础已经足够好了，空谈主义并不能帮助数学家解决实际问题。顺便一提，现在倒是有不少计算机科学家在做数学基础的研究…… 一般来说，不管什么哲学立场，不管讨论多么基础的对象理论，元理论都会包含一点基本的算术，否则我们连定义符号、语法都不行，形式化更无从谈起。 5. 计算机是个不完备的形式系统，但是人能证出哥德尔不完备定理，是不是说明人脑比计算机强？ 这是个广为流传的误解。计算机是可以证明哥德尔不完备定理的，Lawrence C. Paulson就用Isabelle这个软件证明了哥德尔不完备定理[10]。虽然目前计算机只能处理形式化的数学，但是你可以先形式化一些基础的结论，然后把其他数学理论在这个形式系统里再形式化一遍，最后证明这些形式系统内的形式系统有不完备性。顺便夹个私货，作为物理主义者，我相信人脑理论上是能用图灵机模拟的，但是能不能造出来、或者造出来能不能被人理解就不好说了。 6. 物理学需要数学，哥德尔不完备定理是不是意味着我们永远无法理解宇宙？ 这个问题不好说。我倾向于认为哥德尔不完备定理和物理没多大关系。首先，物理定律只是在用数学，而不是创造数学。假设你发现了宇宙最基本的定律，几个方程组可以求出一切物理量，那你也不需要用这个方程组推出自然数、有理数等概念，只要它们能描述你观察到的一切现象就行。再者，宇宙里所有粒子或别的什么基本单元也可能是有限的，你给它们用自然数编号，哪怕一个粒子用一个公式描述，那也是递归集，并不会有不完备性。 注释[0] 写完本文我深刻地体会到用任何自然语言来描绘数学都是苍白无力的，这也算是Quine的翻译不确定性的体现吧。这里推荐几本教材：郝兆宽、杨睿之、杨跃的《数理逻辑》（支持国产教材，而且确实写得很棒），Ebbinghaus的Mathematical Logic, 2nd Edition（很好懂，内容涉及很广，适合开阔眼界），Enderton的A Mathematical Introduction to Logic, 2nd Edition。 [1] P|-p表示给定公式集P，根据推理规则一定能推理出公式p，换句话说，给定公式集P肯定能证明公式p。另一个相似的符号是“|=”，P|-p表示对所有能使P中公式都为真的语义，也都能使p为真，换句话说，不管你怎么翻译，P和p的真假都是一致的（这个一致就是汉语里一致的意思，不是逻辑里一致性的意思）。 [2] 选取不同的数学基础，可以把语言翻译到不同的数学对象上。由于目前ZFC是大多数数学家公认的基础理论，所以标准语义都把变量翻译到一个被称为论域的集合上，把函数和关系符号翻译成论域上的函数和关系，这样的标准语义也被称为模型。研究标准语义的理论被称为模型论，比较经典的教材是C.C.Chang和H.J.Keisler的Model Theory（没看过）；以及David Marker的Model Theory: An Introduction（例子特别多，强推）。比较著名的非标准语义是高阶逻辑的Henkin语义，是一种代数语义。 [3] 这个性质叫soundness，用符号表示是：给定一个公式集P，如果P|-p那么P|=p。反过来的性质叫completeness：给定一个公式集P，如果P|=p那么P|-p。注意这个completeness不是哥德尔不完备定理里的incompleteness的反义词。一阶语言，或者说一阶逻辑，又有soundness又有completeness。 [4] 想学习集合论，我强推Kenneth Kunen的Set Theory: An Introduction to Independence Proofs，时不时地会讲讲哲学背景，非常有趣。Thomas Jech的Set Theory太形式化了，第一次看会非常痛苦…… [5] 递归集是指『某元素是否存在于该集合中』可以用算法判断出来的集合。至于什么叫『算法』，[0]里提到的数理逻辑教材都有讲。另一个相似的概念是递归可枚举集，指在集合中的元素可以用算法判断出来，但判断元素不在集合中可能会让算法死循环。 [6] 前者是递归可枚举集，后者是递归集。哥德尔写证明那年还没有递归可枚举集这样的概念，但是意思是一样的。后来图灵搞出图灵机把可计算函数直观化，哥德尔高度赞赏了他的工作。 [7] 这么说其实不是很准确，极端的形式主义者会认为只有形式化的数学才是数学。 [8] 原文是德语，这个题目是B. Meltzer翻译的论文的题目。根据哥德尔的叙述，当年最火的两个形式系统一个是PM，一个是ZF。 [9] 语出哲学家R. B. Braithwaite在B. Meltzer翻译的On Formally Undecidable Propositions of Principia Mathematica And Related Systems前言。 [10] Paulson L C. A machine-assisted proof of Gödel’s incompleteness theorems for the theory of hereditarily finite sets[J]. The Review of Symbolic Logic, 2014, 7(3): 484-498. |
|
|
