数理逻辑-余俊伟（三）

5.1.3 希尔伯特纲领

希尔伯特认为应对数学基础危机就要证明数学一致性，即数学形式主义，目标是把各门数学形式化，建立相应的形式系统，证明一致性。他认为有三种数学理论：直观数学（算术、几何）、形式数学、元数学（证明论，研究一致性）。

在希尔伯特的学生伯内斯等人的帮助下提出希尔伯特纲领，主要主张：形式化、完全性、一致性、保守性、可判定性。

形式化指所有数学命题都能被严谨数学语言重述并按规则演算（有些概念如素数等，在原始的一阶语言中可能没有定义，但是要求能够定义，这样才可形式化）。

完全性指真数学命题都可被形式化证明。

一致性指可以形式证明且必须是有穷对象的有穷证明。

保守性指与真对象相关的命题证明可以借助理念对象，但要求消解掉，即可以不依赖理念对象证明命题（真实对象和理念对象：这里结合希尔伯特关于“无穷”的讨论进行说明。希尔伯特认为无穷分潜无穷和实无穷。希尔伯特说实无穷的论述运用的是一种虚拟语气。希尔伯特不假定实无穷，但是接受潜无穷，在他看来康托创造的无穷序数就是潜无穷，现实世界没有无穷，无穷是一种超乎经验之外的理念概念。作为无穷的一种，潜无穷虽然被接受，但是必须能够归约到有穷上来。有穷证明中“有穷”的涵义有三个：一是公式序列的长度必须是有穷的，二是公式序列中的公式必须是有穷命题，三是其中涉及的方法必须是有穷方法）。

可判定性指存在一种算法使得任给数学命题该算法都能判定它是不是可证的。

在希尔伯特看来，复杂系统的一致性，比如分析（Analysis），可以用更简单的系统证明，最终把所有数学的一致性归约到皮亚诺算术。哥德尔曾想按希尔伯特的指引，给出皮亚诺算术PA的一致性证明，并进一步给出分析的一致性证明，但得出了相悖的结果：哥德尔第一不完全性定理、哥德尔第二不完全性定理。

5.2 图灵可计算性

可计算性理论，又称递归论、算法理论、能行性理 。起初研究领域主要为可计算函数和图灵度，现在已经扩展至一般可计算性和可定义性，是数理逻辑、计科的独立分支。

5.2.1 三个基本概念：可计算性、算法概念、能行过程

计算来自原始人计数。后来对可计算性的等价的描述：(1) 哥德尔、埃尔布朗和克林尼根据方程演算定义的一般递归函数；(2) 丘奇通过 λ-演算定义的 λ-可定义函数；(3) 哥德尔和克林尼定义的部分递归函数；(4) 图灵基于图灵机的图灵可计算函数。(5) 波斯特基于典范演绎系统定义的函数；(6)马尔科夫基于基本字符集算法定义的可计算函数；(7) 谢佛德森和斯特吉斯基于无界存贮机（URM理想计算机）定义的可计算函数。这些理论促进了计 算工具的发展，电子计算机、DNA 计算机和量子计算机相继出现和应用。可计算性理论的基本概念、思想和方法已被广泛应用于计算机科学的各个领 域，如数据结构、计算机体系结构、算法设计与分析、编译方法与技术、程序设计语言 与语义分析等。

算法是术如《九章算术》，或者花剌子密algorithm表示算法。孙发特点：有输入输出、明确性、能行性、有穷性。明确性：关于算法的具体描述，每一步都必须清楚明白且没有歧义，从而保证算法能正确执行。 能行性：也称有效性或可行性。算法的每一步都必须能够通过有穷次的基本运算执行。有穷性：算法的执行过程必须在有穷步内终止，通常选择伪代码、流程图、控制表、程序设计语言等来描述算法。不满足有穷性的不叫算法而叫计算过程，例如计算机的操作系统就是一个计算过程，只有等待状态而不是停止状态。

