2.5. 理论与模型

这一节将讨论一阶逻辑实现各种具体理论的方式, 并引入一些模型论的观点.

我们前面提到, 一阶语言的结构是一个集合配上其上的一些东西, 但很多时候我们并不是只有这些一阶逻辑天生应当具有的逻辑约束, 而是希望能定义出适合我们使用的数学结构, 换言之, 我们会加入一些限制条件, 以赋予这个语言我们想要的数学性质.

在一般的数学实践中, 很少有人区分 " 理论 " 与 " 模型 ". 例如, 在学习群论的时候, 并没有人会刻意的把 " $G$ 是一个群 " 说成 " $G$ 及其上的某某结构构成群理论的一个模型 ", 但有的时候这样考虑会更好. 例如, 如果要考虑 " 满足实数公理的模型两两同构 ", 或是 " 稠密无端点线序可数集一定与 $Q$ 同构 ", 很难说这是某个特别的模型的性质, 因为这其实就是这个理论的性质. 从理论与模型之间的关系入手来研究数学, 换言之应用模型论, 已经在现代数学中取得了相当的成果, 这里不再进一步举例.

回顾我们对于语句的定义. 若一个公式中没有自由出现的变元, 我们就称之为一个语句, 而语句在一个结构中不需要赋值就能直接确定真假, 因此我们以下考虑一个结构与这结构上的一些语句, 就无需再考虑赋值. 我们会发现, 大部分数学的定义都是语句集而非公式集, 从而这样考虑是切合实践实际的.

如果出现 $σ$ 之类的符号, 我们就默认它是个语句; 如果要说公式, 我们总会写成 $φ (x_{1}, x_{2}, ..., x_{n})$ 的形式, 标明其中所有的自由变元. 有时也概括的写成 $φ (S)$ , 表示其自由变元都在集合 $S$ 中. 我们默认 $M$ 是 $M$ 的论域, 甚至在无歧义的时候自然地混用二者.

定义 2.5.0.1 (结构之间的映射). 我们固定一个语言 $L$ , 考虑它的两个结构 $M$ 与 $N$ .

若一个映射 $F : M \to N$ 满足:

1.	对每个常元符号 $c$ , $F (c^{M}) = c^{N}$
2.	对每个 $n$ 元函数符号 $f$ 与 $M$ 中的 $n$ 个元素 $a_{1}, a_{2}, ..., a_{n}$ , 都有 $F (f^{M} (a_{1}, a_{2}, ..., a_{n})) = f^{N} (F (a_{1}), F (a_{2}), ..., F (a_{n}))$
3.	对每个 $n$ 元谓词符号 $P$ 与 $M$ 中的 $n$ 个元素 $a_{1}, a_{2}, ..., a_{n}$ , 都有 $(a_{1}, a_{2}, ..., a_{n}) \in P^{M} \to (F (a_{1}), F (a_{2}), ..., F (a_{n})) \in P^{N}$

则称 $F$ 是一个从 $M$ 到 $N$ 的同态. 如果谓词符号那里的 $\to$ 是 $\leftrightarrow$ , 则进一步称嵌入. 如果进一步这嵌入还是个双射, 则称这是个同构, 记作 $M ≅ N$ .

接下来考虑所谓的初等 (elemantary, 又译为基本) 性. 具有这一性质的能且只能把一阶的性质说完, 而对这模型可能具有的高阶性质没有保障, 所以称之为初等, 但这其实已经比一般的要求强一些了.

我们称嵌入 $F : M \to N$ 是初等嵌入, 若对任何的公式 $φ (x_{1}, x_{2}, ..., x_{n})$ 和 $a_{1}, a_{2}, ..., a_{n} \in M$ 都有 $M ⊨ φ (a_{1}, ..., a_{n}) \leftrightarrow N ⊨ φ (F (a_{1}), ..., F (a_{n}))$ . 此处记法的合理性由赋值对公式的自由变元决定性保证.

如果 $M \subseteq N$ 且 $M$ 上的结构都恰好是 $N$ 的结构限制而来, 则称 $M$ 是 $N$ 的子结构, 如果刻意要写最好写 $M \subseteq N$ . 如果还有自然嵌入 $i : M ↪ N$ 是初等嵌入, 则称 $M$ 是 $N$ 的初等子结构, 记作 $M ≺ N$ .

我们将很少处理同态, 因为它的限制条件太弱, 得不出什么有意义的结果. 这里讨论一下嵌入的性质, 并且建立一些类似于群论的定理. (其实群论也可以按这样的想法认为是泛代数 (Universal Algebra) 的一种特化, 此处且按下不表)

定理 2.5.0.2. 一个函数 $F : M \to N$ 是嵌入, 当且仅当对任意的无量词公式 $φ (x_{1}, x_{2}, ..., x_{n})$ 和 $a_{1}, a_{2}, ..., a_{n} \in M$ 都有 $M ⊨ φ (a_{1}, a_{2}, ..., a_{n}) \leftrightarrow N ⊨ φ (F (a_{1}), F (a_{2}), ..., F (a_{n}))$ .

一个嵌入 $F : M \to N$ 还满足: 对任意的存在公式 $φ (x_{1}, x_{2}, ..., x_{n})$ 和 $a_{1}, a_{2}, ..., a_{n} \in M$ 都有 $M ⊨ φ (a_{1}, ..., a_{n}) \to N ⊨ φ (F (a_{1}), ..., F (a_{n}))$ .

