一阶模型理论（一）

1. 一阶语言和结构

2. 基本地图

3. 五个大定理

4. 三个有用的结构

5. 三个成功项目

参考书目

学术工具

其他互联网资源

相关条目

1. 一阶语言和结构

数学模型理论带有大量的符号，而 HTML 并不是它的最佳容器。在下文中，句法对象（语言、理论、句子）通常用罗马或希腊字母（例如 L、T、φ）书写，而集合论对象如结构及其元素则用斜体书写（A、a ）。两个例外是变量为斜体 (x, y)，元素序列用小写罗马字母 (a, b) 书写。

我们回顾并提炼了经典逻辑和模型论条目中的一些定义。签名是一组单独的常量、谓词符号和函数符号；每个谓词符号和函数符号都有一个元数（例如，如果其元数为 2，则它是二进制的）。每个签名 K 通过从签名中的符号以及逻辑符号（包括=）和标点符号构建公式来产生一阶语言。

如果 K 是一个签名，那么签名 K 的结构（比如 A）由以下几项组成：

一个集合称为 A 的定义域，写作 dom(A)；通常假设它是非空的；

对于 K 中的每个单独常数 c，dom(A) 的一个元素 cA；

对于元数为 n 的每个谓词符号 P，dom(A) 上的 n 元关系 PA；

对于元数为 n 的每个函数符号 F，一个从 dom(A) 到 dom(A) 的 n 元函数 FA。

A 的元素是 dom(A) 的元素。同样，A 的基数或幂就是其域的基数。由于我们可以从它生成的一阶语言 L 中恢复签名 K，因此我们可以并将签名 K 的结构称为 L 结构。我们将 c 视为结构 A 中元素 cA 的名称，其他符号也同样如此。

例如，实数域形成一个结构 R，其元素是实数，其签名由单个常量 0 组成，用于命名数字零，一个 1 元函数符号 − 表示减号，以及两个 2 元函数符号 +和 。为加号和次。乍一看，我们不能添加一个符号来表示 1/x，因为所有命名函数都必须在结构的整个域上定义，并且不存在像 1/0 这样的实数。但转念一想，这并不是一个严重的问题。任何有能力的数学家都会在除以 x 之前加上条件“x 不为零”，因此 1/0 的值是多少并不重要，我们可以无害地把它取为 42。但是大多数模型理论家对任何类型都感到不舒服除以零，所以他们坚持使用加号、乘号和减号。

如果 L 是签名 K 的一阶语言，那么 Tarski 的模型理论真值定义告诉我们何时 L 的句子在 A 中为真，以及何时将 A 的元素分配给变量满足 A 中的 L 公式。在谈论满足公式的分配时，模型理论家经常谈论由公式 φ(v1,…,vn) 定义的 A 元素的 n 元组集合；连接是，当且仅当每个 vi 到 ai 的赋值满足公式时，n 元组 (a1,…,an) 才在定义的集合中。

如果 φ 是一个句子，我们写

A ⊨ φ

表示 φ 在 A 中为真，或者换句话说，A 是 φ 的模型。如果 φ(v1,…,vn) 是一个带有自由变量的公式，如图所示，我们写

A ⊨ φ[a]

表示 n 元组 a 在由 φ 定义的集合中。 （经典逻辑的条目使用符号“A,s ⊨ φ”，其中 s 是对 L 的所有变量的任何赋值，它将 n 元组 a 中的第 i 个元素分配给 φ 中的每个变量 vi。）

两个 L 结构是完全相同的 L 句子的模型，这两个 L 结构被认为是基本等价的。基本等价是所有L-结构类上的等价关系。 L 中所有在 L 结构 A 中为真的句子的集合称为 A 的完整理论，用符号 Th(A) 表示。某个结构 A 的 Th(A) 理论被认为是完整的。 （根据一阶逻辑的完备性定理，参见经典逻辑的条目，一个理论当且仅当它在句法上最大一致时才是完备的。）两个结构 A 和 B 基本上等价当且仅当 Th( A) = Th(B)。

