数理逻辑-余俊伟（二）

亨廷顿对实数系统进行了二阶公理化，研究了范畴性、范畴定理，此后成为模型论重要性质和基础定理。勒文海定理标志模型论开始。勒文海-斯库伦定理：一阶逻辑中所有可满足的可数一阶公式集都有可数模型。后来应用于集合论得到斯科伦佯谬（可推出不可数集合存在的策梅洛公理系统有可数模型）。

希尔伯特明确区分了一阶逻辑与其他逻辑。还引入高阶逻辑。伯内斯提供了严格的希尔伯特公理系统。确立一阶逻辑的主体地位。

哥德尔证明了一阶逻辑的完全性。

1930年数学基础三大主义成型：逻辑主义、直觉主义、形式主义，引导集合论与一阶逻辑结合作数学基础。集合论的形式化后来被证明都为一阶的，一阶集合论能推出大部分数学因此不必用高阶逻辑。（此书认为）高阶逻辑实质是集合论。，集合论的公理系统又是一阶的。一步步终于确立一阶对高阶的优势地位，集合论与一阶逻辑的数学基础地位。

3.2 语法

3.2.1 基本语法

自然语言的初始符号为汉字等等，人工形式语言之一阶语言的初始符号由非逻辑符号和逻辑符号组成。非逻辑符号是常量、关系、函数、元数函数符号，逻辑符号是变元、等词、联词、量词、语法逗号、语法括号。符号无意义，只有语义说明后才有意义。π为非逻辑符号。对一阶逻辑来说逻辑符号都相同，差别在于非逻辑符号。

语言的阶：公式中量词只作用于变元符号即一阶，否则为高阶。命题语言无量词，为零阶。

然后举了很多一阶语言的例子：一阶图、一阶序、一阶半群、一阶集合论、一阶群、一阶环、一阶域、一阶布尔代数、一阶算术，有些是关系语言有些是代数语言有些啥都不是。

一般一阶语言都有穷、可数。

3.2.2 无歧义性

给定初始符号后，我们生成了项和公式，类似于自然语言词和句，但没有歧义。要证明证明项和公式的无歧义性（唯一可读性），先证项的可读性和唯一可读性，再证公式可读性和唯一可读性。

3.2.3 递归定义

项和公式是递归定义来的，所以要定义关于项或公式的某个概念，也需类似地进行 递归定义，这是由（结构）递归定义定理保证的。证项的结构递归定义，再证公式的结构递归定义，再证对子项封闭的项集上的结构递归定义，再证对子公式封闭的公式集上的结构递归定义。

3.2.4 归纳证明

项和公式是递归定义来的，所以要证明关于项或公式的某个性质成立，就需要归纳证明，这是由（结构）归纳证明定理保证的。先证公式的结构归纳证明，再证对子项封闭的项集上的结构归纳证明，再证对子公式封闭的公式集上的结构归纳证明。

3.2.5 自由变元

数学两种变元：自由变元和约束变元。把它引入到一阶逻辑中。

3.3 语义

3.3.1 结构与赋值

符号需要语义说明才有意义。先赋予量词、函数等意义，即确定论域和解释，论域和解释统称结构。再赋予变元意义，即赋值。结构常见有关系结构、代数结构或者啥也不是，可以根据情况用关系图或者代数式表示。

3.3.2 塔斯基语义

引入结构和赋值完成语义说明后，对项和公式的真假进行语义规定。

基于塔斯基的理论，一个逻辑语句的真值取决于语句中的词语在给定的模型中的解释。

3.3.3 合同与代入

合同引理：因为其他部分已经确定，因此真值只与自由变元赋值相关。

代入分为代入和自由代入，还有代入引理。

3.3.4 重要有效式

有效式被分为联词类、等词类、量词基础类、量词交换类、量词分配类、量词消去类、代入类。

检验有效式的主要工具：合同引理、代入引理、逻辑等价替换定理、逻辑等价易字定理。

3.3.5 公式的范式

此节先讲了逻辑等价替换定理、逻辑等价易字定理。

范式：前束范式、埃尔布朗范式、斯库伦范式等。

3.4 公理系统

3.4.1 公理系统

为定义必然推出，引入一阶公理系统，分为公理和（有穷）推理规则。有很多种一阶公理系统但一般都等价。

