2.8. 型与量词消去

这一节, 我们来讨论模型中是否有满足我们所想要的性质的对象. 首先, 我们来看型这一概念的定义.

定义 2.8.0.1 (有序元素组的型). 对语言 $L$ 的结构 $M$ 中的一个有限有序元素组 $\overset{a}{ˉ} = (a_{1}, ..., a_{n})$ , 我们定义其型为 $tp^{M} (\overset{a}{ˉ}) = {ϕ (x_{1}, ..., x_{n}) ∣ M ⊨ ψ (a_{1}, ..., a_{n})}$ .

评注. 换言之, 我们将 $M$ 中的 $(a_{1}, ..., a_{n})$ 满足的全部性质收集在一起. 然而, 更多的时候我们想脱离具体的 $\overset{a}{ˉ}$ 而只看这一集公式, 因此我们需要另外的定义.

定义 2.8.0.2 (理论的完全型). 对语言 $L$ 的理论 $T$ , 一个公式集 $Σ$ 若满足存在模型 $M$ 和其中的有限有序元素组 $(a_{1}, .. 。, a_{n})$ 使得 $Σ = tp^{M} (\overset{a}{ˉ})$ , 则称 $Σ$ 是理论 $T$ 的完全 $n$ 型, 全体完全 $n$ 型的集记为 $S_{n} (T)$ .

然而, 有的时候我们只知道完全型中的一部分公式, 这时如何确定它们是否能扩张为一个完全型呢? 我们接着考虑以下概念.

定义 2.8.0.3 (实现与省略). 对语言 $L$ 中的一族 $n$ 自由变元句子集 $Σ_{n}$ , 若结构 $M$ 中存在一个有限有序元素组 $\overset{a}{ˉ} = (a_{1}, ..., a_{n})$ 使得 $\forall ϕ \in Σ_{n} (M ⊨ ϕ (\overset{a}{ˉ}))$ , 则称 $\overset{a}{ˉ}$ 在 $M$ 中实现了 $Σ_{n}$ , 有时也称作 $M$ 实现了 $Σ_{n}$ . 如果不存在实现 $Σ_{n}$ 的 $\overset{a}{ˉ}$ , 则称 $M$ 省略了 $Σ_{n}$ .

这诱导出以下想法.

定义 2.8.0.4 (理论的部分型). 对语言 $L$ 的理论 $T$ , 若存在模型 $M$ 实现一族 $n$ 自由变元句子集 $Σ_{n}$ , 则称 $Σ_{n}$ 是 $T$ 的部分 $n$ 型.

我们接下来指出这些定义的命名中暗示的定理.

定理 2.8.0.5. 一个 $Σ$ 是部分型当且仅当它是一个完全型的子集; 一个部分型 $Σ$ 是完全型当且仅当它是极大部分型 (换言之向其中加入任何公式后均不再构成部分型).

证明. 第一个由定义是显然的; 第二个考虑

tp

的定义也是显然的.

$□$

然而, 部分型最厉害的地方在于, 它也有一个紧致性定理.

定理 2.8.0.6. 一个 $Σ$ 是部分型, 当且仅当它的每个有限子集都是部分型.

证明. 假设

Σ

想成为部分

n

型, 在语言

L

中加入

n

个新常元

\overset{c}{ˉ}

, 然后考虑理论

T \cup {ϕ (\overset{c}{ˉ}) ∣ ϕ \in Σ}

, 对这个理论的模型用紧致性定理即可.

$□$

对于完备理论, 我们还可以加强这个紧致性定理, 只在某一个模型中考虑, 这显然是因为它的所有模型都是初等等价的.

定理 2.8.0.7. 如果有完备理论 $T$ 的模型 $M$ , 则:

1.	$Σ$ 是部分型, 当且仅当它的每个有限子集都在 $M$ 中被实现.
2.	$S_{n} (T) = {tp^{N} (\overset{a}{ˉ}) ∣ M ≺ N \land a_{1}, ..., a_{n} \in N}$

证明. 对第一个, 显然只要证明每个有限部分型被实现当且仅当在 $M$ 中被实现; 这是初等等价性带来的.

对第二个, 其实只要证明每个部分型都在一个

N ≻ M

中被实现. 这是因为如果它在一个