继续实数域 R 的例子：两个给定的结构在本质上是否等价通常并不明显。模型理论史前最伟大的成就之一是 Tarski 在 1930 年对 Th(R) 的描述（他在战后才完整发表；请参阅下面的参考书目中他的书）。除其他外，这个描述暗示了基本上等价于 R 的结构正是实闭域，这是代数学家本身已经知道的一类域。

当数学家引入一类结构时，他们喜欢定义他们所认为的这些结构之间的基本映射。相同签名K的结构之间的基本映射称为同态，定义如下。从结构 A 到结构 B 的同态是从 dom(A) 到 dom(B) 的函数 f，其属性是对于每个原子公式 φ(v1,…,vn) 和任何 n 元组 a = (a1,…, an) A 的元素，

A ⊨ φ [a] ⇒ B ⊨ φ [b]

其中 b 是 (f(a1),…,f(an))。如果我们用“⇔”代替引用条件中的“⇒”，我们就说 f 是 A 到 B 的嵌入。由于该语言包含 =，因此 A 到 B 的嵌入始终是一对一的，尽管它不必在 B 的域上。如果在 B 的域上，则从 dom(B) 到 dom(A) 的逆映射也是同态，并且嵌入及其逆都被称为同构。如果一个结构与另一个结构存在同构，我们就说两个结构是同构的。同构是固定签名 K 的所有结构类上的等价关系。如果两个结构是同构的，那么它们共享所有模型理论属性；特别是它们基本上是等效的。

如果A和B是签名K的结构，其中dom(A)是dom(B)的子集，并且K中的符号在A中的解释只是它们在B中的解释的限制，那么我们说A是子结构B 的外延，反之，B 是 A 的外延。如果 B 中还有一些 A 中没有的元素，我们说 A 是 B 的真子结构，B 是 A 的真外延。如果 B 是一个结构，X 是dom(B)的非空子集，则存在唯一的B的最小子结构，其域包含所有X。它被称为由X生成的B的子结构，我们通过首先将所有元素cB添加到X来找到它其中c是K的各个常数，然后在函数FB下关闭，其中F是K的函数符号。

例如，由数字 1 生成的域 R 的子结构由 1、0（因为它由常数 0 命名）、1+1、1+1+1 等、-1、-2 等组成，换句话说，整数环。 （乘法下也不需要封闭，因为乘法下整数集已经封闭。）如果我们也包含 1/x 的符号，则由 1 生成的子结构将是有理数域。因此子结构的概念对签名的选择很敏感。

2. 基本地图

设 L 为一阶语言，A 和 B 为 L 结构。假设 e 是一个函数，它将 A 的一些元素转换为 B 的元素。如果只要 e 域中的元素序列 a1, …, an 满足公式 φ(x1,…,xn)，我们就说 e 是初等映射A中L的)，它们在e下的图像满足B中相同的公式；在符号中

A ⊨ φ(a1,…,an) ⇒ B ⊨ φ(e(a1),…,e(an))。

如果 e 是基本映射且其域是 A 的整个域，则我们称 e 是 A 到 B 的基本嵌入。顾名思义，基本嵌入始终是嵌入。

如果存在从 A 到 B 的基本嵌入，则 A 和 B 基本等价。另一方面，基本等价结构之间、甚至同构结构之间的嵌入不一定是基本的。 （例如，将签名由 0 和 + 组成的整数的阿贝尔群写成 Z，从 Z 到 Z 的嵌入，取每个整数 n 到 2n 是一个嵌入，当然 Z 与其自身同构；但是这个嵌入不是初等的，因为 1 满足公式 Ø∃y(y + y = v1)，但 2 不满足。）

如果 A 是 B 的子结构并且包含图是基本嵌入，则我们说 A 是 B 的基本子结构，B 是 A 的基本扩展。从定义可以看出，A 的基本外延的基本外延又是 A 的基本外延。

