人工智能时代：破解人机共存密码（套装共10册）

亲爱的战友：

我完全同意您的观点，您所论证和讨论的问题的重要性是很多逻辑学家的工作都无法比拟的。

我就有一个小小的困惑想向您讨教，考虑那个不包含任何元素的集合，它是否包含自己呢？

例如，如果以所有集合为元素组成的集合U，便符合U∈U的条件。但一般的集合，例如北京大学的所有同学的集合V，便不是它本身的元素V∉V。现在我们用A表示所有不以本身为元素的集合所成的集合，即若x∈A，则x是一个集合，且x∉x，现在我们问A∈A是否成立？即A是否包含它自己。若 A∈A，则A具有A的元素的性质，A就是A的元素，但A明明是所有不以本身为元素的集合，这与A的定义矛盾；反之，若A∉A，则A不具有A的元素的性质，因此A符合A的定义，它是不包含它自己的集合，即 A∈A 成立，这也是矛盾的。但A∈A和A∉A二者之一必成立，所以矛盾是躲不掉的，这样就形成了悖论。

罗素本人并没有把包袱丢给弗雷格，他接下来花了十几年时间来研究这个问题，写了厚厚的三大本《数学原理》，试图绕开这个逻辑悖论。数理学家、哲学家约翰·凯梅尼（John Kemeny）后来说罗素的《数学原理》是一本“被每个哲学家谈论，而实际上又无人读过的伟大著作”。罗素希望绕开悖论的策略大致是这样的：我们可以定义不同层次的语义和逻辑规则，通过控制这些语义和逻辑规则，有可能划分出来一条清晰的渠道，来避免自指问题的发生。即，通过严格的语义和语法的层次分割来避免发生陈述指向自己的情况。

关于数学的本质，罗素有一个著名的论断：纯数学是这样一门学科，在其中我们并不知道我们在谈论什么，或者我们不知道我们所谈论的是否是真的。这精辟的评论直接切入希尔伯特伟大工程的核心——为全部数学构建一个纯语法的框架。希尔伯特受到刺激的主要原因是，他感觉到，类似于罗素悖论中的核心问题，是由于陈述中悖论性的语义内容所导致的。希尔伯特相信，根除在数学中出现这种悖论的办法，就是建立一种实质上无意义的元数学框架，我们在其中可以谈数学陈述的真或假。这样的框架构成了数学的形式系统，也构成了数学中研究“什么是可证明的”与“什么实际上是真的”这两者之间的鸿沟的历史性起点。基于对完美形式系统的期望，希尔伯特开始了他的伟大工作。希尔伯特的数学终极理性是这样的：

1.将整个数学体系严格形式化；

2.用元数学来证明整个数学体系是建立在牢不可破的坚实基础上。

除去罗素的怀疑，元数学系统已经可以完全形式化：将系统内的所有表达式的意义都抽掉，把它们视为空洞的符号，按照事先规定的一组规则，对这些符号进行操作。这样我们就可以构建一个本身没有任何意义的符号系统来演算或者推演。这套符号系统的所有含义都由我们外部加以定义。这件事情其实并不抽象，考虑一台计算机，那么计算机的制造者并不关心我们拿这台计算机来做什么，写文章、编程序、打游戏还是看电影。他们只是按照已经设计好的规则来做芯片，焊接电路，把零件组装在一起，再安装一套操作软件。计算机本身就可以看作是这套元数学符号演算规则在物理世界的体现。因此具体实施的步骤也有了：

1.将所有数学内容形式化，用确定而唯一的符号表达，彻底摆脱自然语言的模糊。

2.证明数学的完备性，我们能够证明所有的真理，只要是真的命题就可以被证明。

3.证明数学的自洽性，数学本身不会自相矛盾，确保我们在不违背逻辑的前提下获得的结果是有意义的，不会出现某一个陈述，它既是真的又是假的。

4.数学的可判定性，我们可以找到一个算法，自动地、机械地判定数学陈述的对错。

在这个大背景下，罗素的《数学原理》提供了一套全面的符号系统，借助于这套符号，所有的纯数学命题（特别是数论命题）都可以用一种标准的方式来表示；同时《数学原理》明确了数学证明所用的大多数形式推理规则。

语义和语法

亚里士多德的逻辑学有两个支柱：不经证明而被看作真的前提或公设；保证从一个真陈述变换为另一个真陈述所使用的推理规则。我们以古典逻辑中的亚里士多德三段论为例说明，这样的结构也常常被称为大前提、小前提和结论。

