当我们谈论数学，我们在谈论什么？

是高中时的“得数学者得天下”，或是大学时令人头痛的微积分，抑或是似乎在工作后“数学无用”的感叹？

实际上，数学是一门被广泛应用于各个领域的学科，不仅在学术研究中有广泛应用，它在生活中也随处可见。

数理逻辑是数学中非常基础和重要的分支，从20世纪发展至今已经有近百年历史，它是当代哲学、数学、理论计算机科学的共同基础。计算机、大数据、人工智能、医学诊断的发展都离不开它。

举个例子，在使用ATM机或者收银机时，这些设备内部都是依靠基于数理逻辑的电路和算法在运行，从而保证它们的正确性和稳定性。

当你越走近这个奇妙的“数理逻辑”世界，就越会发现它深刻、有趣而又富于挑战的魅力。

何为“数理逻辑”

数理逻辑无非是形式逻辑的精确的与完全的表述，它有着相当不同的两个方面。一方面，它是数学的一个部门，处理类、关系、符号的组合等，而不是数、函数、几何图形等。另一方面，它是先于其他科学的一门科学，包含着所有科学底部的那些思想和原则。正是在第二种意义上，莱布尼兹在他的《通用文字》中首先构想了数理逻辑，原本可作为其中的一个核心部分。

——哥德尔

就字面意思而言，“数理逻辑”至少包含两方面的含义。一是“使用数学”，即以数学为工具来研究逻辑；二是“为了数学”，以数学里面出现的或是数学家常用的逻辑为研究对象。

首先，我们使用数学的符号语言，这种语言本质上可定义为自然数和自然数的序列这样的数学对象。我们还频繁地使用数学中的各种工具，如数学归纳法、紧致性定理等；频繁地引用数学中的定理，如数论基本定理、中国剩余定理、佐恩引理等；并且我们的研究成果（所下的结论）也都是以数学定理的形式表述的。从这一角度来看，与用数学研究几何图形或物理方程没有太多区别，只不过我们的研究对象是逻辑而已。

其次，数理逻辑的研究目标归根到底是要指出哪些命题是真的，而且是不依赖于物理世界的事实而为真的；哪些证明或推理的形式是正确的，它们正确的依据又是什么。例如，2 + 2 = 4 是真的，但这不依赖于“两双鞋子的总数”或“汽车前轮加后轮的个数”这样的物理事实。它的真必定植根于关于另外一个世界的另外一些事实中。再如，勾股定理的证明是正确的，它的正确性并不依赖于我们对任何一个直角三角形的直角边和斜边的测量结果，而必定依赖于另外一些非物理对象的属性。

这些例子足以说明，为什么只有在逻辑与数学结合后才成为深刻、“伟大”的学科。因为究其本性，逻辑研究的现象是超越于物理世界和物理事实之上的。在这里，没有任何物理意义上的偶然性。另外还值得一提的是，虽然这个超越物理世界的宇宙尚属于神秘之域，我们对其知之甚少，但有一点是可以肯定的：它是无穷的。而处理无穷世界带来的困难是数理逻辑发展的主要推动力之一。

以上两点综合起来，就是沙拉赫所说的，数理逻辑是以“数学的方式研究数学”。事实上，数理逻辑主要研究的是数学证明形式的“对错”、数学语句的真假以及数学结构的性质。所谓“以数学的方式研究数学”，就是将数学语句、数学结构、数学证明等作为数学对象，然后用已有的数学理论研究它们的性质。

当然仅停留在字面上的解读是远远不够的。例如，从以上的解读中，我们还看不出数理逻辑和哲学有什么关系，看不出为什么全世界的哲学系都要开设数理逻辑的课程。这当然很难用简短的篇幅进行解释，也不是本书要解决的问题。不过，那个逻辑事实植根于其中的、超越于物理世界的宇宙是什么样的存在呢？无穷究竟有哪些特别的性质呢？这不都是一些关乎根本的哲学问题吗？

