第三次数学危机(7)

于是波斯特提出问题：是否存在两个递归可按举但是非递归的集合，使得第一个集合相对于第二个是递归的，但第二个相对于第一个却不是递归的。一直到十二年后的1956年，苏联人穆其尼克及美国人弗里德伯格才独立地肯定地解决了这个问题。

苏联数学家马尔科夫在1947年发表《算法论》，首先明确提出算法的概念。但是它同以前定义的递归函数及可计算函数的计算过程都是等价的。这几个定义表面上很不相同，并有着十分不同的逻辑出发点，却全都证明是等价的。这件事看来决非巧合。它表明：所有这些定义都是同一个概念，而且这个概念是自然的、基本的、有用的。这就是“算法”概念的精确的数学定义。大家都接受了这个定义之后，判定问题从我们平时直观的概念也上升为精确的数学概念，判定问题也成为一门数理逻辑的重要分支了。从这时起，判定问题有突飞猛进的发展。

判定问题有了精确的数学表述之后，立即在数学基础乃至整个数学中产生了巨大的影响。因为这时一些不可判定命题的出现，标志着人们在数学历史上第一次认识到：有一些问题是不可能找到算法解的。在过去，人们一直模模糊糊地觉得，任何一个精确表述的数学问题总可以通过有限步骤来判定它是对还是错，是有解还是没有解。找到不可判定问题再一次说明用有限过程对付无穷的局限性，它从另外一个角度反映了数学的内在固有矛盾。 怎样得到这些结果的呢？丘奇的论点发表之后，不难看出存在不可计算的函数，也就是非一般递归的函数。因为所有可能不同的算法共有可数无穷多(粗浅来讲，算法都是用有限多个字来描述的)，可是所有数论函数的集合却是不可数的。

不过，头一个明显的不可判定的结果是1936年丘奇得到的。他首先得到与λ可定义性有关的不可判定结果。然后，他把这个结果应用到形式系统的判定问题上，特别他证明，形式化的一阶数论N是不可判定的。也是在1936年，丘奇证明纯粹的谓词演算也是不可判定的。当时大家的反应是：这种不完全性的范围到底有多广？

甚至于象丘奇这样的数学家，也想找到一条出路能避开哥德尔的结果。比如说，可以采用伺哥德尔所用的系统完全不同的其他的特殊系统。一旦算法的精确定义和丘奇论点出现之后，大家就认识到躲不过哥德尔不完全性定理的影响，可计算性和不完全性这两个概念是紧密联系在一起的。

实际上克林在1936年就证明了(作为丘奇论点的应用)：甚至在能够能行地认出公理和证明的形式系统中，哥德尔的定理仍然成立。消去量词方法对许多理论行不通。一般的判定问题是试图找出一个能行的步骤，通过这个步骤可以决定什么东西具有某种指定的元数学特征。

在纯粹逻辑演算的元理论中，有最明显的一类判定问题：对于给定的演算和给定类的公式，求出一个步骤，能够在有限多步内判定这类的任何特殊公式是否可以形式地推导出来。有些情形、问题已经得到肯定的解决，在另外一些情形，答案是否定的，可以证明不存在这样一个步骤。这种否定的证明，特别对于数学理论，很大程度上依赖于递归论。

最早明确提出的数学判定问题是希尔伯特第十问题。他在1900年国际数学家大会上提出了著名的二十三个问题，其中第十个问题是：给定一个有任意多未知数的、系数为有理整

31

数的丢番图方程，设计一个步骤，通过它可以经有限步运算判定该方程是否有有理整数解。这个到1970年才被否定解决的问题不仅解决了一个重大问题，而且解决问题过程中所得到的工具和结果对数理逻辑和数学发展有着极大影响，比如表示素数的多项式，尤其与整个数理逻辑有关的是得出了一个更确切的哥德尔不完全性定理。

现在我们来看希尔伯特第十问题，为了清楚起见，我们考虑多项式方程，看看一般的多项式丢番图方程的次数和未定元的数目是否可以降低。