基本嵌入是一阶模型理论中要考虑的自然映射。 1950 年左右，亚伯拉罕·罗宾逊 (Abraham Robinson) 印象深刻，一般来说，代数结构之间的映射似乎从来都不是初等的，而一些重要的映射（例如两个代数闭域之间或两个实闭域之间的嵌入）却是初等的。他还惊讶地发现，关于代数闭域的这一事实是表述希尔伯特零值定理的另一种方式。罗宾逊的这些观察对模型理论的发展产生了巨大的影响。用罗宾逊的术语来说，如果理论模型之间的每个嵌入都是基本的，那么一阶理论就是模型完备的。这个概念有很多用途，并且经常出现在代数模型理论的应用中。

与模型完整性密切相关但不应与之混淆的一个概念是量词的消除。假设 L 是一阶语言，T 是 L 中的理论，Φ 是 L 的一组公式。如果对于每个公式 Φ(x1,…,xn) L Φ 中有一个公式 ψ(x1,…,xn)，使得在 T 的每个模型中，φ 和 ψ 都由完全相同的 n 元组元素 (a1,…,an) 满足。 （塔斯基真值定义第 2.2 节中讨论的“量词消除方法”）是一种句法和前模型理论方法，用于证明将量词消除到一组特定的公式。）据说理论具有量词消除如果它消除了量词直至无量词公式。

模型完备性和量词消除之间的联系如下。罗宾逊表明，一种理论是模型完备的，当且仅当它消除了量词直至存在公式（即公式要么是无量词的，要么由一个或多个存在量词后跟一个无量词公式组成）。因此，具有量词消除的理论是模型完备的，但反之则不一定成立。尽管如此，证明一个理论是模型完备的有时是证明它具有量词消除的有用的第一步。

回到基本嵌入：它们有许多有用的属性。我们有四个人的空间。

向下的 Löwenheim-Skolem 定理：

假设 L 是具有 κ 公式的一阶语言，A 是 L 结构，并且 λ 是至少为 κ 但小于 A 基数的基数。还假设 X 是A. 那么 A 有一个基本子结构，其基数恰好为 λ，并且包含 X 中的所有元素。

在经典逻辑的条目中使用 Skolem 壳对此进行了证明。请注意，λ 必须是无限的，因为每种一阶语言都有无限多个公式。

初等链式定理：

假设 L 是一阶语言，A0, ​​A1, … 是 L 结构的序列（任意长度），使得序列中的任何结构都是序列中所有后续结构的基本子结构。那么就有一个唯一的最小L结构B，它包含序列中的所有结构作为子结构；该结构B是序列中所有结构的基本扩展。

初等合并定理：

假设 L 是一阶语言，A 是 L 结构，B、C 是 A 的两个基本扩展。然后有 B 的基本扩展 D 和 C 的基本嵌入 e 到 D 中，使得 (i) 对于A 的每个元素 a，e(a) = a，并且 (ii) 如果 c 是 C 的元素但不是 A 的元素，则 e(c) 不在 B 中。

初等合并定理是下一节中紧性定理的结果。

向上的 Löwenheim-Skolem 定理：

假设L是具有κ公式的一阶语言，A是基数是无限基数μ的L结构，并且λ是至少与κ和μ一样大的基数。那么 A 有一个基本扩展，其基数为 λ。

这也是从紧致性定理得出的，如经典逻辑条目所示。这个定理的名字有点不幸，因为这个定理首先是由塔斯基证明的，而斯科伦甚至不相信它（因为他不相信有不可数基数）。