大前提：所有人都要上学。

小前提：小明是个人。

结论：小明要上学。

在这里，大前提和小前提被设想为关于人、关于上不上学和关于一个特定的人——小明的真陈述。从大前提、小前提到结论的得出，这中间利用了由亚里士多德概括的演绎推理律中的一个，“如果所有X都是Y，且Z是一个X，那么Z是一个Y”。只要我们可以确信前提为真，那么小明要去上学这个结论就是牢靠的。确定性来自前提的语义内容，来自我们的心智所确定的演绎过程。

但是，我们看下面这个例子：

证明：亚里士多德是工作。

这是严格按照三段论推导出来的结果：

1.亚里士多德是哲学家。

2.哲学家是工作。

3.所以，亚里士多德是工作。

上面这个结论恐怕连亚里士多德本人也不会认同。

这个推论中蕴含了语义悖论。因为语句1中的“哲学家”和语句2中的“哲学家”不在一个语义层次上，前者是对象概念，后者是词汇的元概念。两个前提内涵不一致，结论就荒谬了。这种逻辑错误很多时候会将我们带入类似于“理发师悖论”。比如当我们谈到“这句话是错的”的时候，我们显然是在两个层次上谈论。从语义和语法的角度区分，能不能回避因为混淆这两个层次的概念而造成的自己指向自己的悖论呢？造成逻辑悖论的所有情况，都是类似于它们以所谓的自指概念为基础。一个典型的例子是“说谎者悖论”（Liar’sparadox）：

克里特岛的一位居民说：“克里特岛上所有的人都说谎。”

“这句话是错的”，这个陈述中包含了真的概念。但我们会看到，哥德尔事实上证明了真概念不可能在正被谈及“真”的那个形式系统的界限内被加以把握。

首先，我们定义一下要用的名词，用普通数学语言来描述的直觉算术（intuitive arithmetic，以下称为IA），IA里的陈述句表达有关算术性质的真伪，它有确定的语义的意义，真实表达了某一算术的概念和性质。

接下来是算术的形式推演系统，在哥德尔的推演中，他使用了罗素在《数学原理》中定义的纯语法系统，系统中给定一组公设和明确的推演规则，通过这组公设和规则，可以决定哪些句式是定理，这称之为形式算术（formal arithmetic，以下称为FA），FA的陈述没有具体的语义，它本身并不代表性质意义上的真伪。

当IA和FA一一对应的时候，FA就被赋予具体的含义，FA的符号会被赋予对应于IA的算术性质。我们也可以把直觉算术IA描述为目标性表述，形式算术FA理解为方法与形式的描述。FA被设计成IA的镜像。如果一切依计划，FA中的数字符号和IA中的数字会有一一对应的关系，而且IA中为真的陈述句和FA中的定理也会有确实的对应。简言之，FA是用来表示IA的。

《数学原理》里的公式原来只是无意义的字符串，无关真假，能够用演绎规则从公设和其他定理推演出来的陈述，被称为定理，这个过程称为形式证明。将一些符号解释成逻辑关系，赋予公设真值，一些公式便有了逻辑的含义，它们被称为命题，定理便是逻辑上为真的命题。将FA的符号解释为算术符号，哥德尔用正式证明前的46条定义和预备定理，建立起元数学真理和算术命题的对应关系，因此赋予了这些公式的数学含义。元数学是在（数学原理）上层谈论公式的性质和关系的语言。

第三种语言或理论是形式算术的后设理论，也就是用来清楚地说出FA的语法规则和证明理论的语言和理论：这个语言成为超形式数学 ， 是 描 述 形 式 算 术 的 形 式 算 术 （ metatheory of formalarithmetic，以下称为MFA）。换句话说，如果FA是机器，MFA就是它的操作手册。MFA是用来说明FA这台机器是如何运作的。和IA一样，MFA也是由具有意义的陈述句组成的，其中的陈述句皆可依照它的意义来判断真伪。MFA规定FA中哪些语句是良性句式（well formedformula，以下称为WFF），也就是哪些陈述句满足构建句式的规则，也同时规定了FA的证明是什么意思。

希尔伯特的一个洞见对哥德尔的证明具有相当大的启发。希尔伯特意识到数学分支的每一个形式化本身便是一个数学对象。在此以前，哥德尔已经发现可以通过使用自然数本身来镜像反映有关自然数之间关系的所有陈述。这是相当关键的一步，它使对象自己述说自己成为可能。

