数理逻辑的大发展

1930年后，数理逻辑开始成为一门专业学科并蓬勃发展。在哥德尔的两个定理被证明后，希尔伯特的有限论程序就不起作用了。证明理论出现了新情况。主要有两个方面:通过放宽有限论的限制来证明算术中不存在矛盾；对证明进行形式化和规范化。这些主要是在20世纪30年代完成的。与此同时，哥德尔引入了递归函数，发展成为递归理论的一个新分支，并开始研究判断问题。哥德尔本人转向了公理集合论的研究，由此出现了公理集合论的黄金时代。模型理论产生于20世纪50年代。它与数学密切相关，并逐渐发挥积极作用。

1.证明论

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

为了使数学理论成为一个合适的研究对象，它必须形式化。自1928年希尔伯特和阿克曼撰写的第一版《理论逻辑大纲》出版以来，一阶谓词演算(和高阶谓词演算)在实践中应用最多。许多理论可以用一阶理论来表达，一阶理论相对简单方便，形式多样。

从基本观点来看，有两种理论是最重要的，因此也是研究最多的。这两种理论是形式钢琴算术理论和形式集合论。由于大多数代数理论都可以在这两个理论中发展，如果这两个理论的合理性得到证实，这将是向数学的可靠性迈出的一大步。“希尔伯特计划”无非是找到一个有限的证明步骤来证明算术的非矛盾性。

这里“有限”的含义是由年轻的法国数学家埃布兰德明确提出的，他认为必须满足以下条件:必须讨论的只有有限数量的确定对象和函数；这些对象和函数应该能够确定它们的真实值并产生一致的计算结果。如果一个对象没有指明如何构造它，它就不能确定它的存在。绝不能考虑无限集合中所有对象的集合。一个定理适用于一组对象，这意味着对于每一个特殊的对象，一般的论证可以重复，并且这个一般的论证只能被视为结果的特殊论证的原型。

数学理论中没有矛盾有了这个有限的和可建构的证明，任何人都可以放心。希尔伯特计划提出后，几组数学家分别努力实现它:一组是希尔伯特和伯尼茨，一组是阿克曼对数学理论形式化的研究，另一组是冯·诺依曼对无矛盾算术的初步研究，哥德尔的不完全性定理和甘曾的最终解。另一个小组是对Ebrand和Ganzen的标准证明形式的研究。

埃布恩是一位有天赋的年轻法国数学家，他在1931年8月攀登阿尔卑斯山时去世。他只有23岁。他在代数数论，尤其是数理逻辑方面做了重要的研究工作。1929年，他在博士论文《证明理论研究》中提出了自己的基本定理。从某种意义上说，这个定理是将谓词演算简化为命题演算。由于前一种理论是不可判定的，后一种理论是不可判定的，所以解决方案不可能是完整的。

然而，由于他对希尔伯特有限性的限制，他应用的证明方法相当复杂。此外，1963年发现他的证据有漏洞，他的错误很快就被弥补了。Ebrand定理可以帮助我们摆脱证明中的三段论。他的许多结果后来都是由甘曾独立获得的。

甘曾的自然演绎系统是数学证明形式化的结果。他由此提出了所谓的“主要定理”，即任何纯粹逻辑的证明都可以表述为形式形式，尽管形式形式不一定是唯一的。为了证明这个主要定理，他引入了所谓的Sequenz微积分。

在常见的数学证明中，三段论是最常用的，也就是说，如果A→B，如果A成立，B成立。事实上，这是甘曾推论图中的“中断”。但是，甘曾的主要定理是，所有“断裂”都可以从任何证明图中消除。也就是说，如果在证明中使用三段论，则定理表明它也可以变成没有三段论的证明，并且可以得到相同的结论。

乍一看，这个定理似乎不可理解。事实上，正如甘曾所说，证明图中的三段论实际上是“拐弯抹角”，而不是用三段论来走直线。这个没有三段论的证明图叫做“范式”，没有三段论的证明图叫做“范式”。利用这个主要定理很容易得到许多重要的结果，其中之一就是非常简单地证明“一阶谓词演算是不矛盾的”，并且可以推导出许多不矛盾的结果。后来，它还可以用来证明哥德尔的完全性和不完全性定理。当然，最重要的是证明算术中没有矛盾。

希尔伯特引入证明理论的目的是证明整个数学的非矛盾性，其中最重要的是集合论的非矛盾性(至少是ZF系统)，数学分析的非矛盾性，当然最基本的是算术的非矛盾性。哥德尔的不完全性定理表明，这一目标不能用有限的方法实现。由于哥德尔不完全定理的影响，希尔伯特的计划需要修改。

如果有限性不可行，就必须采取非有限的超差步骤。1935年，甘岑用超差归纳法证明了自然数的算术形式系统不存在矛盾。在接下来的几年里，他和其他人给出了其他证据。这个宽松的希尔伯特计划在第二次世界大战后发展成为证明理论的一个分支，这些证明也被扩展到类型理论和其他理论的分支。