还有一个使用初等合并定理和初等链定理的证明。可以证明结构A具有适当的初等外延A′。 （使用紧性定理和图引理可以证明这一点 - 参见下面的 3.1 和 3.2；另一个证明是通过超幂 - 参见下面的 4.1。）现在使用 A′ 并再次使用 A′ 来表示初等中的结构 B 和 C合并定理。那么定理中的D是A的初等扩张，并且由定理中的(ii)可知，它必须包含A′中不存在的元素，因此它是真初等扩张。重复此操作以获得 D 的适当基本扩展，依此类推，直到获得无限基本链。使用初等链定理找到位于该链顶部的 A 的初等延伸。不断重复这些动作，直到得到基数至少为 λ 的 A 的基本扩展。然后，如有必要，请使用向下 Löwenheim-Skolem 定理将基数精确降低到 λ。这种论证在一阶模型理论中很常见。通过在构建步骤中仔细选择汞齐，我们通常可以确保顶部结构具有我们可能想要的其他属性（例如饱和度，请参见下面的 4.2）。

3. 五个大定理

本节报告的五个定理在某种意义上是经典模型理论的支柱。它们都是关于一阶模型理论的定理。二十世纪第三个二十世纪所做的大量工作致力于在一阶模型理论中计算这些定理的结果，以及类似定理对于非一阶语言的适用程度。

3.1 紧性定理

如果 T 是一阶理论，并且 T 的每个有限子集都有一个模型，则 T 有一个模型。

这个定理在经典逻辑入门中有一个证明。该定理有几个有用的释义。例如，它相当于以下语句：

假设 T 是一阶理论，φ 是一阶句子。如果 T ⊨ φ 则存在 T 的有限子集 U 使得 U ⊨ φ。

（有关模型理论结果的概念 ⊨，请参见模型理论条目。要从第一个陈述导出第二个陈述，请注意，当且仅当不存在理论 T ∪ {Ø φ}。）

Anatolii Mal’tsev 在 1938 年首次给出了紧致性定理（对于任何签名的一阶逻辑），并在 1940 年 1 月用它来证明了几个关于群的定理；这似乎是模型论在经典数学中的首次应用。几年后，莱昂·亨金和亚伯拉罕·罗宾逊独立地重新发现了该定理，并给出了一些进一步的应用。对于几乎所有无限语言，该定理都严重失败。

3.2 图引理

如果 A 是 L 结构，那么我们将 A 的图构造如下。首先向 L 添加新的单个常量，作为 A 的所有元素的名称。（这说明在一阶模型理论中，我们如何轻松地发现自己使用不可数签名。这些签名中的“符号”是抽象集合 -理论对象，而不是页面上的标记。）然后使用 L 和这些新常数，A 的图是 A 中为真的所有原子句子和原子句子的否定的集合。

如果 B' 是 A 图的模型，并且 B 是从签名中删除了新常数的 B'，则存在 A 嵌入到 B 中的情况。

即，如果 A 的元素由新常量 c 命名，则将该元素映射到 B' 中名为 c 的元素。该引理的一个变体用于证明初等合并定理。

3.3 林登插值定理

该定理可能是模型理论定理中最长的谱系，因为它概括了三段论的分布定律，而三段论至少可以追溯到文艺复兴早期。如果我们假设我们的一阶语言有符号 ∧、∨ 和 Ø，但没有 → 或 ⇔，则该定理最容易表述。那么，如果谓词符号 R 在公式 φ 中的出现位于偶数（或奇数）个 ← 出现的范围内，则该谓词符号 R 的出现被称为正（或负）。

假设L和M是一阶语言，L∪M是包含L和M的最小一阶语言，L∩M是包含L和M中所有公式的语言。假设T是L 中的理论，U 是 M 中的理论，并且没有 (L ∪ M)-结构既是 T 的模型又是 U 的模型。那么有一个句子 φ of L ∩ M 在 T 的所有模型中都成立并且在 U 的所有模型中为假。（这个句子 称为插值。）此外，每个在 φ 中出现正的谓词符号在 T 的某个句子中也有正的出现，在 U 的某个句子中也有负的出现，反之，每个在 φ 中出现负数的谓语符号在 T 的某些句子中出现负数，在 U 的某些句子中出现正数。