哥德尔发现FA不但可以用来表示IA，同时也可以代表MFA。他利用现 在 被 称 为 后 设 数 学 的 算 术 化 （ arithmetization ofmetamathematics）的革命性方式，证明IA可以代表MFA。但如果FA可以代表IA，那么也可经由MFA在IA中解读的方式来代表MFA。因此FA可以代表它自己的后设理论。接下来就是构建一个FA中的语式，该陈述同时在IA和MFA两种语言中有两种意义。哥德尔找到了这样的陈述，可以同时在FA中为不可证并直观上在IA和MFA中为真。这个陈述可以在FA中证明为不可证，但又在IA中代表一个为真的有关自然数的陈述句，同时又在MFA中成为有关它自己的不可证明为真的陈述句。哥德尔的第一步工作，就是证明FA可以用来代表IA。这部分工作事实上被皮亚诺公设系统完成了，即一套适用于数论基础的严格逻辑规则。第二步需要证明FA可以表示MFA。通过哥德尔所用的配数方法，哥德尔首先系统地将FA中的基本符号编号，接着证明如何以序列的基本符号，也就是陈述，对应到自然数，不同的序列因此会有不同的编号。接着就可以为一序列的陈述来编号，一个证明就是一序列的陈述，因此也可以将证明对应到自然数。

真概念不可能在正被谈及“真”的那个形式系统的界限内被加以把握，为了避开永远难以捉摸的真与假的概念，哥德尔意识到应该用某种可以形式化的东西来代替“真”，这就是“可证性”的概念。于是，哥德尔利用他的编码方案，通过46条引理来编码上述悖论，并将其翻译成：

这个陈述是不可证的。

这被称为哥德尔陈述，我们用G–S来代替。哥德尔的思路是：对于每一个形式系统，总可以构造出一个从系统外来看是真的，但在系统内却不能判定的陈述G–S。接下来我们讨论一下这个论断的逻辑结果：

如果哥德尔陈述G–S是可证的，由于陈述G–S是真的，根据论断，它不可证。因此，在这个系统中，陈述G–S和它的否定都成立，所以，这个系统是不自洽的。

如果哥德尔陈述G–S是不可证的，由于陈述G–S是真的，但是不可证，所以系统中至少有一个命题，它是真的，但其正确性无法被系统已知的定理证明，所以，这个系统是不完备的。

于是哥德尔得出了“对于算术的任何自洽的形式化系统，都存在着在该形式系统内不可证明的算术真理”这一惊人的结论。

让我们试图用通俗（不太严格）的说法来理解哥德尔的不完备定理，以及他的证明方式。

首先将哥德尔的两个不完备定理翻译成通俗语言：

1. 一个算术系统，要么自相矛盾，要么总能得出一些包括在该系统中但无法判断真伪的结论；

1. 不可能在一个算术系统内部，证明此系统没有自相矛盾的。

哥德尔用“可证性”概念代替“真”的概念，然后把悖论“这句话是错的”拓展为论断“这个陈述是不可证的”。进而证明语句“这个陈述是不可证的”有一个算术的对应陈述，即在算术形式化中有一个自然数对应为哥德尔陈述G–S。在此基础上，他需要做的证明就变成了：

1.不完备性：证明如果该形式系统是自洽的，则此哥德尔陈述必定是真的，但它陈述了自己不可证。

2.不完备性附则：证明即使补充的公设加进来构成了新的系统，使得这个陈述G–S在其中可证，含有补充公设的新系统仍有它自己的不可证的哥德尔陈述。

3.自洽性：构造一个算术陈述，它断定“算术是自洽的”。证明这个算术陈述是不可证的，故此证明，算术作为一个形式系统不足以证明自己的自洽性。

接下来FA还有所谓形式正确（well formed）的要求，以及更重要的，由一个字符序列组成的陈述是否能构成证明的问题。哥德尔证明的是，要完整描述FA语法所有的必要概念和函数，包括形式正确的语句和证明，都对应到IA中一些特定的递归函数。直观上来说，所谓的递归函数就是可以用机械方式计算的函数。这类函数也可以严谨地用数学的语言来刻画其特性。