甘曾在第二次世界大战接近尾声时去世。他的结果代表了当时证明理论的最高成就。希尔伯特和贝纳斯在《数学基础》第二卷中总结了他的工作，但证明理论远未实现其最初的目标。战后，随着模型理论和公理集合论在递归理论中的发展，甚至自20世纪60年代以来，证明理论都没有取得多大进展。

在20世纪50年代中期，日本数学家Takeshi等人开始探索实数理论(或数学分析)的非矛盾性。因为实数从一开始就与无限有理数集相关，所以用一阶谓词演算来描述它是不够的。因此，第一步是将Ganzen的工作扩展到高阶谓词演算。

1967年，日本青年数学家高用非结构方法证明了三段论可以从纯类型理论中剔除。因此，可以推导出数学分析子系统的非矛盾性。然而，由于证明还没有建立，数学分析的矛盾仍然需要解决。

虽然Ebrand和Ganzen的结果不能实现希尔伯特计划的最初目标，但由于其有限性和可构造性，它们已被广泛应用于机械证明，并成为该学科的理论基础。

证明理论的方法极大地促进了数理逻辑本身，尤其是新的不可判定命题。最近，年轻的英国数学家巴黎和其他人有了一个惊人的发现。他们在皮亚诺的算术中发现了一个既不能证明也不能证明的纯组合问题，这不仅给出了哥德尔不完全性定理的一个具体例子，而且使人们怀疑解决数论中许多未解决的问题可能是徒劳的。这无疑为证明理论开辟了一个全新的方向。

2.递归理论

递归理论讨论了用形式描述一个操作或过程的“可行性”的直观概念，也就是说，原则上，它们可以被机械地执行以产生一个确定的结果。“能做”的概念包含具体的、有效的、有效的等等。1898年，法国数学家波德莱尔在他的功能理论教科书中首次引入了这个词。他把数学的对象限制在可以完成的对象上。这个命题实际上是“法国经验主义”。因为函数论主要讨论集合、函数、积分等，所以描述集合论、拜耳函数等概念就是从这个角度产生的。

递归理论中讨论的函数相对简单。它讨论了有效的可计算函数，即递归函数。递归函数在历史上曾从不同的角度提出过，后来被证明是等价的。

1931年秋天，丘奇在普林斯顿举办了一个逻辑课，克莱恩和拉塞尔作为学生做笔记。丘奇在他的讲座中介绍了他的系统，并在其中定义了自然数。这自然提出了如何在丘奇系统中发展自然数理论的问题。于是克林开始了他的研究，结果克林和丘奇得到了一类可计算函数，他们称之为可定义函数。

1934年春天，歌德在普林斯顿做了一系列演讲(克莱恩和拉塞尔做了笔记)。在他的演讲中，哥德尔介绍了另一组可以精确定义的可计算函数类，他称之为一般递归函数。据他说，他的灵感来自欧文·布朗。

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

同样在1936年，年轻的英国数学家图灵发表了另一篇重要文章，它标志着所谓图灵机的诞生。在本文中，图灵还定义了一类可计算的函数，即可以由图灵机计算的函数。同时，他还提出了自己的一个论点:“可以计算的函数”和“可以由图灵机计算的函数”是一回事。1937年，图灵证明了图灵机可以计算的函数类与可定义的函数类是一致的，而可定义的函数类与一般的递归函数类是一致的。这样，丘奇的论点与图灵的相同。当时，许多人怀疑丘奇的论点。由于图灵的思想表达得如此清晰，许多人的疑虑都被驱散了。哥德尔是其中之一。从那以后，每个人都普遍支持丘奇-图灵的论点。

与图灵同时，美国数学家波斯特也发表了一篇与图灵的可计算函数相似的文章。他的文章太短了。直到1943年，波斯特才发表了第四种表达方式。结果证明他和其他人的是一样的。

递归的概念不难理解。这意味着以前的结果可以递归地用于获得以后的结果。Godel等人引入了一个通用的递归函数，递归函数可以从原始的递归函数中计算出来。

另一个更复杂的概念叫做递归集S，它的定义是有一个可行的方法来判断任何正整数N是否属于S。正计数集是递归的，当且仅当它和它在N中的补集是递归可枚举的。任何无限递归可枚举集都包含无限递归集。然而，有一个正整数的递归可枚举集，而不是递归集。

Post然后询问是否有两个递归但非递归的集合，这样第一个集合相对于第二个是递归的，但是第二个相对于第一个不是递归的。直到12年后的1956年，苏联的木奇尼克和美国的弗里德伯格才独立而明确地解决了这个问题。

