第三次数学危机(6)

矛盾的、完全的，如果它们能够得证，并且集合论公理系统也能得到同样的结果，那么整个数学就比较牢靠了。

为了不使一小撮直觉主义者指手划脚、评头品足，希尔伯特提出他的计划：把理论系统形式化，然后通过有限多步证明它们没有矛盾。他信心十足，在1930年9月东普鲁士哥尼斯堡的科学会会议上，他批判了不可知论。 1928年希尔伯特提出四个问题：

1、分析的无矛盾性。1924年阿克曼和1927年冯·诺依曼的工作使希尔伯特相信只要一些纯算术的初等引理即可证明。1930年夏天，哥德尔开始研究这个问题，他不理解希尔伯特为什么要直接证明分析的无矛盾性。哥德尔认为应该把困难分解：用有限主义的算术证明算术的无矛盾性，再用算术的无矛盾性证明分析的无矛盾性，哥德尔由此出发去证明算术的无矛盾性而得出不完全性定理。

2、更高级数学的无矛盾性，特别是选择公理的无矛盾性。这个问题后来被哥德尔在1938年以相对的方式解决。

3、算术及分析形式系统的完全性。这个问题在1930年秋天哥尼斯堡的会议上，哥德尔已经提出了一个否定的解决，这个问题的否定成为数理逻辑发展的转折点。 4、一阶谓词逻辑的完全性。这个问题已被哥德尔在1930年完全解决。

这样一来，哥德尔的工作把希尔伯特的方向扭转，使数理逻辑走上全新的道路。

3、1930年哥德尔的两项主要贡献

1、完全性定理：哥德尔的学位论文《逻辑函数演算的公理的完全性》解决了一阶谓词演算的完全性问题。罗素与怀德海建立了逻辑演算的公理系统的无矛盾性及完全性(也许还包括不那么重要的独立性)。所谓完全性就是，每一个真的逻辑数学命题都可以由这个公理系统导出，也就是可证明。

命题演算的完全性已由美国数学家波斯特在1921年给出证明，而一阶谓词演算的完全性—直到1929年才由哥德尔给出证明。但是哥德尔认为，斯柯仑在1922年的文章中已隐含证明了命题演算的完全性，但是他没有陈述这个结果，可能是他本人并没有意识到这一点。 2、哥德尔的不完全性定理：这是数理逻辑最重大的成就之一，是数理逻辑发展的一个里程碑和转折点。哥德尔在研究过程中直接考虑悖论及解决悖论的方法，从而把第三次数学危机引导至另外一个方向上。

哥德尔证明不完全性定理是从考虑数学分析的协调性问题开始的。1930年秋在哥尼斯堡会议上，他宣布了第一不完全性定理：一个包括初等数论的形式系统，如果是协调的，那就是不完全的。不久之后他又宣布：如果初等算术系统是协调的，则协调性在算术系统内不可证明。

哥德尔的证明使用了“算术化”的方法。哥德尔说：“一个系统的公式??从外观上看是原始符号的有穷序列??。不难严格地陈述，哪些原始符号的序列是合适公式，哪些不是；

26

类似地，从形式观点看来，证明也只不过是(具有某种确定性质的)一串公式的有穷序列”。因此，研究一个形式系统实际上就是研究可数个对象的集合。我们给每个对象配上一个数，这种把每一个对象配上一个数的方法称为“哥德尔配数法”。哥德尔通过这些数反过来看原来形式系统的性质。

哥德尔研究了46种函数和谓词，哥德尔证明了他的前45个函数和谓词都是原始递归的。但第46个谓词为“X是一个可证公式的哥德尔数”。在对哥德尔配数的系统中，可以得到一个公式，它相当于：我是不可证的。所以这个句子是不可证的且是真的。所以系统中存在真语句而又不可证，也就是系统不完全。

哥德尔的论文在1931年发表之后，立即引起逻辑学家的莫大兴趣。它开始虽然使人们感到惊异不解，不久即得到广泛承认，并且产生巨大的影响：