哥德尔证明了FA中MFA的基本概念或证明理论，可以对应到IA中某些特定的递归函数。在证明FA可以表示IA的过程中，哥德尔证明IA中的任何递归函数，都可以在FA中表示出来。说得更明确些，如果在IA中有关于某一递归函数的真实叙述，就会有一个FA定理为其对应的陈述句。一旦他成功证明MFA中的基本函数，若以数字来编码会产生递归函数，就可以得到MFA，正如IA一般，可以在FA中表示。以算术的方式编码处于不同语义层次的逻辑表达式是哥德尔得出不完备定理的重要一步。哥德尔发明的这种方式可以使用算术语言本身对算术中的所有可能的陈述进行编码，通过自然数本身来镜像反映有关自然数之间关系的所有陈述，即算术既可作为被解释的数学对象，又可作为谈论自身的未被解释的形式系统。在形式系统内部构造一个命题，又表明它在系统中不可判定，哥德尔由此推出自洽性在系统自身中的不可证。

通过哥德尔配数，哥德尔把FA的语法算术化了，因此有关FA的语法事实，可以对应到IA总有一个有关自然数的事实。这样一来，哥德尔证明了FA中的理论可以同时代表IA中有关算术的事实，以及通过哥德尔配数代表MFA语法的事实。也就是说，FA中的定理，将可以代表IA中的一个数学真理，而该定理本身通过哥德尔配数可以代表有关FA的语法真理。如此，哥德尔成功地证明了FA本身虽然是一个没有意义的形式化符号系统，却可以通过一语双关的方式被赋予两种不同的意义，以确保其可用来同时表示数论和语法，这里的语法指的是FA本身的证明理论。换言之，通过自然数，FA中的陈述句可以表示FA本身。

哥德尔接下来居然证明了算术是数学复杂性的分水岭。

哥德尔特意声明，他的结果的根本点不在于任何形式系统都无法包罗全部数学。这一点从康托的对角线法已经能得出了，他并未排除数学的某些相当强的子系统具有完备性的可能。相反，哥德尔的结果的根本点在于每一个既含加法又含乘法的数学形式系统都包含一些颇为简单的命题，可以在该形式系统中被表达出来，但不可判定。

哥德尔的定理说，如果一个形式系统是：

1.有限大的；

2.足够大以包括算术逻辑；

3.自洽的；

则它是不完备的。

算术结构在哥德尔不完备定理的证明中起着核心作用。数字的特殊属性，例如任何数字都可以作因式分解，表达为一些质因数的乘积（例如“130=2×5×13”），哥德尔考虑用一种方法来建立数学性质和关于这些性质的陈述之间的对应关系。他成功的证明了像“说谎者悖论”这样的自然语言陈述悖论可以像自然数一样嵌入描述数学性质系统所用的语言结构中。只要足够丰富的逻辑系统包括算术就不得不包容这些悖论。要是我们选择了一个理论，该理论仅包括前十个数字

（0，1，2，3，4，5，6，7，8，9），这个阉割版的算术可以是完备的。它一样可以生成有关个别数字的陈述，如加法和乘法运算。欧几里得几何只描述连续的点、线和面，一般来说，它不能包含所有算术的逻辑。因此欧几里得几何是可以完备的，同样，非欧几里得几何也是完备的。如果我们有一个逻辑理论处理只使用这个概念的数字“大于”，没有提到任何具体的数字，那么它将是完备的：我们可以判定关于仅涉及的实数大小关系的陈述的正确与否。

“小于”算术的系统的另一个例子是没有加法而只有乘法操作。这叫作Presburger算术（皮尔斯伯格算术）。它是个完备的算术版本，但是是“阉割”过的版本，即如果有加法就不能有乘除法。起初这听起来很奇怪，我们在日常中遇到的乘法只不过是作为加法的简写方式（例如“2+2+2+2+2+2+2=2×6”），但是算术的完备逻辑系统存在逻辑量词，如“存在”“任何”，乘法允许结构不仅仅是等价的一连串的加法的简单补充。

Presburger算术是完备的：所有关于添加自然数的陈述数字可以证明或反驳；所有正确的命题都可以从公设中得到。同样，如果我们创建另一个“阉割”版本的算术，没有加法但保留乘法，这也是完备的。只要加法和乘法同时存在，不完备性就会出现。延伸系统通过向基本操作添加指数等进一步额外操作也不会带来结构性上的任何区别，不完备性仍然存在。

哥德尔不完备定理的证明

接下来的内容会比较有难度，但为了表达对哥德尔的敬意，我们重新走一下那个奇妙而又幽默的智者走的路，当然，你也可以赤裸裸地跳过，知道结果就好。