1947年，苏联数学家马尔科夫发表了《算法理论》，首次明确提出了算法的概念。然而，它相当于以前定义的递归函数和可计算函数的计算过程。从表面上看，这些定义非常不同，逻辑起点也非常不同，但它们都被证明是等价的。这似乎不是巧合。它表明所有这些定义都是同一个概念，这个概念是自然的、基本的和有用的。这是“算法”概念的精确数学定义。在每个人都接受了这个定义之后，判断问题从我们通常的直观概念上升到了精确的数学概念，判断问题成为了数理逻辑的一个重要分支。从那以后，判断问题发展很快。

在用精确的数学表达式来判断问题之后，它立即对数学基础甚至整个数学产生了巨大的影响。因为在这个时候，一些不可判定命题的出现标志着数学史上第一次人们意识到有些问题不能用算法来解决。过去，人们总是模糊地认为，任何精确表达的数学问题总是可以通过有限的步骤来判断它是对还是错，是否有解。再次发现不可判定的问题表明有限过程可以处理无限的限制。它从另一个角度反映了数学的内在矛盾。

你是怎么得到这些结果的？丘奇的论点发表后，不难看出可计算函数的存在，即非一般递归函数。因为所有可能的不同算法都是可数的和无限的(简而言之，算法用有限的字数来描述)，但是所有算术函数的集合都是不可数的。

然而，1936年，丘奇获得了第一个明显不确定的结果。他首先得到了与λ可定义性相关的不可判定结果。然后，他将这个结果应用于形式系统的判断，特别是他证明了形式一阶数论n是不可判定的。同样在1936年，丘奇证明了纯谓词演算也是不可判定的。当时，每个人的反应都是:这种不完全性的范围有多广？

甚至像丘奇这样的数学家也想找到摆脱哥德尔结果的方法。例如，可以使用与哥德尔系统完全不同的其他特殊系统。一旦算法的精确定义和丘奇的论点出现，每个人都意识到他们无法躲避哥德尔不完全性定理的影响，可计算性和不完全性这两个概念是紧密联系在一起的。

事实上，富兰克林在1936年证明(作为丘奇论证的应用)，哥德尔定理即使在能够识别公理和证明的形式系统中仍然有效。消除量词的方法并不适用于许多理论。一般的判断问题是试图找到一个可行的步骤，通过这个步骤人们可以决定什么具有特定的元数学特征。

在纯逻辑演算的元理论中，有一种最明显的判断问题:对于给定的演算和给定类的公式，找到一个步骤就可以判断这种特殊公式是否可以在有限的步骤中被正式推导出来。在某些情况下，问题已经明确解决；在其他情况下，答案是否定的，这可以证明这样一个步骤不存在。这种否定的证明，特别是对于数学理论，在很大程度上依赖于递归理论。

希尔伯特第十题是第一个明确提出的数学判断问题。他在1900年的国际数学家大会上提出了23个著名的问题，其中的第十个问题是给出一个含有任意个未知数和有理数的系数的丢番图方程，并设计一个步骤，通过有限步运算来确定该方程是否有有理数的整数解。这个直到1970年才被解决的问题，不仅解决了一个重大问题，而且在解决问题的过程中所获得的工具和结果也对数理逻辑和数学的发展产生了巨大的影响。例如，表示素数的多项式，特别是与整个数理逻辑有关的多项式，得到了更精确的哥德尔不完全性定理。

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

施拉姆在1938年证明了任何丢番图方程的次数都可以简化为小于或等于4的方程。1974年，马蒂亚·舍甫琴科和罗宾逊证明了未定元素的数量可以减少到小于或等于3。对于齐次方程，Adler在1971年证明了任何齐次方程都可以简化为二次齐次方程，从而等价于一个四次齐次方程。长期以来，一直有一种求解丢番图方程的具体方法。西格尔还在1972年发现了一种算法，适用于任何含有许多待定元素的二次方程。四次方程无法确定，三次方程仍然未知。

解决判定丢番图方程解是否存在的方法是引入丢番图集。我们把丢番图方程的论点分成两组解。每个丢番图集都是一个递归可枚举集。1970年，苏联大学生马蒂亚·舍甫琴科证明了每一个递归可枚举集也是一个丢番图集。因此，由于不确定递归可枚举集的存在，存在一些特殊的丢番图方程，使得确定是否有解是不可解的。当然，一般丢番图方程的判断更不可解。

另一个判断问题是半群和群论中的词问题。半解问题最早是由挪威数学家Tue在1907年提出的。问题是在给定有限多个生成元和有限多个关系的情况下，半群是否能找到一种方法来确定某个特定的词是否等于单位元。1947年，波斯特以消极的方式解决了这个问题。

群论中的人物问题更为重要。德韦恩在1911年首次研究了这个问题，直到1955年才被苏联数学家诺维科夫解决。这些结果向数学家们展示了一个新的方向:不要试图解决一大类问题。然而，对于较窄的对象类，如特殊的组类，组的词问题是可解的。