也许，只有通过学习数理逻辑，熟练地掌握它的内容、方法和技巧以后，才能真正开始讨论“什么是数理逻辑？”这个问题。不过到那时候，你可能会想起陶潜的诗句：“此中有真意，欲辨已忘言。”下面简单介绍数理逻辑早期发展的历史（近期的发展请参照结束语部分）。这类似于勾勒一个本学科的简明“历史地图”，也许有助于读者了解自己所处的位置和将要前进的方向。

逻辑史早期的几个重要里程碑

亚里士多德

亚里士多德是古希腊思想的集大成者（不仅限于逻辑学）。他研究了三段论和其他各种形式推理，逻辑学代表作为《工具论》 。在之后的两千多年中，尽管有中世纪的宗教学家和学者有零星的逻辑学研究成果，但没有重大突破。康德曾经说过：“……从亚里士多德时代以来，逻辑在内容方面就收获不多，而就其性质来说，逻辑也不能再增加什么内容。”亚里士多德的形式逻辑不能称为数理逻辑。他使用自然语言，而且也没有讨论量词等概念。

莱布尼兹

在人类文明史上，莱布尼兹可以与文艺复兴时代的任何一位巨匠相提并论。他26岁时的工作使他与牛顿一起成为微积分的共同创立者。在逻辑史上，莱布尼兹被称为“数理逻辑的先驱”。

他有一个伟大的设想，试图建立一个能够涵盖所有人类知识的“通用符号演算系统”，让人们讨论任何问题，包括哲学问题，都变得像数学运算那样清晰。一旦有争论，不管是科学上的还是哲学上的，只要坐下来算一算就可以毫不费力地辨明谁是对的。

他的名言是：“让我们来算吧。”这一伟大的设想后来被称为“莱布尼兹之梦”。但是，莱布尼兹的许多工作在当时并不被人所知，在他死后很久才得以发表，或许这也是康德认为没人超越亚里士多德的原因吧。值得一提的是，很多哲学家研究逻辑的出发点都是试图为人类理智建立一个坚实的框架或系统，而这样的框架或系统很自然地涉及数学工具。

布尔

布尔的主要贡献是把逻辑变成了代数的一部分，从而向“让我们来算吧”的方向跨出了重要一步。简单地说，布尔把逻辑中对真假的判断变成了代数中符号的演算。所谓布尔代数即是以他命名的。大致上说，亚里士多德形式逻辑的所有规则都可以用布尔代数重新表述出来。

弗雷格

弗雷格是莱布尼兹之梦的实现者，是现代数理逻辑的创始人。他一生致力于数学基础的研究，试图从纯逻辑的概念出发定义出全部数学，从而使数学成为逻辑的一个分支。这一纲领被称作“逻辑主义”。他的工作对分析哲学（有人称他为“分析哲学之父”）、现代逻辑和数学基础都有极其深远的影响。

我们将要学习的一阶逻辑就是源自他的理论。他第一个引进了量词，同时把谓词处理为函项，这从根本上改变了逻辑的形态，使其成为一门伟大的学科。但是，当弗雷格即将宣布他的逻辑主义成功的时候，罗素于1902 年写信给他：“只有一点我遇到些困难……”，而正是这一点困难，引发了关于数学基础的一场巨大的争论。

说到这里，需要涉及一点数学史，尤其是19 世纪末、20 世纪初数学基础方面的争论。从古到今，数学大致是沿着从具体到抽象、从含混到准确、从庞杂到精纯的方向发展。以微积分为例，在古希腊时代，阿基米德已经有了近似于现代定积分的概念。

到了17世纪，牛顿和莱布尼兹独立发明了微积分。但用现代数学的标准来衡量，当时的微积分领域里有很多概念是不精确的。例如，莱布尼兹用无穷小量来表述导数，而无穷小量有如下性质：它可以参与所有的算术运算，小于所有的正实数但又不是零。无穷小这一概念当时即受到很多批评，其后200 多年也一直不被人接受。尽管如此，牛顿和莱布尼兹的直观完全与物理世界吻合，微积分理论也获得了巨大成功。