哥德尔的证明对希尔伯特原来的计划是一个巨大的打击，因此把整个数学形式化的打算是注定要失败的，因而逻辑主义和形式主义的原则是不能贯彻到底的；“希尔伯特计划”中证明论的有限主义观点必须修正，从而使证明论的要求稍稍放宽。1936年甘岑在容许超穷归纳的条件下证明了算术的无矛盾性，而倡导有限构造主义的直觉主义也不能解决问题；哥德尔的工具递归函数促进了递归函数论的系统研究，同时推动了不可判定问题的研究，开始出现递归论的新分支。

哥德尔不完全定理的证明结束了关于数学基础的争论不休的时期，数学基础的危机不那么突出表现出来。数理逻辑形成了一个带有强技巧性的独立学科，而绝大部分数学家仍然把自己的研究建立在朴素集合论或ZF公理集合论的基础上。

尽管集合论中存在矛盾，但这些矛盾大部分均可回避。研究这些矛盾，特别是集合论的矛盾变成数理逻辑学家的事业。另外一方面，直觉主义和构造主义数学虽然也有发展，但终究是一小部分，半个世纪以来，在数学中始终不占统治地位。因为矛盾也好、危机也好，根源在于无穷，但是数学中毕竟少不了无穷。归根结蒂，数学终究是研究无穷的科学。

第五章：数理逻辑的大发展

1930年以后，数学逻辑开始成为一个专门学科，得到了蓬勃发展。哥德尔的两个定理证明之后，希尔伯特的有限主义纲领行不通，证明论出现新的情况，主要有两方面：通过放宽有限主义的限制来证明算术无矛盾性以及把证明形式化、标准化，这些主要是在三十年代完成。同时哥德尔引进递归函数，发展成递归论的新分支，开始研究判定问题。而哥德尔本人转向公理集合论的研究，从此出现公理集合论的黄金时代。五十年代模型论应运而生，它与数学有着密切联系，并逐步产生积极的作用。 1、证明论

27

证明论又称元数学，它研究数学的最基本活动—证明的合理性问题。研究这类数学基础的问题原来一直是哲学家的事，后来才成为数学家的事。这个转变发生在1893年弗雷格发表《算术基础规则》之时，后来希尔伯特和他的许多合作者使这种思想发展成一门学科—元数学，目的是用数学方法来研究整个数学理论。

要使数学理论成为一个合适的研究对象，就必须使之形式化。自从希尔伯特和阿克曼所著《理论逻辑纲要》第一版在1928年出版以来，在实践中用得最多的是具有等式的一阶谓词演算(以及高阶谓词演算)。许多理论可以用一阶理论来表述，它比较简单方便，具有多种形式。

从基础的观点来看，有两个理论最为重要，因而研究也最多。这两个理论就是形式化的皮亚诺算术理论与形式化的集合论。因为大多数观代数学理论都可以在这两个理论范围内发展，所以这两个理论的合理性如果得到证实，也就是向数学的可靠性迈进了一大步。“希尔伯特计划”无非就是要找到一个有限的证明步骤来证明算术的无矛盾性。

这里“有限”的意义是由法国年轻数学家厄布朗明确提出的，他认为下列条件必须满足：必须只讨论确定的有限数目的对象及函数；这些对象及函数要能确定它们的真值产生协调一致的计算结果；一个对象如不指出如何构造它就不能肯定其存在；必须永远不考虑一个无穷集体中所有对象的集合；一个定理对于一组对象都成立的意思是，对于每个特殊的对象，可以重复所讲的普遍论证，而这普遍论证只能看成是结果特殊论证的原型。

数学理论的无矛盾性有了这种有限的、可构造性的论证之后，任何人都可以放心了。希尔伯特计划提出后，几组数学家分别为实现它而努力：一组是希尔伯特及贝耐斯，以及阿克曼关于把数学理论形式化的研究，一组是冯·诺依曼关于算术无矛盾性的初步研究及哥德尔的不完全性定理以及甘岑的最后解决；还有一组是厄布朗及甘岑关于证明的标准形式等的研究。