1938年斯科兰姆证明，任何丢番图方程的次数可约化成次数小于等于4的方程；1974年马蒂亚谢维奇和罗滨逊证明未定元的数目可约化成小于等于3。对于齐次方程，阿德勒在1971年证明，任何齐次方程可以能行地约化为二次齐次方程组，从而等价于一个四次齐次方程。对于一次方程早就有具体方法解丢番图方程了。对于任意多未定元的二次方程，1972年西格尔也找到一个算法。四次方程不能判定，三次方程尚不知道。

解决丢番图方程解是否存在的判定问题的方法是引进丢番图集。我们把丢番图方程的变元分成两有一组解。每个丢番图集合是递归可枚举集。1970年，苏联大学生马蒂亚谢维奇证明了每个递归可枚举集也是丢番图集合。这样一来，由于存在不可判定的递归可枚举集，所以存在一些特殊的丢番图方程，使得对是否有解的判定问题不可解。当然对一般丢番图方程的判定问题就更不可解了。

另一个判定问题是半群和群论中字的问题，半解问题是挪威数学家图埃在1907年首先提出来的。问题是对于一个半群，如果给定它的有限多生成元和有限多关系，那么能否找到一个方法来判定任何一个特殊的字是否等于单位元素。1947年，波斯特否定地解决了这个问题。

群论中字的问题更为重要，它是在1911年由德恩首先研究的，一直到1955年才由苏联数学家诺维科夫否定解决。这些结果给数学家指明了新的方向：不要妄图去解决一大类问题。不过对于更窄的一类的对象比如一类特殊的群，群的字问题是可解的。

3、模型论

模型论是数理逻辑的一个分支，讨论形式语言与其解释或者模型之间的关系。如语言是一阶谓词逻辑，则这种模型论就称为“古典模型论”。最简单的模型是数学中的一些结构，例如 5阶循环群，有理数域，以及所有按照包含关系历形成的偏序结构由整数构成的集合等等。在数学里我们直接研究这类模型，而不管形式语言。这个理论可以说是泛代数(当然也包含通常代数中的群论、环论、域论等等)，它们研究同态、同构、子结构、直积等等。可是关于这些模型的性质，都要表示成为语言。反过来，一个语句可以真也可以假，看你是说哪一个模型。

这样看来，模型论和代数学是有区别的，有人把模型论看成是逻辑加上泛代数，这也是十分形象的。模型论一定要明显地涉及语句，并且以语句为出发点，这是它同一般代数学有区别的地方。另外模型论的语言是形式语言，它与模型的关系是语法和语义的关系。对于形

32

式语言，我们只是按照一定的规则(文法规则)去造出一些语句，至于这些语句含义如何、是真是假，就不是语法所能管得了的。

语法只考虑形式的结构，比如构成语句的符号是哪些，符号之间的关系如何(谁在谁的前面而不能在后面)等等，而语义则提供解释或者意义，只有意义才能确认语句的真假(除了重言式或恒真语句或同语反复之外)。因此可以说，模型论是研究形式语言的语法和语义之间关系的学科。

在数学中，我们对模型还不是很陌生，在非欧几何中就是靠引进模型才论证了非欧几何公理系统是不矛盾的。但一直到195年左右，模型论才正式成为一门新学科。主要标志就是1949年亨肯发表的完全性定理的新证明，以及1950年国际数学家大会上塔尔斯基与罗滨逊的的报告，以及1951年罗滨逊《代数的元数学》的发表。

自此之后，模型论大致可分为两条路线，一条是美国西海岸的斯科兰姆一塔尔斯基路线，他们从四十年代起就由数论、分析、集合论的问题所推动，强调研究一阶逻辑所有公式的集合模型。另一条是美国东海岸的罗滨逊路线，他们的问题由抽象代表的问题所推动，它强调无量词公式集与存在公式集。关于两块量词的理论很多，它们有许多应用。罗滨逊主要用于域论，前苏联马力茨夫等人主要用于群论。

属于纯粹模型论主题的最早的定理有两个，一个是罗文汉姆的定理。他在1915年证明每一组有限多公理如果有模型的话，则它也有一个可数模型。把这个定理推广到有可数个公理的情况。另一个定理是紧性定理。