常见两个公理系统：希尔伯特公理系统（公理多、推理规则少、线性结构）、根岑自然演绎系统（公理少、推理规则多、树形结构）。

常见公理和推理规则：命题公理、代入公理、分配公理、等词公理、概括公理、分离规则MP。

如前所述，推理规则是指从有穷个命题推出某个命题的简单直接的规则。具体到一 阶语言上，推理规则就是指从某个有穷的 L1 的公式集推出某个 L1-公式的简单直 接的规则。而公理是直接得到某个 L1-公式，它可以看作从 ∅ 推出某个 L1-公式的 规则。从这个意义上讲，公理都可以被看作推理规则。

由于推理规则就是指从有穷个命题推出某个命题的简单直接的规则，加之绝大多数 推理规则都是保真的，所以绝大多数推理规则都可以转换成某个逻辑有效式，这就 意味着绝大多数推理规则也可以被看作公理。

3.4.2 证明与演绎

几何证明一般有两种：初等几何从公理出发推出某个结论，这是一种无假设的证明；高等几何则有假设。在一阶逻辑中，无假设叫证明，有假设叫演绎。演绎这个词出自《朱子语类》卷六七：汉儒解经，依经演绎；晋人则不然，舍经而自作文。

注意区分定理、非定理、元定理（元语言中的定理）、内定理（对象语言中的定理）。了解语法蕴含、语法等价等概念。语法蕴涵符号是证明符号的推广，而演绎概念也是证明概念的推广。

3.4.3 重要元定理

演绎序列太长，因此此简化：已经证过的定理编号后列入证明中。但还是太长，就总结元定理和演绎规则。

例如（作为定理或推论）演绎、反证法、假言易位、归谬法、概括、语法等价替换定理、语法等价易字定理等。

3.4.4 演绎规则

例如全称量词引入规则、存在量词引入规则、量词消去规则、等词规则、代入规则等。

3.4.5 逻辑与理论

一阶理论是一阶逻辑的推广。

3.5 完全性定理

即 Γ ⊨ φ 当且仅当 Γ ` φ（符号没打出），这就是本节所要证明的（可数的）哥德尔完全性（Compleness）定理。严格说来，(⇐) 是可靠性（Soundness）定理，而 (⇒) 才是（可数的）哥德尔完全性定理。用亨金构造法证。

3.5.1 可靠性定理

（可靠性）. 设 Γ 是公式集，φ 是公式。如果 Γ ` φ（符号没打出），那么 Γ ⊨ φ。

3.5.2 可满足定理

先给出极大一致集的概念。

（可满足）. 设 Γ 是 L1 的公式集。如果 Γ 是亨金完全的且极大一致的，那么 Γ 是可满足的。

整体思路：先定义一个基于 Γ 的等价关系 ∼Γ，然后借助这个等价关系定义一个模 型 (M, v)，最后证明这个模型就是 Γ 的模型。

3.5.3 可扩张定理‬

可扩张定理断言断言的是所有一致的公式集都可以扩张成亨金完全的、极大一致的公式集。设 Γ 是 L1 的公式集，φ 是公式，c 不在 Γ 的任一公式中出现且 φ(c) 是自 由代入。如果 Γ ` φ，那么 Γ ` ∀xφ(c; x)。

3.5.4 完全性定理