厄布朗是法国天才的青年数学家，1931年8月在登阿尔卑斯山时遇难，年仅23岁。他对代数数论尤其是数理逻辑进行过重要的研究工作，1929年他在博士论文《证明论研究》中提出他的基本定理。从某种意义上来讲，这个定理是想把谓词演算归结为命题演算。由于前一理论是不可判定的，而后一理论是可判定的，因此这种归结不可能是完全的。 但是，由于厄布朗局限于希尔伯特有限主义立场，他应用的证明方法比较绕弯子。而且在1963年发现，他的证明中有漏洞，他的错误很快就得到了弥补。厄布朗定理可以便我们在证明中摆脱三段论法。他的许多结果，后来也为甘岑独立地得出。

甘岑的自然演绎系统是把数学中的证明加以形式化的结果。他由此得出所谓“主定理”，即任何纯粹逻辑的证明，都可以表示成为某种正规形式，虽然正规形式不一定是唯一的。为了证明这个主定理，他又引进了所谓的式列(Sequenz)演算。

在普通的数学证明中，最常用则是三段论法，即如果A→B，且若A成立，则B成立。其实这就是甘岑推论图中的“断”。但是甘岑的主定理就是从任何证明图中可以消除掉所有的“断”。也就是：如果在一个证明中用到三段论法，那么定理表明，它也可以化成为不用三段论法的证明，也得到同样的结论。

28

这个定理乍一看来似乎不可理解，其实正如甘岑所说，一个证明图中有三段论法实际上是“绕了弯子”，而不用三段论法是走直路。这种没有三段论法的证明图称为“正规形式”，利用这没有三段论法的证明图称为“正规形式”。利用这个主定理很容易得出许多重要结果，其中之一就是极为简单地证明“一阶谓词演算是无矛盾的”，而且能够推出许多无矛盾性的结果。后来还可以用来证明哥德尔的完全性及不完全性定理，当然，最重要的事还是要证明算术的无矛盾性。

希尔伯特引进证明论的目标是证明整个数学的无矛盾性，其中最重要的是集合论的无矛盾性(至少ZF系统无矛盾)、数学分析的无矛盾性，最基本的当然是算术的无矛盾性。哥德尔的不完全性定理说明，用有限的办法这个目标是达不到的。由于哥德尔不完全定理的冲击，希尔伯特计划需要修改。

有限主义行不通就要用非有限的超穷步骤。1935年，甘岑用超穷归纳法证明自然数算术形式系统的无矛盾性。其后几年，他和其他人又给出了其他的证明。这种放宽了的希尔伯特计划在第二次世界大战之后发展成为证明论的分支，这些证明也推广到分支类型论及其他理论。

甘岑在第二次大战行将结束时去世，他的结果代表当时证明论的最高成就，希尔伯特和贝纳斯的《数学基础》第二卷中总结了他的工作，但是证明论远远未能完成它的最初目标。战后随着模型论和递归论乃至六十年代以来公理集合论的发展，证明论一直进展不大。 五十年代中，日本数学家竹内外史等人开始对于实数理论(或数学分析)的无矛盾性进行探索。因为实数一开始就同有理数的无穷集和有关，描述它的语言用一阶谓词演算就不够了，所以第一步就要先把甘岑的工作推广到高阶谓词演算中去。

1967年，日本年轻数学家高桥元男用非构造的方法证明，单纯类型论中也可以消去三段论法。由此可以推出数学分析子系统的无矛盾性。但是，由于证明不是构造的，数学分析的无矛盾性至今仍然有待解决。

厄布朗及甘岑的结果虽然不可能完成希尔伯特计划的最初目标，但是由于其有限性、可构造性的特点，现在已广泛地应用于机械化证明，成为这门学科的理论基础。