该定理有多个证明，但并非所有证明都是模型论的。如果没有最后一句，该定理被称为克雷格插值定理，因为威廉·克雷格在罗杰·林登于 1959 年发现完整陈述之前几年就证明了这个版本。正如克雷格当时指出的那样，他的插值定理为埃弗特·贝斯的插值定理提供了简洁的证明可定义性定理，其运行过程如下。

假设L是一阶语言，M是通过向L添加一个新的谓词符号R而得到的一阶语言。还假设T是M中的一个理论。如果以下条件为假，我们说T隐式定义了R有两个 M 结构，它们是 T 的模型，具有相同的元素，并以相同的方式解释 L 的所有符号，但以不同的方式解释符号 R。如果存在 L 的公式 φ(x1,…,xn)，使得在 T 的每个模型中，公式 φ 和 R(x1,…,xn) 都由完全相同的 n- 满足，则我们说 T 明确定义了 R元素的元组 (a1,…,an)。很容易看出，如果 T 显式定义 R，那么它就隐式定义 R。 （这一事实被称为帕多亚方法；帕多亚使用隐式可定义性的失败来证明显式可定义性的失败。）贝丝定理是相反的：

假设L、M、R和T如上。如果 T 隐式定义 R，则 T 显式定义 R。

3.4 省略类型定理

该定理需要一些初步定义。假设L是一阶语言，T是L中的完整理论，Φ是L的一组公式，它们都具有自由变量x（并且没有其他自由变量）。如果 A 中存在一个元素满足 Φ 中的所有公式，我们就说 L 结构 A 实现了 Φ；如果 A 没有这样的元素，我们说 A 省略了 Φ。如果 T 的结果包括句子 ∃xψ(x) 和句子 ∀x(ψ(x) → φ( x)) 只要 φ(x) 是 Φ 中的公式。不难看出，如果T中存在Φ的支持，则T的每个模型都实现Φ。反过来并不总是正确的，但是省略类型定理告诉我们，如果我们将自己限制在可数一阶语言，则它是正确的：

假设L是一阶语言，有可数个公式。假设T是L中的完备理论，Φ是L的一组公式，它们都具有自由变量x。最后假设每个只有可数个元素的 T 模型都实现 Φ。那么 T 中就存在 Φ 的支持。（换句话说，在 T 的任何模型中都不能省略‘类型’ Φ 是有一个有限的原因的。）

省略类型定理可以追溯到 20 世纪 50 年代中期。这绝对取决于语言是否是一阶且可数的。它有几个有用的概括，例如模型理论强迫，它类似于集合论中的强迫结构。事实上，用于模型理论强迫的游戏（参见逻辑和游戏条目）也可以用于证明省略类型定理。对于不可数一阶语言也有类似但更复杂的定理；其中一些可以解释为无限语言的省略类型定理。

3.5 初始模型定理

如果无量词公式具有以下三种形式之一，则称其为 Horn 公式（以 Alfred Horn 命名）

ψ,

φ1 ∧ … ∧ φn → ψ,

Ø(φ1 ∧ … ∧ φn),

其中公式 φ1, …, φn, ψ 都是原子的。通用 Horn 句子（计算机科学家也称为 Horn 子句）是由全称量词和无量词 Horn 公式组成的句子；如果其中没有出现负号（即，如果它不是来自第三类无量词霍恩公式），则称它是严格的。

令 T 为由严格的通用 Horn 句子组成的理论。那么T有一个模型A，其属性是对于T的每个模型B，从A到B都有唯一的同态。（这样的模型A称为T的初始模型。它在同构方面是唯一的。）

该定理是 Mal’tsev 对称为生成元和关系构造的群论构造的概括。它是代数规范背后的主要思想，代数规范是计算机科学中系统规范的一种方法。系统所需的行为被写成一组严格的通用霍恩句子，然后这些句子的初始模型就是所需系统的抽象版本。

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