三十年代，哥德尔对可数语言证明紧性定理，1936年苏联马力茨夫推广到不可数语言。紧性定理在代数学方面有许多应用。

这两个定理都肯定某种模型的存在性，特别是罗文汉姆—斯科兰姆定理及紧性定理指出有想不到的特别大的模型存在。最明显的就是自然数集合的皮亚诺公理(其中归纳公理加以改变)，不仅有通常自然集N为其标准模型(即包括可数多个元素)，还有包括不可数多个元素的模型，这就是所谓非标准算术模型。第一个非标准算术模型是由斯科兰姆在1934年首先造出的。这两个定理的证明都依赖于造模型的方法。

模型论中常用的构造模型方法与工具有：初等链方法、图式、紧性定理、下行罗文海姆—斯科兰姆定理、省略类型定理、力迫法、超积、齐性集合等8种，这些方法都是相当专门的。

图式方法是亨金及罗滨逊首创的，它有许多用处，不仅能证明紧性定理、罗文海姆—斯科兰姆定理、哥德尔完全性定理等等，而且可以得出许多新定理。

初等链是塔尔斯基及沃特在1957年提出的。超积是最常用的构造模型的方法，超积和超幂的用处表现在同构定理上。超幂的另一个很大的用处是构造非标准分析的模型。 对于数学理论最重要的事是公理化。在模型论中，公理数目可以有限多，称为有限可公理化的理论。这类理论有；群、交换群、环、整域、域、有序域、全序集、格、布尔代数、贝纳斯—哥德尔集合论等等。许多重要理论是不能有限公理化的，其中一部分是递归可公理

33

化的。如可分群、无挠群、特征0的域、代数封闭域、实封闭域、有限域、尤其重要的是皮亚诺算术和ZF集合论，而有限群论甚至连递归可公理化都不行。

一个理论是递归可公理化的充分必要条件是：它的所有推论集合是递归可枚举的。通常它不一定是递归的，如果是递归的，则称为可判定的。可以证明，每个完全、递归可公理化理论是可判定的。因此利用模型论的有力工具可以得出判定理论的一些结果，如早在1948年塔尔斯基等人证明，实闭域理论是完全的，因此是可判定的。

早在十九世纪，数学家利用造模型的方法来肯定非欧几何的真实性，他们造过许多模型，但这些模型本质上没有区别，也就是“同构”。在二十世纪初，数学家一般认为，一个理论的模型都是同构的，如自然数理论就是皮亚诺公理所刻划的一种。

但是这种想法很快就由于自然数非标准模型的存在而被打破，所以人们又在模型论当中引进重要的概念—范畴性：一个理论或一组公式如果其所有模型均同构，它就称为范畴的。实际上，这对于形式系统(或公理系统)是仅次于协调性(无矛盾性)、完全性、独立性之后的第四个重要要求。但是这个要求实在太强了，实际上，只要一个理论有一个无穷模型，那么它就不是范畴的，所以我们把范畴性的要求降低。

模型论给数学带来许多新结果，我们大致可以分成三大部分：在代数方面的应用主要是在群论和域论方面；在分析方面的应用主要是非标准分析；在拓朴学、代数几何学方面的应用主要是拓扑斯理论。

模型论在代数学中最早的应用是量词的消去，早在三十年代，就由此得到了整数加法群的判定步骤，塔尔斯基得到实数的可定义集和实数域的判定步骤。

1965年以后，数理逻辑的发展逐步影响到数学本身，因而重新引起数学家们的注意，特别是集合论与模型论的结果不断冲击数学本身。模型论在解决代数问题方面显示巨大威力，特别是艾柯斯及柯辰解决了著名的阿廷猜想，这个问题曾使代数学家为难了几十年。 非标准分析是罗滨逊在1960年创造的。1961年1月，在美国数学大会上，罗滨逊宣布了他的非标准分析，其实这就是逻辑学家所谓的实数的非标准模型。在这篇报告中，他总结了新方法的所有重要方面，因此无可争辩地成为这个新领域的独一无二的创造者。他指出，实数系统是全序域，具有阿基米德性质，也就是任何一个正实数经过有限次自己加自己之后可以超过任何一个实数。但是非标准实数一般并不满足这个条件，比如说一个无穷小量的一千倍，一万倍、一亿倍甚至更多，也大不过 1，这个性质称为非阿基米德性质。

