20世纪数理逻辑的概貌

《20世纪数理逻辑的概貌》由会员分享，可在线阅读，更多相关《20世纪数理逻辑的概貌（7页珍藏版）》请在金锄头文库上搜索。

1、2020 世纪数理逻辑的概貌世纪数理逻辑的概貌20 世纪数理逻辑的概貌 （李娜）分类:形式语义和数理逻辑在 20 世纪里，数理逻辑的发展极其迅速并取得了巨大的成就。例如，1937 年 图灵提出了一个非常重要的关于计算的数学模型，现在人们称它为图灵机。它 能计算一切能行可计算的问题类，是一个能行可计算的模型。还为现代通用计 算机体系设计思想的产生提供了理论准备。1931 年哥德尔证明了：一个包括初 等数论在内的形式系统，如果它是一致的，那么它就是不完全的；或者说如果 这样的系统是一致的，那么它的一致性在本系统中不可证。现在人们称这个结 论为哥德尔不完全性定理。这一定理为 20 世纪数理逻辑的发展

2、带来了新的活力。 近年来，它对人工智能的研究也产生了巨大影响。1933 年塔斯基发表的形式 语言中的真值概念一文是模型论的奠基著作，它为后来的逻辑语义学的发展 奠定了基础。这是 20 世纪 30 年代数理逻辑所取得的三项伟大成就。笔者认为： 20 世纪 30 年代数理逻辑所取得的这三项伟大成就，不仅决定了 20 世纪逻辑学 的面貌，而且也将影响着 21 世纪逻辑学的发展。本文将从历史的视角回顾 20 世纪数理逻辑的面貌并展望 21 世纪数理逻辑或者 21 世纪早期数理逻辑的发展。数理逻辑包括一阶逻辑(指命题逻辑和狭谓词逻辑，也称为经典逻辑)、高阶逻 辑、公理化集合论、递归论、模型论和证明论等。

3、这部分内容基本上是数学化 的，所以，它也是现代数学的基础。数理逻辑方面的分支相对来说比较成熟， 即便如此，20 世纪中也出现了一些新的发展。例如，在常见的经典命题逻辑系 统中，联结词和括号总是兼而有之。在这样的系统中，联结词和括号各自承担 各自的作用。实际上，它们的作用是可以互兼的。20 世纪 20 年代，卢卡西维 奇采用前置法使联结词兼负起括号的作用，并建立了不用括号的系统。我国学 者在 20 世纪 90 年代中，建立了不用联结词的命题逻辑系统，这表明括号也能 兼具联结词的作用。不久，他又推广了他的这一结果，建立了不用联结词和量 词的一阶逻辑系统，使括号发挥着更充分的作用。另外，通常在表述一

4、阶逻辑 的形式系统时，需要使用个体变项，现在有一种不使用个体变项的记法，这样 的系统不仅保留了原来系统的表达能力，还在某些方面更接近于日常推理。 7080 年代人们还给出了一种一阶逻辑的动态解释。此外，对一阶逻辑的一些 子系统也进行了研究。例如，一元谓词逻辑，全称子句，以及 Horn子句等的 研究。1在四论中，公理化集合论是用现代公理化的方法重建康托尔集合论的研究。康 托尔集合论中有一条重要的原则：把凡是满足某种性质 p(x)的对象 x 聚集起来就构成一个集合。这一原则被称为概括原则。它很自然，人们原来对它深信不 疑。1901 年，罗素用具有性质 x?x 的元素 x 构成集合推出矛盾，这个矛盾

5、就是 著名的罗素悖论。罗素悖论的出现立即震动了整个数学界，引起了数学史上的 第三次危机。为了消除罗素悖论，人们不得不对集合的概念加以限制。由于当 时希尔伯特刚为欧氏几何学成功地建立了公理系统，因此大家普遍认为采用公 理化的方法对集合作一些必要的限定是适当的。1908 年蔡梅罗提出了第一个集 合论公理系统，后经弗兰克尔等人加以改进和补充，终于形成了著名的 ZF 公理 系统。在这个系统中，不仅避免了过去已发现的悖论，而且至今未发现出现新 的悖论。特别是，保留了康托尔集合论。另外，还有罗素建立的类型论，冯?诺 伊曼、贝奈斯和哥德尔等人建立的 GB 公理系统。由于 ZF 系统是一个形式公理 系统，它建