设 L1 为可数的一阶语言。则如下命题成立 且等价： (1) 任给公式集 Γ，Γ 是一致的当且仅当 Γ 是可满足的； (2) 任给公式集 Γ 和公式 φ，Γ ⊨ φ 当且仅当 Γ ` φ（符号没打出）。

3.6 紧致性定理（紧性定理）

先证可数的紧致性定理。然后涉及一些拓扑的知识。给出了紧性定理的一些应用。

3.6.1 紧致性定理

（可数的紧致性，1929）. 设 L1 为可数的一阶语言。则如下命题成立且等价： (1) 任给公式集 Γ，Γ 是有穷可满足的当且仅当 Γ 是可满足的； (2) 任给公式集 Γ 和公式 φ，Γ ⊨ φ 当且仅当存在 Γ 的有穷子集 Γ0 使得 Γ0 ⊨ φ。

3.6.2 常见的应用

紧致性定理在数理逻辑中的应用可谓十分广泛，尤其在模型论中的应用几乎随处可 见，比如线序定理、超滤定理、无穷模型存在定理、非标准模型构造等。

3.6.3 拉姆齐定理

拉姆齐于 1928 年证明了拉姆齐定理的无穷版本和有穷版本2 ，标志着拉 姆齐理论3 的诞生。自此拉姆齐理论经过不断发展形成了一个独立的研究方向，并促使 了组合集合论4 等研究方向的产生。

3.6.4 广义初等类

借助紧致性定理讨论结构类的可以定义性问题，从而深入分析一阶语言表达力的局限性，引入初等类和广义初等类的概念。

3.7 哲学的应用

哲学里常用一阶逻辑分析部分论证的有效性。

逻辑的形式化方法：给定公理化的具体理论1 ；建立相应的形式语言，给定初始符号；建立语法，准确定义什么是公式；建立语义，准确定义什么是真的；建立公理系统，给定公理和推理规则；在公理系统下，准确定义什么是证明；把理论的公理与公理系统的公理合成一个公理集，形成该理论的公理系统。具体到一阶逻辑，即一阶逻辑的形式化方法，还要求其中的理论、语言、语法、语义、公理系统都是一阶的。

在形式化方法的基础上用一阶逻辑分析某些使用自然语言的哲学论证 的有效性，论证指用自然语言从有穷个自然语言命题推出某个自然语言命题的推理。论证步骤：一是针对哲学论证选择合适的一阶语言；二是 将哲学论证所涉及的自然语言命题形式化为一阶公式；三是区分清楚哲学论证的前提和结论；四是判断前提所对应的一阶公式组成的公式集 Γ 能否推出结论所对应的一阶公式 φ，即 Γ ⊨ φ 是否成立。如果成立那么论证有效，反之不然。而判断 Γ ⊨ φ 是否成立，一般采用语义赋值的办法或者语法证明的办法。

宇宙论论证：亚氏论证、安萨里卡拉姆宇宙论论证，卡拉姆是雄辩的、宗教哲学的意思。历史上有很多宇宙论论证。

第4章 一阶理论

（私货：我理解的就是，一阶理论是一阶逻辑在数学里的推广，所以以下都是数学理论，此章的正确标题是一阶数学理论。）

4.1 导言

在前面几章中，我们已经看到用形式化方法（公理化的、外延的）可以相对完美地 整理出通常使用的逻辑规律；在本章中，我们将进一步看到这种方法能够把握相当一部 分数学真理；在下一章中，我们会揭示形式化方法更加深刻的特性。 本章题目中的“一阶”这一定语表明，我们会基于一阶语言进行相应的讨论。但这 并不意味着，其他的形式语言，如命题语言、高阶语言或者模态语言不能用于这种形式 化的工作。之所以如此，是因为在具体的数学分支中，这种形式化的工作主要是基于一 阶语言进行的，并且此间已有一些自然而深刻的结果，以之为典范，或许可以使我们更 加深入有效地了解形式化方法。

4.2 结构与理论

此节梳理基本概念。

4.2.1 归约与膨胀

我们有加算和乘算，有运算律，对一个给定的论域，我们可以考虑让其携带不同的常量、关系、函数。这种添加或减少不同的常量、关系、函数的操作自然地就导出了结构间的归约与膨胀的概念，与之相对应，还有语言间的归约与膨胀的概念。 即讨论不同的结构。

4.2.2 结构间关系

如当我们手里有一类数学结构时，它们之间自然会有同态、同构等等这样的关系；与此同时，我们手里现在又有了可以用来描述这些数学结构的形式语言。

4.2.3 理论的性质

在本节里，我们会 回顾“理论”“公理”等基本概念的定义，同时也会引入“一致性”“范畴性”“完全性” 这三个在讨论理论时最常涉及的概念。

勒文海–斯库伦定理意味着，如果我们所面对的是一个无穷的数学结构，那么就不可 能找到一个理论能够使我们“范畴”地把握这一数学结构。

4.3 无端点稠密线序理论DLO

无端点稠密线序是非常自然的数学结构。对于无端点的稠密线序结构，我认为它是一个具有无限多个元素的序列，且在这个序列中不存在首尾元素。每个元素都有且仅有一个前驱和一个后继元素，且它们之间没有间隔，形成了一种连续的结构。这种结构在数学和计算机科学中具有重要的应用，例如在拓扑学中，无端点的稠密线序结构常用于描述一些无限维的空间。

4.4 随机图理论RG

随机图理论研究的是由随机过程生成的图结构。在随机图中，顶点和边都是随机的，而不是由事先确定的规则或模式确定的。随机图理论研究的问题包括性质、特征和行为、随机图模型的分析等等。

4.5 算术真理论

算术真理论中的典型问题是关于自然数的性质和关系的证明，比如加法和乘法的性质、数学归纳法的应用、质数分解等。通过应用逻辑推理和数学归纳法，我们可以在算术真理论的框架下证明这些性质和定理的真实性。

我们首先需要确定什么是算术命题以及何为算术 真，换言之，即明确所要分析的数学结构与相应的形式语言。

4.6 公理集合论

一阶集合论语言：非逻辑符号里只 有一个二元的关系符号 ∈。

公理：从集合论的角度来看，所有的对象都是集合，而首先，我们自然会接受，世界中是有对象的，由此就得到存在公理。蒯因强调同一性，因此得到外延公理，即即任一集合由它所包含的元素唯一确定。上述两条公理并没有向我们保证会有什么样的集合存在；一个自然的想法是，对给 定的一个集合，我们通常会用相应的性质来描述它，那么，反过来，每一条性质似乎也都应有一个集合与之对应。在集合论的早期历史中，这一想法被整理为所谓的概括原则但导出了悖论，因此修改。对集公理：对于任意的集合 x 与 y，存在着恰好以它们为元素的集合。并集公理：对每个集合 x，存在着集合，它恰好由 x 的元素的元素组成。幂集公理：对任意的集合 x，存在着集合，它恰好由 x 的所有子集所组成。无穷公理：存在着归纳集：∃xφind(x)。良基公理：每个非空集中都有“属于”极小元。

选择公理：对每个其元素非空且两两不交的集合的非空集族 X，都存在着代表元 集 S 使得 S 恰好从 X 中的每个集合里抽取一个元素。就是说是可选的而不是选不出的。

我们还希望能获得二元的加法函数的集合表示，引入替换公理模式与超穷递归构造方法。替换公理模式分弱替换公理模式和强替换公理模式，在已有的公理的 基础上它们是等价的。

4.7 相对一致性

一致性难证于是只证相对一致性。保守扩张能保证一致性，还有定义扩张的概念，都说明适当引入新符号不会破坏一致性。把一个公理系统看作从一个较小的系统出发，逐步加入新公理而得；直观上似乎自然的是，小系统一致性的可能性相对来说会更高，那么，假如我们倾向于相信一个小系统 是一致的，并且能证明增加某一（些）公理后的系统相对于原来的小系统是一致的，那 么我们也应该相信这一更大系统的一致性。再进一步，比如，我们相信一个小的集合论系统是一致的，那么它应该有模型，或 者说，它正确地“描述”了集合论宇宙；那么在这一小系统基础上增加新公理，在某种 意义上就是增加对集合论宇宙的“新信息”，或者说，限制小系统原来有的模型；下面我 们会看到，这种限制的信息可以用来保持一致性

第5章 不完全性

5.1 希尔伯特纲领

5.1.1 数学基础危机

数学三次危机：发现无理数、微积分被质疑、集合论悖论。

康托尔集合论悖论：尤拉里–佛蒂悖论（所有序数组成一个集合）、康托尔悖论（所有基数组成一个集合）、罗素悖论（所有不属于自身的集合组成一个集合）。

5.1.2 集合论公理化

尤拉里–佛蒂悖论、康托悖论与罗素悖论的本质是一样的，都是错误地使用了集合概念，问题出在概括公理（任给性质 φ(x)，{x | φ(x)} 都是集合），后来对该公理做了修正：任给性质 φ(x) 和集合 A，{x ∈ A | φ(x)} 都是集合。 这样一来上述悖论中的 Ω, Γ, R 都不再是集合，相应的悖论也消失了。为避免其他悖论开始公理化。给出集合论语言；建立语法，明确什么是项和公式；建立其语义，准确定义什么是真；建立合适的一阶公理系统，包括公理集和推理规则；定义什么是证明；找到公认的可以判断一个对象是不是集合的公理，加入公理集；任何一个对象，如果它是集合，那么它是集合这一点必须在该公理系统中得到证明 。集合论ZFC 给绝大部分现代数学提供了一个严谨的基础。其他公理化如皮亚诺算术公理化、希尔伯特初等几何公理化。

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