证明论的方法对于数理逻辑本身有很大的推动，特别是得出新的不可判定命题。最近，英国年轻数学家巴黎斯等人有了一项惊人的发现。他们发现了一个在皮亚诺算术中既不能证明也不能否证的纯粹组合问题，这不仅给哥德尔不完全性定理一个具体的实例，而且使人怀疑要解决许多至今尚未解决的数论难题可能都是白费力气。这无疑开辟了证明论一个完全新的方向。 2、递归论

递归论讨论的是从形式上刻划一个运算或一个进程的“能行”性这种直观的观念，也就是从原则上讲，它们能机械地进行而产生一个确定的结果。“能行”的这个概念含有可具体实现的、有效的、有实效的等等意思。法国数学家保莱尔首先在1898年他的函数论教科书中引进了这个词，他把数学的对象局限于能行的对象，这种主张实际上就是“法国经验主

29

义”。因为函数论主要讨论集合、函数、积分等等，从这种观点产生出描述集合论、拜尔函数等概念。

递归论中所讨论的函数是比较简单的。它讨论有效可计算的函数，也就是递归函数。递归函数在历史上曾从不同角度提出来，后来证明它们都是等价的。

1931年秋天，丘奇在普林斯顿开了一门逻辑课，克林和罗塞尔当时作为学生记了笔记。丘奇在讲课中引进了他的系统，并且在其中定义自然数。这就很自然引起一个问题，在丘奇系统中如何发展一个自然数理论。于是克林开始进行研究，结果克林和丘奇得到一类可计算的函数，他们称之为A可定义函数。

1934年春天，哥德尔在普林斯顿做了一系列讲演(克林和罗塞尔记了笔记)。在讲演中，哥德尔引进了另外一套可以精确定义的可计算函数类，他称为一般递归函数。据他讲，他是受了厄布朗的启发得到的。

这时自然出现了一个问题。一般递归函数类是否包括所有能行可计算的函数，它是否与克林与丘奇研究的 A可定义函数类重合。1934年春末，丘奇和哥德尔讨论一般递归函数问题，结果丘奇明确提出他的“论点”，所有直觉上可看成能行可计算函数都是 λ可定义函数，于是丘奇花了好几个月反复思考。当时克林表示怀疑，他认为这论点不太可能是对的，他想如果从A可定义函数类用对角化方法可以得出另外一个能行可计算函数，那么它就不是A可定义的。但他又想到这事行不通。不久之后，丘奇和克林在1936年分别发表论文，证明A可定义函数类正好就是一般递归函数类。有了这个有力的证据，丘奇于是公开发表他的“论点”。

也是在1936年，英国年轻数学家图林发表了另外一篇重要文章，这标志着所谓图林机的产生。在这篇文章中，图林也定义了一类可计算函数，也就是用图林机可以计算的函数。同时，他也提出他的一个论点：“能行可计算的函数”与“用图林机可计算的函数”是一回事。1937年图林证明了用图林机可计算的函数类与可定义函数类是一致的，当然，也就和一般递归函数类相重合。这样一来，丘奇的论点与图林的论点就是一回事。当时许多人对于丘奇的论点表示怀疑，由于图林的思想表述得如此清楚，从而消除了许多人的疑虑，哥德尔就是其中一位。从这时起大家对于丘奇—图林论点一般都抱支持的态度了。

与图林同时，美国数学家波斯特也发表了一篇文章，类似于图林的可计算函数，他的文章过于简短，一直到1943年波斯特才发表了第四个表述，结果证明他的与别人的也都一样。 递归的概念并不难理解，它就是由前面的结果可以递推得到后面的结果。哥德尔等人引进的实际上是一般递归函数，一股递归函数都可以由原始递归函数算出来。

另一个复杂一些的概念称为递归集合S，它的定义是存在一种能行的办法来判断任何正整数n是否属于S。正数数集合是递归的当且仅当它与它在N中的补集都是递归可枚举的。任何无穷递归可枚举集都包含一个无穷递归集。但是，存在正整数的递归可枚举集而不是递归集。

30

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