能行过程：在数理逻辑和计算机科学中，算法也是一个能行过程或能行方法，即能解决某问题。能行过 程的特点与算法基本是一样的，区别在于：前者稍显粗略，因为它允许用自然语言描述， 不过可读性却比较强；后者十分严格，是用选择伪代码、流程图、控制表、程序设计语 言等进行描述的，不允许使用自然语言描述，不过可读性不是很强。因此，算法一定是 能行过程，而能行过程不一定是算法，但能行过程却一定可以通过语言的转换变成算法。

5.2.2 图灵可计算性

此节先说了图灵机如何运算，然后用图灵机描述可计算性。涉及部分函数的概念。

不同书不同图灵机，但等价。

5.2.3 部分递归函数

除了图灵机，可计算性有另一种精确描述：哥德尔–克林尼式的数学描述。它 可以从最简单的、直观的可计算函数逐步地生成（全部的）直观的可计算函数利于人们把握具体的直观可计算函数。最终，我们还会说明所有的部分递归函数都是图灵可计算的。

原始递归函数：给出0也就是零值函数，给出后继函数，给出投影函数，然后复合函数。再原始递归。原始递归函数类是包含初始函数并对复合和原始递归封闭的最小函数类。称函数 f 是原始递归的，如果它属于原始递归函数类。引入极小算子（minimalisation operator）和正则（regular）极小算子。定义递归函数和部分递归函数。递归函数类是包含初始函数并对复合、原始递归和正则极小算子封闭的最小函数类；称函数f是递归的，如果它属于递归函数类。 部分递归函数类是包含初始函数并对复合、原始递归和极小算子封闭的最小函数类； 称函数f 是部分递归的，如果它属于部分递归函数类。 递归函数类不等于图灵可计算函数类，它只是图灵可计算函数的真 类，因为下文会证明图灵可计算函数类就是部分递归函数类。

5.2.4 丘奇图灵论题

丘奇给出 λ-可定义函数这种可计算性描述的同时，还提出了丘奇论题：直观上可计算的函数类就是 λ-可定义函数类。图灵 1936 年给出图灵可计算函数这 种可计算性描述后，1937 年又证明了图灵可计算性和 λ-可定义性的等价。用图灵可计算函数对丘奇论题进行了重新表述，得到丘奇–图灵论题：直观上可计算的函数类就是图灵可计算函数类。

5.2.5 可计算枚举集

可计算集和可计算枚举集又可叫递归集和递归可枚举集。

5.3 第一不完全性

设 T 是可计算公理化的、一致的 L1-理论。作为目标，希望 T 是完全的， 即 T 等于 Th(M)。不妨进一步假设，能够用语言 L1 谈论自身基本语法和自 公理到定理的证明。一般说来，只要 L1 可以谈论自然数的性质，那么 L1 就 能通过编码的方式谈论自身语法。

罗宾森算术比皮亚诺算术要弱很多，一来定理表述可以更一般， 二来标准算术模型的真语句集与罗宾森算术的差异比其与皮亚诺算术的差异更大。

本节哥德尔第一不完全性定理的证明思路是：首先证明所有的可计算关系都是可表 示的，然后证明算术化的语法概念是可计算的，而后在此基础上证明不动点引理，从而 基于可表示的证明概念由不动点引理推出哥德尔第一不完全性定理。

5.3.1 罗宾森算术

（一阶）算术语言 L1 的图册 sigL1 = {0, S, +, × }，其中 0 是常量符号，S 是一元 函数符号，+, × 是二元函数符号。特殊地，分别称此时的 L1-项、L1-公式、L1-语句、 L1-结构、L1-模型、L1-理论为算术项、算术公式、算术语句、算术结构、算术模型、算 术理论。如无特殊说明，第 5.3 节和第 5.4 节所谈及的项、公式、语句、结构、模型、理 论默认都是算术的。另外，称基于算术语言的一阶公理系统为一阶算术公理系统。 罗宾森算术最早由塔斯基、莫斯托夫斯基1 、罗宾森2 在 1953 年提出3 。

5.3.2 可表示性

本节主要任务是证明所有的可计算关系都是可表示的。

5.3.3 算术化

首先用哥德尔编码的方式把算术语言的初始符号进行算术化。 本子节所关注的语法概念都有可以借助哥德尔编码转换为自然数的某个原始递归子 集（除证明转化为可计算子集、可证性转化为可计算枚举子集外），从而都是可表示的。