所谓存在公式, 就是由一大串存在量词量化一个无量词公式得来的公式 (换言之, 没有架在两个已经被量化了的公式之间的逻辑连接词). 显然类似定义的全称公式也就是在它前面多了一个 $\neg$ , 无关大局.

证明. 先来看第一部分. 嵌入满足这个条件是归纳显然的, 这个条件指出嵌入则只需要对项

t

考虑

t \approx t

这种公式. 第二部分也是传统方法, 把 " 满足存在公式 " 变成一堆

M

里面的实例, 然后将它们映到

N

中.

$□$

评注. 这个定理给出了嵌入到底比初等嵌入的要求弱了多少的一个直观看法.

定理 2.5.0.3. 若 $M$ 是 $N$ 的子结构, 则 $i : M ↪ N$ 自然成为嵌入.

证明由上一个定理是显然的.

定理 2.5.0.4. 给出一个结构 $M$ 及其任意的一个子集 $S$ , $S$ 可以在 $M$ 中生成一个最小的子结构 $< S >$ 包含 $S$ .

这个的证明只需要意识到子结构的非空任意交仍然是个子结构.

定理 2.5.0.5. 如果 $F : M \to N$ 是一个初等嵌入, 则有 $M$ 的扩张 $\overset{ˉ}{M}$ 使得 $M$ 是 $\overset{ˉ}{M}$ 的初等子结构, 且 $F$ 可以提升为 $\overset{ˉ}{F} : \overset{ˉ}{M} \to N$ 成为一个同构.

这个证明甚至不需要常数构造法, 直接把

N - F (M)

切下来接在

M

旁边就可以了.

接下来讨论带有初始公理的数学理论.

定义 2.5.0.6 (理论与模型). 假定我们有指定的语言 $L$ .

对于句子集 $Σ$ , 若结构 $M$ 满足 $\forall σ \in Σ M ⊨ σ$ , 则称 $M$ 是 $Σ$ 的一个模型, 记为 $M ⊨ Σ$ .

对于句子集 $Σ$ 与句子 $σ$ , 若每个 $M ⊨ Σ$ 都有 $M ⊨ σ$ 就称 $Σ$ 蕴含 $σ$ , 记为 $Σ ⊨ σ$ . (我们不再考虑语法蕴含了, 如果真的要提最好称之为推断)

如果句子集 $Σ$ 对蕴含封闭, 换言之对任何句子 $σ$ 都有 $Σ ⊨ σ \to σ \in Σ$ , 就称 $Σ$ 是一个 $L$ 理论, 简称理论.

如果一个理论 $Σ$ 有一个模型, 则称这个理论是一致的 (相容的, 可满足的). 如果一个理论 $Σ$ 满足对任何 $σ$ 都有 $σ \in Σ \lor \neg σ \in Σ$ , 则称这理论是完备的.

对任何一个结构 $M$ , 定义这个结构的理论为 $Th (M) = {σ ∣ M ⊨ σ}$ , 它显然是个一致完备的理论.

如果对一个理论 $Σ$ , 能找到它的一个递归子集 $Γ$ , 使得 $Σ ⊨ σ$ 当且仅当 $Γ ⊨ σ$ , 则称这个子集是原来的理论的一组公理. 有公理的理论称为可公理化的理论.

如果有两个结构 $M$ 与 $N$ , 它们的理论是一样的, 则称它们是初等等价的, 记作 $M \equiv N$ .

如果有一族结构 $K = {M ∣ M ⊨ Σ}$ , 其中 $Σ$ 是个理论, 则称这一族结构形成一个初等类.

我们熟知的许多数学理论, 有的是一阶的 (如集合论, 群论, 向量空间), 有的则不是一阶的 (挠群, 有限域). 注意, 不是一阶的理论往往会导致全体模型无法形成初等类, 从而用一阶语言试图描述时会产生伪 (pseudo) 结构, 如伪挠群和伪有限域.

关于模型最重要的定理是如下的紧致性定理.

定理 2.5.0.7. 若一个理论是有限可满足的 (换言之, 每个有限子句子集都是可满足的), 则这个理论是可满足的.

证明. 由完备性定理可以简单地推出, 细节留作练习.

$□$

然而, 这并不意味着紧致性定理很菜; 事实上在某些观察下, 紧致性定理反而是一阶逻辑的本质特征. 紧致性定理也可以视作选择公理的一个重要弱化形式 (看过 2.7 节后, 读者可以思考完备性定理的证明何处用到了选择公理), 因此在数学的许多领域运用它常常比运用选择公理更简单, 这里不再举例.

定理 2.5.0.8 (Lindström). 我们称 $L = (S, T)$ 为一个抽象逻辑, 这里 $S$ 是个集, $T$ 是结构与 $S$ 中元素的一个关系, 且 $L$ 在同构、重命名、自由延拓、否定、合取和存在量化下均保持封闭.

全体一阶逻辑的句子 $S_{0}$ 与通常定义的满足关系 $T_{0} (M, ϕ) \leftrightarrow M ⊨ ϕ$ 构成一阶逻辑 $L_{ωω} = (S_{0}, T_{0})$ .

若抽象逻辑 $L \geq FO$ 具有可数紧致性和下行 Lowenheim-Skolem 性质, 则 $L \equiv L_{ωω}$ .

名字空间

视图

2.5. 理论与模型