6、立在带等词“=”和属于关系“?”的一阶谓词演算上，它的非逻辑 公理有：外延公理、空集公理、配对公理、并集公理、幂集公理、子集公理、 无穷公理、替换公理、正则公理。如果加上选择公理(AC)，得到的系统记作 ZFC。在 ZFC 公理系统中，子集公理是一种受到限制的概括原则。用这条公理只 能得到与已构造的集合相比并不大的集合。这样就有效地阻止了悖论的产生， 并且还能够得出数学中所需要的东西。但是，在 ZFC 公理系统中仍然存在着一 些问题有待解决。例如连续统假设(CH)以及 ZFC 公理系统的协调性等等。在 ZFC 公理系统中，使用其它公理所得到的集合都可以构造性地给出，唯有选择 公理是一个例外。为

7、此在数学家中就是否承认选择公理也曾引起过激烈的争论。 此外，有些由选择公理推出的结论也与直觉不服，其中最著名的是 1924 年巴拿 赫和塔斯基证明的被称为“分球怪论”的定理。这是人们感到它(选择公理)是 一条危险的公理。另一方面，我们又很难放弃选择公理。事实上，若要放弃选 择公理就得放弃一大部分现代数学。关于选择公理的激烈争论，直到 1938 年哥 德尔建立了可构成模型 L，用内模型方法，证明了选择公理和连续统假设(CH) 相对于 ZF 是协调的才告结束。此后，哥德尔的内模型方法被广泛用于集合论的 协调性证明中。到了 70 年代，吉森等人对可构成模型 L 进行了更精确的刻画， 创立了“精细结构

8、”的理论，从而在 L 中证明了许多组合问题。后来，道德和 吉森等人将精细结构理论和超幂方法相结合，提出了柱心模型理论。虽然用内 模型方法解决了很多问题，但是选择公理和连续统假设的独立性问题仍然没有 解决。直到 60 年代，科恩用力迫法才证明了选择公理和连续统假设相对于 ZF 是独立的。力迫法是一种强有力的构造模型的方法。用它不但建构了选择公理和连续统假设在其中成立的模型，还得到了大量的独 立性结果。例如集合论中的 Souslin 假设和 Kurepa 猜想。从此，公理化集合论 的研究在 20 世纪的后 30 年里又有了长足的发展。随着集合论研究的深入，基 于各种原因，人们从两个方面来加强 ZF

9、 公理系统。一个方面：提出一批有用的 新公理或新假设，如马丁公理和决定性公理等等。决定性公理是与选择公理相 矛盾的，并且由 ZF 推不出决定性公理。但是，使用决定性公理可以得到许多重 要的结论。例如，由它可以证明每一实数集都是 Lebesgue 可测的，并且具有 Baire 性质。对决定性公理的研究不仅为 ZF 系统的研究开辟了新的领域，还给 传统的描述集合论的研究注入了新的活力。马丁公理(MA)是 1973 年马丁提出的 一条命题，它与连续统假设的关系非常有趣。一个方面连续统假设可以推出马丁公理。另一方面用马丁公理也能证明许多连续统假设不能证明的命题。用马 丁公理还能得出许多结论。如用 MA

10、2 推出的结果表明在 和 2 之间 的基数具有和基数 相似的性质。另一方面：用大基数公理强无穷公理加 强 ZF，如马洛基数、可测基数、可达基数、划分基数、不可描述基数、紧致基 数、可扩基数和巨大基数等等。几乎每一种大基数都是可数无穷基数 的某种 性质向不可数基数的推广。这之后，人们又开始关注集合论的无穷长语言的模 型及其性质的研究。例如，无穷长语言的可构成模型与其序数可定义集模型的 研究。探索这类模型中的各种集合论性质：例如，选择公理及其弱形式，连续 统假设及其强弱形式，大基数公理，决定公理以及力迫公理等等。并将这类模 型与哥德尔可构成模型，(有穷长语言的)序数可定义集模型及各种力迫模型进 行

11、比较。我国学者在近 20 年来对集合论的研究中，也取得了出色的成果。四论中，递归论也称为可计算性理论，它产生于对算法的研究。主要研究可计 算对象的计算复杂性和不可计算对象的结构，也是计算机科学的理论基础。它 的目的是研究计算和相对计算的本质。在 20 世纪 30 年代曾产生过几种等价的 刻画算法本质的精确定义，其中主要有 可定义函数，递归函数、图灵可计 算函数以及由波斯特产生系统定义的算法可产生集。随着人们寻求谓词演算系 统判定过程的失败和著名的哥德尔不完全性定理的出现，人们开始转向对不可 计算对象的研究，并找到了许多不可计算的例子。在这个基础上，1939 年图灵 引入了相对可计算的概念，从此