哥德尔编码的实质是在标准算术模型 N 中创建变元的镜像，比如，21 是 x0 的镜像。

5.3.4 不完全性

此节证不完全性。

5.3.5 相关推论：不可表示性、不可判定性、希尔伯特第 10 问题

丘奇于 1935 年、图灵于 1936 年分别独立地证明了一阶逻辑的不可判定性1 ，所以 如下推论也称丘奇–图灵不可判定性定理。1931 年，哥德尔没有证明2 丘奇–图灵不可判 定性定理，原因应该是如本书第 256 页所说，当时关于算法的概念还不是十分清楚。但 是后来人们发现该定理可以作为哥德尔所证明的不动点引理 5.3.77 的推论。为方便起见， 先证明 RA 的强不可判定性定理。

5.4 第二不完全性

冯·诺伊曼去信向哥德尔说明，用相同思路可以证明哥德尔第二不完全性定理。哥德尔、伯内斯和泡利同乘一条船前往美国，在旅途中和抵达普林斯顿高等研究院的几周里，哥德尔向伯内斯讲解了哥德尔第二不完全性定理的证明细节4 。 后来，伯内斯从哥德尔的证明中提取出可证性条件，然后推出了哥德尔第二不完全性定理。

哥德尔第二不完全性定理：设 T 是足够强的可计算公理化的理论。如果 T，比如皮亚诺算术，是一 致的，那么它不能证明自身一致性。

5.4.1 皮亚诺算术

由于本书所证哥德尔第二不完全性定理的最小典型实例是皮亚诺算术，所以先介绍皮亚诺算术。

5.4.2 可证性条件

可证性条件最早是由伯内斯于 1939 年从哥德尔的证明中提取出的，由于著作也署名希尔伯特，所以也称希尔伯特–伯内斯可证性条件。

3（可证性条件）. 设 φ, ψ 是公式。三个可证性条件为： D1 : 如果 `T φ, 那么 `T ✷Tφ； D2 : `T ✷T(φ → ψ) → ✷Tφ → ✷Tψ； D3 : `T ✷Tφ → ✷T✷Tφ。

5.4.3 T满足D1

本子节关注可证性条件 D1，并且证明满足一定条件的理论 T 满足 D1。 引理 5.4.19. 设 T 是包含 PA 的、可计算公理化的理论。

5.4.4 T满足D2

首先引入可证计算的概念以形式化部分函数和关系，然后形式化部分算术定理，继而形式化有穷序列的概念和有穷序列的串接运算，从而形式化原始递归和语法概念，最后利用形式化的有穷序列概念、串接运算、证明概念证明 T 满足 D2。

5.4.5 T满足D3

该节引入了新符号释放了自由变元。

5.4.6 不完全性

（形式化的哥德尔第二不完全性）. 设 T 是包含 PA 的、可计算公理化的理 论。如果 T 是一致的，那么 `T Con(T) → ¬✷TCon(T)。

柯尔比–帕瑞斯定理

5.4.7 相关推论

哥德尔第一不完全性定理可被视为哥德尔第二不完全性定理的直接推论。 还研究了可证公式的不动点、典型理论等。

5.5 希尔伯特纲领所受影响

5.5.1 哥德尔不完全性定理的冲击

哥德尔第一不完全性定理冲击了希尔伯特纲领的完全性，哥德尔第二不完全性定理冲击了希尔伯特纲领的一致性。哥德尔第一不完全性定理在一定程度上间接否定了希尔伯特纲领的可判定性。

5.5.2 哥德尔之后的希尔伯特纲领

虽然希尔伯特纲领受冲击但有积极影响，证明论、反推数学发展起来了。希尔伯特纲领也调整了：虽然目前还不确定是否所有的数学都能被形式化到同 一个形式系统，但目前已被广泛接受的是，大多数的数学都能被形式化到一阶公理系统 ZFC中，虽然没有一个形式系统可以证明所有真的数学命题，但一阶公理系统 ZFC 可以证明现行绝大多数数学分支的绝大多数真的数学命题，虽然PA、PA一致的理论都不可攀的但发现了一些非平凡、可判定的其他理论，对什么是有穷方法的定义也扩展了。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。