最近，非标准分析在分析、微分几何学、代数几何学、拓扑学有一系列的应用，使数学家对非标准分析也不得不另眼相看了，特别是非标准拓扑和非标推测度论近来更是有重要的突破。

非标难测度论已经得出许多新的“标准”结果，如关于测度的扩张、位势理论、布朗运动理论、随机微分方程、最优控制理论，甚至运用到数理经济学及高分子物理化学当中。其中关键来自1975年洛布的工作。他从非标准测度空间能造出丰富的标准测度空间，使得非标准分析真正能对标准数学作出自己的贡献。

34

拓扑斯是统—现代数学的最新基础，它反映了数理逻辑与范演论的结合。范畴论大约在六十年代初由同调代数学脱胎而出，而同调代数则在四十年代末到六十年代初由代数拓扑学发展而来。代数拓扑学则是用群、环、域、模等代数结构来刻化几何图形的拓扑结构。同调代数学则用代数结构来刻化代数结构，比如说一组群与另一组的对应关系。把这个组发展到集合或其它任何结构，研究范踌与范踌之间的关系就是范畴论。

我们可以考虑几何的范踌和范踌的范踌。1963年出现了层的范畴，这就是拓扑斯。托普斯使范畴方法迅速推广到其他数学分支中去。1970年，劳威尔等人引进一种特殊的范畴—初等拓扑斯。几年之后，证明了一个重要结果，一个初等拓扑斯正好是高阶直觉主义集合论的模型。因此，初等拓扑斯就象集合一样成为数学的基础，而且更接近数学的内容。

4、公理集合论

1930年以后，迎来了公理集合论的黄金时代。对于数学家们来说，策梅罗的公理系统ZF大致够用。他们仍不太关心集合论的细微未节，以及一层一层的无穷大，这些在他们的数学中难得碰到。不过除了九条可靠的ZF公理之外，他们也往往需要选择公理(AC)，有时也要考虑连续统假设(CH)。他们希望这两个公理是真的，这样似乎就可以天下太平了。谁知事情越来越麻烦，现在居然找出一大堆玄妙的公理和假设，它们能推出一些我们想要的结果来，同时又出现许多荒唐矛盾的现象。这些现象十分有趣，但是从外行看来实在乱七八糟。这里还是简单归纳介绍一下:

4.1 选择公理

选择公理是现代数学中最常用的假设，过去许多人曾不自觉地使用。对这个问题引起注意，是因为康托尔在1883年提出任意集合是否都可良序化的问题。希尔伯特也曾把这个问题引入其23问题头一问题的后半部分。1904年，策梅罗提出选择公理，并通过选择公理证明了良序定理。这个公理有极多的等价形式，其中有在代数中常用的造恩引理。这个应用极广、看来正确的选择公理，却可以证明出一些看来荒唐的结果。如1914年的豪斯道夫的分球面定理和U23年的巴拿赫—塔尔斯基悖论。

可是选择公理的用途太大，不能忽视，许多学科的基本定理少不了它：泛函分析中的哈恩—巴拿赫定理(关于巴拿赫空间上的线性泛函的可扩张性)；拓扑学的吉洪诺夫定理(关于任意多紧空间的直积为紧)；布尔代数的斯通表示定理，每个布尔代数皆同构于集代数；自由群论的尼尔森定理，自由群的子群也是自由的。 其他还有许多定理，如果没有选择公理也不行。

4.2连续统假设

连续统假设的历史最久，它可以说是随着集合论一起产生的。1883年康托尔就提出了这个假设，可数无穷集的基数的后面就是连续统的基。康托尔花了毕生精力去证明，但没有

35

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第三次数学危机(7)在线全文阅读。