直到19 世纪，柯西和魏尔斯特拉斯引入了数学分析中的ε-δ 方法，才给微积分奠定了坚实的基础。首先，微积分中最根本的概念“微分”和“积分”都可以用极限来定义，而极限的概念又可以通过ε-δ 方法建立在实数理论的基础上。之后数学家又用有理数定义实数、用整数定义有理数、用自然数定义整数。在康托尔创立集合论之后，人们又用集合作为最根本的概念来定义自然数。

因此，人们自然会想：也许集合论和逻辑就是莱布尼兹当年梦想的通用语言？也许整个数学（乃至整个科学，甚至人类全部精神活动）都可以归约到逻辑？这就是逻辑主义的历史背景。

让我们回到困扰罗素的那一点。罗素在弗雷格的逻辑体系中找到了一个矛盾，后来被称为“罗素悖论”。罗素悖论的具体内容这里不提。在20 世纪初，有很多与罗素悖论类似的其他悖论。这些悖论的共同点是它们都涉及非常大的集合。这些悖论让人们怀疑人类是否越过了自己能力的极限，或者说，数学理论是不是太抽象了，抽象到人们对它的真假完全没有了直觉。

因此不少人基于哲学的考虑，想给数学概念和方法加一些人为的限制，以保证数学基础的坚实，起码避免悖论。其中比较极端的主张是以布劳威尔为代表的直觉主义。直觉主义者只承认潜无穷，对实无穷（起码对不可数的实无穷）持完全否定的态度。这样一来，数学里涉及实无穷的部分都将被抛弃，作为专门研究无穷的理论，康托尔的集合论也就失去了意义。

希尔伯特

希尔伯特是对20世纪数学发展影响最大的数学家之一。对数学的许多领域都有杰出的贡献。希尔伯特强烈反对直觉主义者对数学的限制。他的名言是：“没有人能把我们从康托尔创造的乐园中赶出去。”在20 世纪初，他提出了“希尔伯特计划”，期望一劳永逸地为数学奠定坚实的基础。纲领大致如下：

首先分离出数学中那些连直觉主义者都认为无可争议的证明手段，也就是本质上有穷的那些数学证明工具。对于直觉主义者担心的，涉及无穷的数学命题，则暂时不去考虑它们的意义，而只是将其看作按照一定规则进行的纯符号操作。或者说暂时把无穷数学的语义和语法分开，只研究语法部分。这样一来，如何保证证明系统是一致的就成为头等重要的大事。希尔伯特期望找到这样的形式系统，在其中能够证明这种形式化后的全部数学的一致性，而在证明过程中只使用本质上有穷数学的证明手段。

哥德尔

哥德尔被称为亚里士多德以来最伟大的逻辑学家。他的主要成就包括一阶逻辑的完全性定理、一阶算术的不完全性定理（这两个定理将是本课程的主要内容），以及选择公理和连续统假设与集合论公理系统的相对一致性。哥德尔的成果遍及数理逻辑的几乎所有领域，而且对很多领域来说是开创性的。

这些成果从根本上影响和推动了数理逻辑的发展，直到今天依然如此。在哥德尔所有这些惊世骇俗的成就中，不完全性定理不仅对逻辑，甚至对整个人类文明的发展都有深远的影响。我们只谈逻辑。哥德尔定理改变了逻辑发展的进程，其中一个重要的原因就是它彻底否定了（依原本设想方式的）希尔伯特计划。

假设皮亚诺公理系统PA代表经典数论的形式化系统，按照希尔伯特计划的要求，至少要能从PA 出发，只使用严格的“有穷主义”的手段来证明PA 的一致性。但是，哥德尔不完全性定理告诉我们，除非PA 是不一致的，PA 的一致性不能在PA 中得到证明，更遑论在PA 中证明全部数学的一致性了。

《数理逻辑：证明及其限度》（第二版）

郝兆宽 杨睿之 杨跃 著

复旦大学出版社