12、开始了相对可计算的研究。20 世纪 50 年代中 期，弗里德伯格和穆契尼克各自独立地创立了有穷损害优先方法(或称 0?方 法)，证明了“存在两个不可比较的递归可枚举的图灵度”，解决了波斯特问题。 60 年代，申菲尔德和萨克斯又各自独立地创立了无穷损害优先方法(或称 0? 方法)，证明了稠密性定理。此后若干年中，人们用无穷损害优先方法得到了一 大批关于递归可枚举的结果。70 年代，拉克朗又创立了树构造和 0?方法， 证明了拉克朗非分解定理成立。这一方法现在已被用在其它领域的研究中。在 最近 20 年中，可计算可枚举度理论的主要进展都是应用 0?方法，获得了 一些重要的结果。将 0?方法用在研究

13、n-c.e.度和02 度的结构和理论， 以及研究 c.e.，n-c.e.和02 的结构关系及局部可定义关系等问题则属于局部 度理论。到目前为止，最显著的可定义性成果是库波 1990 年、1993 年和 1994 年的可定义性定理。我国学者利用可计算枚举囿界极小定理获得了这一领域最 新的一些进展。四论中，模型论是一个新兴的学科。它是研究形式语言及其解释或者模型之间 关系的理论。也是形式语言的语法和语义关系的理论。模型论的早期工作有： “如果一个命题有无穷模型，则它有可数模型”。1915 年洛文海姆首先证明了 这一结果对可数语言的无穷命题集成立，1920 年斯柯伦把这一结果推广到可数 语言的无穷公

14、式集的情况，1931 年塔斯基把这一结果推广到不可数语言的情况。 所以，这一结果后来发展为洛文海姆斯柯伦塔斯基(简称 LST)定理。模型 论中另一项重要工作是：哥德尔的完全性定理和紧致性定理。1930 年哥德尔证 明了可数语言的情况，1936 年马尔塞证明了不可数语言的情况。1931 年和1935 年塔斯基刻画了实数可定义集，对一个命题在一个模型中为真的严格定义 进行了系统的研究。这些人对模型论的早期发展都起了重要作用。20 世纪 40 年代末和 50 年代初，由于亨金、鲁滨逊和塔斯基的工作，才使模型论成为数理 逻辑的一个分支，从 20 世纪 50 年代起，模型论才开始系统的发展。现在，模 型

15、论已经发展成为一个内容十分丰富的重要学科。它包括：一阶模型论、高阶 模型论、无穷长语言模型论、具有广义量词的模型论、模态模型论、多值模型 论。特别是，应计算机科学发展的需要，在 20 世纪 7080 年期间，模型论中 专门研究有穷模型而形成了有穷模型论。由于数理逻辑中以一阶逻辑的发展最 为成熟，模型论也以一阶模型论内容最丰富，应用也最多。另外，一阶模型论 还有两个特点：第一，模型论与数理逻辑的其它分支联系密切。首先，各种逻 辑演算都是模型论的基础。其次，模型论的方法被广泛用于证明论中有关判定 问题的研究。再次，模型论中的布尔值模型方法被用于公理化集合论中各种独 立性问题的研究。有关大基数的研究

16、也与模型论有关。反过来，公理化集合论中的力迫法也被移植于模型论中。最后，递归论中很多 重要的概念及结果也被应用于研究各种代数结构(模型)中。第二，模型论中的 概念和方法，除了主要来源于数理逻辑之外，也有不少直接来源于代数，它与 抽象代数的关系最密切。而与其它数学学科，例如，数论、拓扑学、概率论等 也有联系。反过来，它的成果也正在进入其它数学分支领域。近 20 年来，我国 学者在模型论的研究和应用方面的成果非常丰硕，他们还取得了模型论研究方 面的一些开拓性成果。四论中，证明论自 20 世纪 20 年代希尔伯特创立以来也有很大发展。20 世纪 20 年代初，希尔伯特提出了一个试图解决数学基础问题的证明论方案，此方案的 目的是：用能行的有穷方法研究包括古典逻辑和古典数学的形式系统，并论证 其协调性等。为实现这个方案，1924 年阿克曼作了一些工作并得到了一些结果。 在 20 年代最后两年里，还得到了一些重要结果，从而推动了逻辑演算的形式化 过程。在 30 年代开始的几年(193019