M^{'}

中被实现, 我们用初等融贯把

M

和

M^{'}

融贯为一个

N

, 就可以得到它在

N

中被实现的证据.

$□$

$S_{n} (T)$ 构成一个有趣的拓扑空间, 我们将发现紧致性定理确实谈论了这个空间的紧致性.

定义 2.8.0.8 (型的空间). 在 $S_{n} (T)$ 中, 由全体公式 $ϕ$ 定义的 $[{ϕ}] = {p \in S_{n} (T) ∣ ϕ \in p}$ 为基自然生成 $S_{n} (T)$ 上的一个拓扑.

定理 2.8.0.9. $S_{n} (T)$ 是紧致 $T_{2}$ 完全不连通零维空间, 开闭基就是这些 $[{ϕ}]$ .

其实, 我们初始版本的紧致性定理也可以变成一个拓扑空间的紧致性.

定义 2.8.0.10. 全体完备一致 $L$ 理论的集合 $T$ 上, 由全体句子 $σ$ 定义的 $[{σ}] = {T \in T ∣ σ \in T}$ 为基自然生成 $T$ 上的一个拓扑.

定理 2.8.0.11. $T$ 是紧致 $T_{2}$ 完全不连通零维空间, 开闭基就是这些 $[{σ}]$ .

我们定义的两种 $n$ 型有两种可能的扩展定义: 一种是允许更多的变元, 一种是允许临时扩张语言. 我们现在来讨论这两者. 首先, 我们介绍可定义的概念.

定义 2.8.0.12. 对 $L$ 结构 $M$ , 给定 $A \subseteq M$ 和 $X \subseteq M^{n}$ , 我们可以定义 $X$ 的 $A$ 可定义子集的集族为 $Def_{A} (X) = {Y \subseteq X ∣\exists ϕ (\overset{x}{ˉ}, \overset{y}{ˉ}) \exists \overset{ˉ}{b} \in A^{m} (Y = {\overset{a}{ˉ} \in X ∣ ϕ (\overset{a}{ˉ}, \overset{ˉ}{b})})}$ . 我们更细致地称公式 $ϕ$ 与参数 $\overset{ˉ}{b}$ 在 $X$ 上定义了 $Y$ .

对 $A \subseteq M$ , 我们定义其可定义闭包为 $dcl_{M} (A) = {b \in M ∣ {b} \in Def_{A} (M)}$ , 定义其代数闭包为 $acl_{M} (A) = {b \in M ∣\exists S \in Def_{A} (M) (b \in S \land ∣ S ∣ < ω)}$ .

首先, 我们论证这两种闭包确实是闭包算子. 单调性与单增性都是显然的, 我们只论证幂等性.

定理 2.8.0.13. $dcl_{M} (dcl_{M} (A)) = dcl_{M} (A)$ , $acl_{M} (acl_{M} (A)) = acl_{M} (A)$

证明. 我们自然可以直接验证, 但这里有一种更优雅的方式, 我们可以指出它们甚至是有限闭包算子.

定义 2.8.0.14. 称闭包算子 $C$ 是有限的, 若 $a \in C (A)$ 指出存在有限子集 $A_{f} \subseteq A$ 满足 $a \in C (A_{f})$ .

称闭包算子 $C$ 满足交换性质, 若 $a, b \neq \in C (X)$ 时必有 $a \in C (X \cup {b}) \leftrightarrow b \in C (X \cup {a})$ .

一个集合 $X$ 连同其上一个满足交换性质的有限闭包算子称作一个拟阵. 此时这个闭包算子又常常记为 $span$ .

虽然

a c l

并不总是满足

span

的条件, 但有限性和一个长得很像交换性的性质合在一块可以用单调和单增推出幂等.

引理 2.8.0.15. 如果一个 $C : P (X) \to P (X)$ 是有限、单调、单增的, 且满足 $\forall S \subseteq X \forall a, b \in X (a \in C (S) \land b \in C (S \cup {a}) \to b \in C (S))$ , 则 $C$ 是有限闭包算子.

证明. 只要验证幂等. 显然

C (C (X)) \supseteq C (X)

, 我们只要证明

C (C (X)) \subseteq C (X)

. 对

b \in C (C (X))

, 有限性指出存在

a_{1}, ..., a_{n} \in C (X)

使得

b \in C (a_{1}, ..., a_{n})

. 我们的条件指出

a \in C (X) \to C (X) = C (X \cup {a})

, 因此

C (a_{1}, ..., a_{n}) \subseteq C (X \cup {a_{i}}) = C (X)

.

$□$

现在我们来验证 $a c l_{M}$ 有限且满足上引理的条件. 事实上, $a c l_{M}$ 有限是因为定义只用到有限个参数, 上引理的条件则可通过考虑最小的包括 $a$ 的有限可定义集, 用其中的全体元素来模糊 $a$ 即可.

类似地可以验证

d c l_{M}

的性质.

$□$

接下来, 我们来考虑何时可以把闭包算子中的下标去掉.

定理 2.8.0.16. 如果 $N ≺ M$ , 且 $A \subseteq N \subseteq M$ , 则 $dcl_{N} (A) = dcl_{M} (A)$ , $acl_{N} (A) = acl_{M} (A)$ .

证明. 这是因为在语言

L_{A}

中仍然有

N ≺ M

, 而这指出

p hi

在

N

中与在

M

中定义出相同的对象.

$□$

推论 2.8.0.17. 若 $N ≺ M$ , 则 $dcl_{M} (N) = acl_{M} (N) = N$ .

现在回到对型的处理上.

定义 2.8.0.18. 对指标集 $I$ 和语言 $L$ 的结构 $M$ 中的一个以 $I$ 为指标的元素组 $A = {a_{i} ∣ i \in I} \subseteq X$ , 我们定义其型为 $tp^{M} (A) = {ϕ (x_{i_{1}}, ..., x_{i_{n}}) ∣ M ⊨ ψ (a_{i_{1}}, ..., a_{i_{n}}), i_{j} \in I, a_{i_{j}} \in A}$ .

我们同理定义完全 $I$ 型与部分 $I$ 型. 注意, 我们默认了语言的变元集有一子集以 $I$ 为指标集, 因此必须放弃语言的变元集可数的假设.

对语言 $L$ 的结构 $M$ 中的一个有限有序元素组 $\overset{a}{ˉ} = (a_{1}, ..., a_{n})$ 和子集 $B \subseteq M$ , 我们定义其型为 $tp_{B}^{M} (\overset{a}{ˉ}) = {ϕ (x_{1}, ..., x_{n}) ∣ M ⊨ ψ (a_{1}, ..., a_{n})}$ , 这里 $ϕ$ 是加入了全体 $B$ 中元素为常元的语言 $L_{B}$ 的公式.

其余定义同理.

这两个延伸定义都是相当自然的. 第一种延伸定义用得较少, 我们现在用第二种延伸定义来讨论集合的型.

定义 2.8.0.19. 对 $L$ 结构 $M$ 的子集 $A \subseteq M$ , 我们称理论 $Th_{A} (M)$ 的部分型与完全型为 $A$ 的部分型与完全型, 全体完全 $n$ 型构成的空间记为 $S_{n}^{M} (A)$ . 这里 $Th_{A} (M)$ 是 $M$ 作为扩张语言 $L_{A}$ 的结构的理论.

由于 $Th_{A} (M)$ 自动的是完备一致理论, 我们同 $S_{n} (T)$ 一样有以下这些结果.

定理 2.8.0.20. 以下定理对 $S_{n}^{M} (A)$ 同样成立.

1.	$S_{n}^{M} (A) = {tp_{A}^{N} (\overset{ˉ}{b}) ∣ M ≺ N, \overset{ˉ}{b} \in N^{n}}$
2.	$L_{A}$ 公式集是部分型, 当且仅当它的每个有限子集都在 $M$ 中被实现, 当且仅当它是一个完全型的子集. 完全型是极大部分型.
3.	$S_{n} (A)$ 是一个紧致 $T_{2}$ 完全不连通零维空间.

证明. 显然.

$□$

最后, 我们来给出著名的省略型定理, 它指出非主型总是被某个模型省略. 首先仍然来看基础的定义.

我们先对集合的型定义主型. 固定一个可数语言 $L$ 的结构 $M$ 的子集 $A \subseteq M$ .

定义 2.8.0.21. 如果完全型 $p \in S_{n}^{M} (A)$ 对应的 ${p} \subseteq S_{n}^{M} (A)$ 是开闭集, 则称 $p$ 是主型. 换言之, 若存在 $ϕ$ 使得 ${p} = [{ϕ}]$ , 则 $p$ 是主型. 不是主型的型称作非主型.

主的意思是必须存在.

定理 2.8.0.22. 每个主型都在 $M$ 中实现.

证明. 这是因为

p

有限可满足, 从而

ϕ

必须被满足, 这又指出

p

被实现.

$□$

类似地, 我们也可以定义完备理论的主型. 仍然固定一个可数语言

L

上的完备理论

T

.

定义 2.8.0.23. 如果完全型 $p \in S_{n} (T)$ 对应的 ${p} \subseteq S_{n} (T)$ 是开闭集, 则称 $p$ 是主型.

定理 2.8.0.24. 每个主型都在每个 $T$ 的模型中实现.

证明. 对任何

T

的模型

M

, 显然有

S_{n} (T) = S_{n}^{M} (\emptyset)

.

$□$

我们的目标是以下定理.

定理 2.8.0.25 (省略型定理). 如果有一列非主型 $p_{i} \in S_{n_{i}} (T)$ , 则存在 $T$ 的可数模型 $M$ 省略其中每个型.

这个定理的证明非常奇妙, 因为它用到了理论空间的 Baire 性质, 这是 Baire 定理所允许的.

证明. 我们向 $L$ 中加入一列常元 ${c_{n} ∣ n \in ω}$ , 得到一个新的语言 $L^{'}$ . 令 $L^{'}$ 中全体延伸一开始的理论 $T$ 的完备理论 $T^{'}$ 形成一个空间 $S$ . 事实上由于这始终是可数语言, 它就是 $S_{ω} (T)$ , 因而是个紧致 $T_{2}$ 完全不连通零维空间.

我们用这列 $c_{i}$ 来讨论 $T^{'}$ 的见证性.

定义 2.8.0.26. 称 $L^{'}$ 的理论 $T^{'}$ 对常元组 ${c_{n} ∣ n \in ω}$ 具有见证性, 若对每个公式 $ϕ (x)$ , $T^{'} ⊨ \exists x (ϕ (x))$ 时均有一个 $i \in ω$ 使得 $T^{'} ⊨ ϕ (c_{i})$ .

引理 2.8.0.27. 在 $S$ 中, 全体对 ${c_{n}}$ 具有见证性的理论 $T^{'}$ 构成的集合 $W \subseteq S$ 是余第一纲集.

证明.

$□$

接下来, 我们考虑 $σ \in ω^{< ω}$ , 每个 $σ$ 都给出一个 $π_{σ} : S \to S_{n} (T)$ , 它只保留变元为 $c_{σ (0)}, ..., c_{σ (n - 1)}$ 的那些公式. 、

引理 2.8.0.28. $π_{σ}$ 是连续函数, 且将开闭集映为开闭集.

证明.

$□$

接下来, 我们来看看谁不被实现.

引理 2.8.0.29. 对非主型 $p \in S_{n} (T)$ , 存在余第一纲集 $V_{p} \subseteq S$ 使得对每个 $T^{'} \in V_{p}$ , 此时的任何 $σ \in ω^{n}$ 均让 $p$ 不被 ${c_{σ (i)} ∣ i \in n}$ 实现.

证明.

$□$

最后, 这个定理的证明水到渠成. 第一个引理给出一个余第一纲集

W

, 第三个引理对每个

p_{i}

给出一个余第一纲集

V_{i}

, Baire 纲定理指出它们全部交起来不空, 因此不妨假定其中有一个理论

T^{'}

. 由于它对

{c_{n} ∣ n \in ω}

有见证性, 我们有

T

的可数模型

{c_{n}}

. 显然这个模型省略了每个

p_{i}

.

$□$

我们来讨论理论的一种重要性质, 它允许我们用简单的无量词句子代替复杂的可能带量词的任意句子.

定义 2.8.0.30. 我们称理论 $T$ 具有量词消去, 若对任意公式 $ψ (\overset{x}{ˉ})$ 均有无量词公式 $φ (\overset{x}{ˉ})$ 满足 $T ⊨ \forall \overset{x}{ˉ} (ψ (\overset{x}{ˉ} \leftrightarrow φ (\overset{x}{ˉ})))$ .

量词消去的显著好处是初等性变得更容易满足了.

定理 2.8.0.31. 考虑量词消去的理论 $T$ 的两个模型 $M, N$ .

1.	任何嵌入 $f : M \to N$ 都是初等嵌入.
2.	$M$ 是 $N$ 的子结构时, $M$ 也是 $N$ 的初等子结构.

证明. 这是因为前者的无量词版本现在推出后者的任意版本.

$□$

我们现在给出判断一个理论是否具有量词消去的判据. 首先, 我们需要将上一节的工具移植过来.

定义 2.8.0.32 (无量词型). 对语言 $L$ 的结构 $M$ 中的一个有限有序元素组 $\overset{a}{ˉ} = (a_{1}, ..., a_{n})$ , 我们定义其无量词型为 $qftp^{M} (\overset{a}{ˉ}) = {ϕ (x_{1}, ..., x_{n})$ 无量词 $∣ M ⊨ ψ (a_{1}, ..., a_{n})}$ .

类似定义理论的无量词完全型与无量词部分型, 以及带有定义集 $A$ 的无量词型等等. 无量词完全 $n$ 型构成的空间记为 $S_{n}^{q f}$ .

定理 2.8.0.33. 给定两个 $L$ 结构 $M$ 与 $N$ , 指定两个 $n$ 元组 $\overset{a}{ˉ} \in M^{n}$ 和 $\overset{ˉ}{b} \in N^{n}$ , 则 $qftp^{M} (\overset{a}{ˉ}) = qftp^{N} (\overset{ˉ}{b})$ 当且仅当存在同构 $f :< \overset{a}{ˉ} >_{M} \to< \overset{ˉ}{b}_{N} >$ , 使得 $f (a_{i}) = b_{i}$ .

证明. 这里的 $< \overset{a}{ˉ} >_{M}$ 指的是 $\overset{a}{ˉ}$ 作为 $M$ 的子集时生成的子结构, 不难观察到它事实上就是全体 $n$ 变元项 $t$ 实现在 $\overset{a}{ˉ}$ 上后获得的所有 $t (\overset{a}{ˉ}) \in M$ 构成的集.

无量词型相等时, 记 $p = qftp^{M} (\overset{a}{ˉ}) = qftp^{N} (\overset{ˉ}{b})$ , 则 $f : t (\overset{a}{ˉ}) \mapsto t (\overset{ˉ}{b})$ 就是我们想要的同构, 这是因为:

1.	$t^{M} (\overset{a}{ˉ}) = s^{M} (\overset{a}{ˉ}) \leftrightarrow (t = s) \in p \leftrightarrow t^{N} (\overset{ˉ}{b}) = s^{N} (\overset{ˉ}{b})$
2.	$R^{M} (t_{1}^{M} (\overset{a}{ˉ}), ..., t_{m}^{M} (\overset{a}{ˉ})) \leftrightarrow R (t_{1}, ..., t_{m}) \in p \leftrightarrow R^{N} (t_{1}^{N} (\overset{ˉ}{b}), ..., t_{m}^{N} (\overset{ˉ}{b}))$

存在同构时, 由于考虑的是无量词型,

A =< \overset{a}{ˉ} >_{M}

是子结构足以论断

qftp^{M} (\overset{a}{ˉ}) = qftp^{A} (\overset{a}{ˉ})

, 因此只需要论证

qftp^{A} (\overset{a}{ˉ}) = qftp^{B} (\overset{ˉ}{b})

, 而这由同构

f : A \to B

显然地保证了.

$□$

现在我们给出量词消去判据.

定理 2.8.0.34. 对理论 $T$ , 以下两个论断等价.

1.	$T$ 具有量词消去.
2.	任给 $T$ 两个模型 $M, N$ 中的 $n$ 元组 $\overset{a}{ˉ}, \overset{ˉ}{b}$ 均有 $qftp^{M} (\overset{a}{ˉ}) = qftp^{N} (\overset{ˉ}{b}) \to tp^{M} (\overset{a}{ˉ}) = tp^{N} (\overset{ˉ}{b})$

证明. 我们来考虑一个典范的 $π_{q f} : S_{n} (T) \to S_{n}^{q f} (T)$ , 它将 $tp (\overset{x}{ˉ})$ 送到 $qftp (\overset{x}{ˉ})$ . 我们现在来证明以下链条: $T$ 量词消去 $\to$ 判据 $\to π_{q f}$ 是同胚 $\to T$ 量词消去.

对于第一个 $\to$ , 我们其实有加强版本.

断言. 任给量词消去理论 $T$ 的两个模型 $M, N$ 中的 $n$ 元组 $\overset{a}{ˉ}, \overset{ˉ}{b}$ , 均有 $qftp^{M} (\overset{a}{ˉ}) = qftp^{N} (\overset{ˉ}{b}) \leftrightarrow tp^{M} (\overset{a}{ˉ}) = tp^{N} (\overset{ˉ}{b})$

证明. 一边是简单的, 另一边用量词消去的无量词公式来传递等价性.

$□$

对第二个 $\to$ , 我们只需证明 $π_{q f}$ 是双射, 紧致 $T_{2}$ 空间之间的连续双射自然是同胚. 满射是因为 $qftp$ 也可以解读为部分型, 单射就是条件.

对第三个

\to

, 把公式变成

S_{n}

的开闭集, 无量词公式变成

S_{n}^{q f}

的开闭集, 同胚给出与公式等价的无量词公式.

$□$

量词消去有一个弱化的版本.

定义 2.8.0.35 (模型完全).

名字空间

视图

2.8. 型与量词消去