8. 理论与模型

8.1理论与模型

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

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

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

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

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

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

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

1.	对每个常元符号 $c$, $F(c^{\mathcal{M}})=c^{\mathcal{N}}$
2.	对每个 $n$ 元函数符号 $f$ 与 $M$ 中的 $n$ 个元素 $a_1,a_2,...,a_n$, 都有 $F(f^{\mathcal{M}}(a_1,a_2,...,a_n))=f^{\mathcal{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^{\mathcal{M}}\to (F(a_1),F(a_2),...,F(a_n))\in P^{\mathcal{N}}$

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

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

我们称嵌入 $F:M\to N$ 是初等嵌入, 若对任何的公式 $\phi (x_1,x_2,...,x_n)$ 和 $a_1,a_2,...,a_n\in M$ 都有 $\mathcal{M}\models \phi (a_1,...,a_n)\leftrightarrow \mathcal{N}\models \phi (F(a_1),...,F(a_n))$. 此处记法的合理性由赋值对公式的自由变元决定性保证.

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

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

定理 8.1.2. 一个函数 $F:M\to N$ 是嵌入, 当且仅当对任意的无量词公式 $\phi (x_1,x_2,...,x_n)$ 和 $a_1,a_2,...,a_n\in M$ 都有 $\mathcal{M}\models \phi (a_1,a_2,...,a_n)\leftrightarrow \mathcal{N}\models \phi (F(a_1),F(a_2),...,F(a_n))$.

一个嵌入 $F:M\to N$ 还满足: 对任意的存在公式 $\phi (x_1,x_2,...,x_n)$ 和 $a_1,a_2,...,a_n\in M$ 都有 $\mathcal{M}\models \phi (a_1,...,a_n)\to \mathcal{N}\models \phi (F(a_1),...,F(a_n))$.

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

证明. 先来看第一部分. 嵌入满足这个条件是归纳显然的, 这个条件指出嵌入则只需要对项 $t$ 考虑 $t\approx t$ 这种公式. 第二部分也是传统方法, 把 " 满足存在公式 " 变成一堆 $M$ 里面的实例, 然后将它们映到 $N$ 中.

$\square$

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

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

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

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

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

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

这个证明甚至不需要常数构造法, 直接把 $N-F(M)$ 切下来接在 $M$ 旁边就可以了.

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

定义 8.1.7 (理论与模型). 假定我们有指定的语言 $\mathcal{L}$.

对于句子集 $\Sigma$, 若结构 $\mathcal{M}$ 满足 $\forall \sigma \in \Sigma \mathcal{M}\models \sigma$, 则称 $\mathcal{M}$ 是 $\Sigma$ 的一个模型, 记为 $\mathcal{M}\models \Sigma$.

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

如果句子集 $\Sigma$ 对蕴含封闭, 换言之对任何句子 $\sigma$ 都有 $\Sigma \models \sigma \to \sigma \in \Sigma$, 就称 $\Sigma$ 是一个 $\mathcal{L}$ 理论, 简称理论.

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

对任何一个结构 $\mathcal{M}$, 定义这个结构的理论为 $\mathrm{Th}(\mathcal{M})=\{\sigma |\mathcal{M}\models \sigma \}$, 它显然是个一致完备的理论.

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

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

如果有一族结构 $\mathcal{K}=\{\mathcal{M}|\mathcal{M}\models \Sigma \}$, 其中 $\Sigma$ 是个理论, 则称这一族结构形成一个初等类.

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

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

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

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

$\square$

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

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

全体一阶逻辑的句子 $S_0$ 与通常定义的满足关系 $T_0(\mathcal{M},\varphi )\leftrightarrow \mathcal{M}\models \varphi$ 构成一阶逻辑 $L_{\omega \omega }=(S_0,T_0)$.

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

8.2超积

这一节对最常用的构造模型的方法做论述.

定义 8.2.1 (滤与超滤). 集合 $X$ 上的滤 $\mathcal{F}$ 是一个 $\mathcal{P}(X)$ 的子集, 满足以下要求:

1.	$\varnothing \notin \mathcal{F}$, $X\in \mathcal{F}$
2.	$A\in \mathcal{F}\wedge A\subseteq B\to b\in \mathcal{F}$
3.	$A\in \mathcal{F}\wedge B\in \mathcal{F}\to A\cap B\in \mathcal{F}$

称一个滤为极大滤, 若不存在真包含它的滤; 称一个滤为超滤, 若它满足 $\forall A\subseteq X(A\in \mathcal{F}\vee X\backslash A\in \mathcal{F})$.

定理 8.2.2. 超滤和极大滤等价.

证明. 由于 $A\cap (X\backslash A)=\varnothing$, 这两个集至多有一个在滤中.

$\square$

定理 8.2.3 (滤子存在定理). 任给一个 $F\subseteq \mathcal{P}(X)$, 存在滤子 $\mathcal{F}$ 包含 $F$ 当且仅当 $F$ 具有有限交性质, 即
$\forall X_1,...,X_n\in F(X_1\cap ...\cap X_n\ne \varnothing )$

证明. 仅当是显然的, 下面考虑当的方向. 我们逐步扩充 $F$, 直到它成为一个滤: 令 $F_0=F$, $F_{2n+1}=\{{\cap }_{k\in m}{A}_k|m\in \mathbb{N},A_k\in F_{2n}\}$, $F_{2n+2}=\{B\subseteq X|\exists A\in F_{2n+1}(A\subseteq B)\}$, $n\in \mathbb{N}$. 令 $\mathcal{F}={\bigcup }_{n\in \mathbb{N}}{F}_n$, 它是一个滤子.

$\square$

定理 8.2.4 (超滤扩张定理). 在 ZFC 中, 任何滤都被一个超滤包含.

证明. 我们使用 Zorn 引理, 考虑全体包含这个滤的滤们在包含关系下所成的偏序集. 注意一列相互包含的滤的并仍然是滤, 而极大滤就是超滤.

$\square$

直观上, 超滤给出了 $X$ 上一些很大的子集; 与之相反的, 也可以定义理想, 它将给出一些很小的子集. 这两个定义都可以拓展到格上, 而有的格又和布尔环有关系, 所以这个理想并不是和环的理想完全无关, 有兴趣的读者可以参考格论著作来补齐中间的过程. 然而实分析与格论完全没有关系, 所以此书忍痛割去相关内容.

定义 8.2.5 (超积). 给定一族 $\mathcal{L}$ 结构 $\{M_i|i\in I\}$ 和 $I$ 上的一个超滤 $\mathcal{U}$, 我们定义这些结构的超积 $M={\prod }_{i\in I}^{/\mathcal{U}}{M}_i$ 为商结构 ${\prod }_{i\in I}{M}_i/{\sim }_{\mathcal{U}}$, 等价关系如下定义:

$s{\sim }_{\mathcal{U}}t\leftrightarrow \{i\in I|s(i)\approx t(i)\}\in \mathcal{U}$.

验证它是个结构是很无聊的工作, 我们直接留给比较闲的读者. 注意, 这个等价关系可以当成是 “在 $\mathcal{U}$ 的意义下这两个东西 “几乎处处” 相等”.

超积好就好在它保持了这些结构的性质. 具体而言, 我们有

定理 8.2.6 (Los 超积定理). 任给公式 $\varphi (x_1,...,x_n)$, 记超积 $M={\prod }_{i\in I}^{/\mathcal{U}}{M}_i$, 给定一些 $s_1,...,s_n\in {\prod }_{i\in I}{M}_i$, 则

$M\models \varphi ([s_1{]}_{\sim },....,[s_n{]}_{\sim })\leftrightarrow \{i\in I|M_i\models \varphi (s_1(i),...,s_n(i))\}\in \mathcal{U}$

证明. 对公式 $\varphi$ 的结构进行归纳, 细节是枯燥的.

$\square$

超积的这一性质给与它广阔的应用空间. 例如,

定理 8.2.7 (紧致性定理). 一个有限一致的句子集 $\Sigma$ 是一致的.

证明. 我们不妨设它是一个理论, 然后枚举它的有限子集 $\{{\Sigma }_i|i\in I\}$, 给每个 ${\Sigma }_i$ 找一个模型 $M_i$, 然后对每个 $\sigma \in \Sigma$ 考虑 $X_{\sigma }=\{i\in I|{\Sigma }_i\models \sigma \}$. 它们显然有有限交性质, 于是有一个超滤 $\mathcal{U}$ 包含全体 $X_{\sigma }$, 把所有 $M_i$ 关于这个超滤作超积, 所得的结构恰好就是 $\Sigma$ 的模型.

$\square$

注 8.2.8. 如果先按第一章的方式证明完备性再证紧致性, 或者化用那一思想直接证明, 总是要用 Henkin 方法加入常元再提取常元, 不如此法简便.

它可以用来在一般的模型论中刻画类似于 HSP 定理的定理.

定理 8.2.9. $\mathcal{K}$ 是初等类当且仅当它关于初等等价和取超积封闭.

证明. 显然初等类关于初等等价封闭, 而 Los 定理也指出它对取超积封闭, 所以接下来只证另一个方向.

假定有一模型 $\mathcal{M}\models T$, 其中 $T=\{\sigma |\mathcal{N}\in \mathcal{K}\to \mathcal{N}\models \sigma \}$ 是我们这个对初等等价和取超积封闭的类 $\mathcal{K}$ 的理论, 我们要证明 $\mathcal{M}\in \mathcal{K}$.

我们令 $\Sigma =\mathrm{Th}(\mathcal{M})$ 是这个模型的理论, 然后枚举 $\Sigma$ 的全体有限子集 $\{{\Sigma }_i|i\in I\}$.

引理 8.2.10. 对每个 $i\in I$ 均存在 ${\mathcal{M}}_i\in \mathcal{K}$ 满足 $\mathcal{M}\models {\Sigma }_i$.

证明. 否则, 存在 ${\Sigma }_i=\{{\sigma }_j\}$ 使得 $\forall \mathcal{N}\in \mathcal{K}(\mathcal{N}\models {\bigvee }_j(\neg {\sigma }_j))$, 于是 ${\bigvee }_j(\neg {\sigma }_j)$ 与 $\neg ({\bigvee }_j(\neg {\sigma }_j))={\bigwedge }_j{\sigma }_j$ 都在 $T$ 中, 显然矛盾.

$\square$

于是, 仿照我们上面对紧致性定理的证明, 存在一个 $I$ 上的超滤 $\mathcal{U}$ 使得 ${\prod }_{i\in I}^{/\mathcal{U}}{\mathcal{M}}_i\models \Sigma$, 换言之 $\mathcal{M}\equiv {\prod }_{i\in I}^{/\mathcal{U}}{\mathcal{M}}_i$, 于是 $\mathcal{K}$ 的封闭性给出 $\mathcal{M}\in \mathcal{K}$.

$\square$

它还可以用来更深刻地刻画初等等价.

定理 8.2.11 (Keisler-Shelah). $\mathcal{M}$ 和 $\mathcal{N}$ 初等等价当且仅当存在集合 $I$ 和其上的一个超滤 $\mathcal{U}$, 使得 ${\mathcal{M}}^I/{\sim }_{\mathcal{U}}$ 与 ${\mathcal{N}}^I/{\sim }_{\mathcal{U}}$ 同构.

这一定理的证明远超出此书能承受的范围, 我们遗憾的省略它.

8.3Lowenheim-Skolem 定理

这一节, 我们介绍这个由紧致性定理引出的最重要的定理. 它指出, 一阶逻辑不可能限制无穷模型的基数.

定理 8.3.1 (下行 Lowenheim-Skolem 定理). 我们称语言 $\mathcal{L}$ 的全体句子构成的集合的基数为这个语言的基数, 记为 $|\mathcal{L}|$.

假定我们有论域为 $M$ 的结构 $\mathcal{M}$, 任给 $A\subseteq M$, 均存在 $N\subseteq M$ 使得 $N\supseteq A$, $N\prec M$ 且 $|N|\le \max \{|A|,|\mathcal{L}|,{\aleph }_0\}$.

证明. 我们需要一些判定初等子结构的定理.

定理 8.3.2 (Tarski-Vaught 测试). 若 $M$ 是 $N$ 的子结构, 则 $M\prec N\leftrightarrow$ 对每个公式 $\phi (x_1,...,x_n,y)$ 以及 $a_1,...,a_n\in M$ 均有 $\mathcal{N}\models \exists y(\phi (a_1,...,a_n,y))\to \mathcal{M}\models \exists y(\phi (a_1,...,a_n,y))$.

注 8.3.3. 换言之, 子结构是初等子结构当且仅当它保留了所有存在公式的证据.

证明. 初等子结构满足此式是显然的, 我们反过来在此式的条件下证明对每个公式 $\varphi (x_1,...,x_m)$ 和 $b_1,...,b_m\in M$ 均有 $\mathcal{M}\models \varphi (b_1,...,b_m)\leftrightarrow \mathcal{N}\models \varphi (b_1,...,b_m)$.

对公式的结构归纳, 无量词和逻辑连接词显然, 而对应于存在量化的情况我们的假定给出了原本不能推出的方向.

$\square$

但是这还不够方便. 我们来考察可定义性如下:

定义 8.3.4. 设有 $\mathcal{L}$ 的结构 $\mathcal{M}$.

1.	对于 $X\subseteq M^n$, 若存在公式 $\phi (x_1,...,x_n,y_1,...,y_m)$ 和 $b_1,...,b_m\in M$ 使得 $X=\{(a_1,...,a_n)\in M^n|\mathcal{M}\models \phi (a_1,...,a_n,b_1,...,b_n)\}$, 则称 $\phi$ 和 $(b_1,...,b_m)$ 定义了 $X$, 简称为 $X$ 是可定义集.
2.	对于可定义集 $X$, 若 $b_1,...,b_m\in A\subseteq M$, 则可额外称 $X$ 定义在 $A$ 上, 或 $X$ 是 $A$ 可定义集. 原本的可定义集也因此可以称作 $M$ 可定义集.

现在, 我们有另一个对初等子结构的描述.

定理 8.3.5 (Tarski 测试). 若 $A\subseteq M$ 是非空子集, 则 $A\prec M$ 当且仅当每个非空的 $A$ 可定义集 $X\subseteq M$ 与 $A$ 的交集均非空.

证明. 先证明 $A$ 是子结构, 再证明它初等. 引用 Tarski-Vaught 测试.

$\square$

我们构造所需的 $N$, 然后运用 Tarski 测试来验证 $N\prec M$. 对于集合 $A\subseteq M$, 我们记语言 ${\mathcal{L}}_A$ 为原本的语言加上全体 $a\in A$ 作为常元所得到的新语言.

令 $A_0=A$, 我们归纳地定义一列 $A_n$, 然后令 $N={\bigcup }_{n\in \omega }{A}_n$. 若 $A_n$ 已经构造好, 则至多有 $|A_n|+|\mathcal{L}|+{\aleph }_0$ 个 ${\mathcal{L}}_{A_n}$ 公式, 故 $M$ 的非空 $A_n$ 可定义集也至多这么多个. 我们把它们收集起来得到 $P_n$, 然后做选择函数 $f_n:P_n\to M$, 令 $A_{n+1}=A_n\cup f_n(P_n)$. 这个归纳的过程已经给出 $|A_{n+1}|\le \max \{|A_n|,|\mathcal{L},{\aleph }_0|\}$, 因此 $|A_n|\le \max \{|A|,\mathcal{L},{\aleph }_0\}$, 进而 $|N|\le \max \{|A|,\mathcal{L},{\aleph }_0\}$.

考虑 $X\subseteq M$ 是非空的 $N$ 可定义子集. 由于定义 $X$ 用到的参数 $b_i$ 只有有限个, 必然有一个 $A_n$ 包含了全体这些参数, 因此 $X\cap N\supseteq X\cap A_{n+1}\ni f_n(X)$ 不空.

$\square$

这指出, 我们可以随意给出更小基数的初等子结构. 另一方面, 我们也可以随意给出更大基数的初等扩张 (即使得原模型成为其初等子结构的模型).

定理 8.3.6 (上行 Lowenheim-Skolem 定理). 假定我们有语言 $\mathcal{L}$ 的无穷模型 $\mathcal{M}$, 则对任意的基数 $\kappa \le |M|+|\mathcal{L}|$ 均存在基数为 $\kappa$ 的 $\mathcal{M}$ 的初等扩张 $\mathcal{N}$. 这里结构的基数就指的是论域的基数.

证明. 引入常元 $\{c_i|i\in \kappa \}$, 我们向语言 $\mathcal{L}$ 中加入全体 $M$ 中的元素作为常元, 得到语言 ${\mathcal{L}}_M$, 再加入 $\{c_i\}$ 们作为常元符号得到 ${\mathcal{L}}^{\prime }$. 为了构造一个理论, 使得这理论的模型都是 $\mathcal{M}$ 的初等扩张, 我们引入以下定义.

定义 8.3.7 (图). 对 $\mathcal{L}$ 结构 $\mathcal{M}$, 我们称以下 ${\mathcal{L}}_M$ 句子集为 $\mathcal{M}$ 的基本图:

$\mathrm{Diag}(\mathcal{M})=\{\varphi (a_1,...,a_n)|\varphi$ 是 $n$ 自由变元的 $\mathcal{L}$ 无量词公式, 且 $a_i\in \mathcal{M},\mathcal{M}\models \varphi (a_1,...,a_n)\}$

称以下 ${\mathcal{L}}_M$ 句子集为 $\mathcal{M}$ 的初等图:

$\mathrm{Dia}{\mathrm{g}}_{\mathrm{el}}(\mathcal{M})=\{\varphi (a_1,...,a_n)|\varphi$ 是 $n$ 自由变元的 $\mathcal{L}$ 公式, 且 $a_i\in \mathcal{M},\mathcal{M}\models \varphi (a_1,...,a_n)\}$

注 8.3.8. 为了将 $\mathcal{M}$ 满足的一切公式变成句子, 我们必须加入全体论域中的元素作为常元. 今后我们不会经常区分一个句子究竟在哪个语言中, 请读者自行甄别.

定理 8.3.9. 若 ${\mathcal{L}}_M$ 结构 $\mathcal{N}$ 满足 $\mathcal{N}\models \mathrm{Diag}(\mathcal{M})$, 则存在 $\mathcal{M}$ 到 $\mathcal{N}$ 的嵌入. 如果 $\mathcal{N}\models \mathrm{Dia}{\mathrm{g}}_{\mathrm{el}}(\mathcal{M})$, 则存在 $\mathcal{M}$ 到 $\mathcal{N}$ 的初等嵌入.

证明. 显然把 $\mathcal{N}$ 的常元映射当成嵌入即可.

$\square$

因此, 为了的得到 $\mathcal{M}$ 的基数 $\kappa$ 的初等扩张, 我们来考虑 ${\mathcal{L}}^{\prime }$ 句子集 $\Sigma =\mathrm{Dia}{\mathrm{g}}_{\mathrm{el}}(\mathcal{M})\cup \{c_i\ne c_j|i\ne j\in \kappa \}$. 由于 $M$ 是无穷集合, 这个 $\Sigma$ 是有限一致的, 因此存在其模型 $\mathcal{N}$, 显然忘记其上的多余结构就给出作为 $\mathcal{L}$ 结构的 $\mathcal{M}$ 的初等扩张.

$\square$

这两个定理合称 Lowenheim-Skolem 定理.

推论 8.3.10. 若 $\mathcal{L}$ 的一个理论 $T$ 拥有一个无穷模型, 则对任意基数 $\kappa \le |\mathcal{L}|$ 均存在基数 $\kappa$ 的 $T$ 的模型.

证明. 对原来的无穷模型做初等扩张或取初等子模型, 把基数控制得恰好是 $\kappa$ 即可.

$\square$

值得注意的是, 无穷模型不能换成有穷模型. 事实上, 我们有以下定理.

定理 8.3.11. 若 $\mathcal{L}$ 有有限结构 $\mathcal{M}$, 则 $\mathcal{M}$ 的每个初等扩张和初等子模型都与 $\mathcal{M}$ 同构.

证明. 假定 $|M|=m$, 我们只需要考虑命题 ${\exists }^{=m}x$, 也就是$$\exists x_1...\exists x_m((\underset{i\ne j}{\bigwedge }{x}_i\ne x_j)\wedge \forall x(\underset{i}{\bigvee }(x=x_i)))$$

$\square$

Lowenheim-Skolem 定理还给出另一个重要定理.

定理 8.3.12 (初等融贯定理). 若两结构 $M_1\equiv M_2$, 则存在结构 $N$ 和两个初等嵌入 $g_i:M_i\to N(i=1,2)$.

证明. 不妨设 $M_1\cap M_2=\varnothing$, 我们考虑 ${\mathcal{L}}^{\prime }={\mathcal{L}}_{M_1\cup M_2}$. 只需证明 $\mathrm{Dia}{\mathrm{g}}_{\mathrm{el}}({\mathcal{M}}_1)\cup \mathrm{Dia}{\mathrm{g}}_{\mathrm{el}}({\mathcal{M}}_2)$ 是有限一致的句子集, 则其模型即为所需的 $\mathcal{N}$.

事实上, 从其中选出有限个句子, 我们将同一个初等图中的句子用且合并为一个句子, 就成了两个句子 $\varphi (a_1,...,a_n)\in {\mathcal{L}}_{M_1}$ 与 $\psi (b_1,...,b_m)\in {\mathcal{L}}_{M_2}$. 注意 ${\mathcal{M}}_1\models \varphi$ 而 ${\mathcal{M}}_2\models \psi (b_1,...,b_m)$, 后者正是 ${\mathcal{M}}_2\models \exists b_1\exists ...\exists b_m(\psi (b_1,...,b_m))$, 初等等价指出 ${\mathcal{M}}_1$ 同样满足右侧式子, 于是我们就得到了 $b_1^{\prime },...,b_m^{\prime }\in {\mathcal{M}}_1$. 现在将 ${\mathcal{M}}_1$ 解释为 ${\mathcal{L}}^{\prime }$ 结构即可.

$\square$

8.4型

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

定义 8.4.1 (有序元素组的型). 对语言 $\mathcal{L}$ 的结构 $\mathcal{M}$ 中的一个有限有序元素组 $\bar{a}=(a_1,...,a_n)$, 我们定义其型为 ${\mathrm{tp}}^{\mathcal{M}}(\bar{a})=\{\varphi (x_1,...,x_n)|\mathcal{M}\models \psi (a_1,...,a_n)\}$.

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

定义 8.4.3 (理论的完全型). 对语言 $\mathcal{L}$ 的理论 $T$, 一个公式集 $\Sigma$ 若满足存在模型 $\mathcal{M}$ 和其中的有限有序元素组 $(a_1,..。,a_n)$ 使得 $\Sigma ={\mathrm{tp}}^{\mathcal{M}}(\bar{a})$, 则称 $\Sigma$ 是理论 $T$ 的完全 $n$ 型, 全体完全 $n$ 型的集记为 $S_n(T)$.

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

定义 8.4.4 (实现与省略). 对语言 $\mathcal{L}$ 中的一族 $n$ 自由变元句子集 ${\Sigma }_n$, 若结构 $\mathcal{M}$ 中存在一个有限有序元素组 $\bar{a}=(a_1,...,a_n)$ 使得 $\forall \varphi \in {\Sigma }_n(\mathcal{M}\models \varphi (\bar{a}))$, 则称 $\bar{a}$ 在 $\mathcal{M}$ 中实现了 ${\Sigma }_n$, 有时也称作 $\mathcal{M}$ 实现了 ${\Sigma }_n$. 如果不存在实现 ${\Sigma }_n$ 的 $\bar{a}$, 则称 $\mathcal{M}$ 省略了 ${\Sigma }_n$.

这诱导出以下想法.

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

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

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

证明. 第一个由定义是显然的; 第二个考虑 $\mathrm{tp}$ 的定义也是显然的.

$\square$

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

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

证明. 假设 $\Sigma$ 想成为部分 $n$ 型, 在语言 $\mathcal{L}$ 中加入 $n$ 个新常元 $\bar{c}$, 然后考虑理论 $T\cup \{\varphi (\bar{c})|\varphi \in \Sigma \}$, 对这个理论的模型用紧致性定理即可.

$\square$

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

定理 8.4.8. 如果有完备理论 $T$ 的模型 $\mathcal{M}$, 则:

1.	$\Sigma$ 是部分型, 当且仅当它的每个有限子集都在 $\mathcal{M}$ 中被实现.
2.	$S_n(T)=\{{\mathrm{tp}}^{\mathcal{N}}(\bar{a})|\mathcal{M}\prec \mathcal{N}\wedge a_1,...,a_n\in \mathcal{N}\}$

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

对第二个, 其实只要证明每个部分型都在一个 $\mathcal{N}\succ \mathcal{M}$ 中被实现. 这是因为如果它在一个 ${\mathcal{M}}^{\prime }$ 中被实现, 我们用初等融贯把 $\mathcal{M}$ 和 ${\mathcal{M}}^{\prime }$ 融贯为一个 $\mathcal{N}$, 就可以得到它在 $\mathcal{N}$ 中被实现的证据.

$\square$

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

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

定理 8.4.10. $S_n(T)$ 是紧致 $T_2$ 完全不连通零维空间, 开闭基就是这些 $[\{\varphi \}]$.

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

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

定理 8.4.12. $\mathcal{T}$ 是紧致 $T_2$ 完全不连通零维空间, 开闭基就是这些 $[\{\sigma \}]$.

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

定义 8.4.13. 对 $\mathcal{L}$ 结构 $\mathcal{M}$, 给定 $A\subseteq M$ 和 $X\subseteq M^n$, 我们可以定义 $X$ 的 $A$ 可定义子集的集族为 ${\mathrm{Def}}_A(X)=\{Y\subseteq X|\exists \varphi (\bar{x},\bar{y})\exists \bar{b}\in A^m(Y=\{\bar{a}\in X|\varphi (\bar{a},\bar{b})\})\}$. 我们更细致地称公式 $\varphi$ 与参数 $\bar{b}$ 在 $X$ 上定义了 $Y$.

对 $A\subseteq M$, 我们定义其可定义闭包为 ${\mathrm{dcl}}_M(A)=\{b\in M|\{b\}\in {\mathrm{Def}}_A(M)\}$, 定义其代数闭包为 ${\mathrm{acl}}_M(A)=\{b\in M|\exists S\in {\mathrm{Def}}_A(M)(b\in S\wedge |S|<\omega )\}$.

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

定理 8.4.14. ${\mathrm{dcl}}_M({\mathrm{dcl}}_M(A))={\mathrm{dcl}}_M(A)$, ${\mathrm{acl}}_M({\mathrm{acl}}_M(A))={\mathrm{acl}}_M(A)$

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

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

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

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

虽然 $acl$ 并不总是满足 $\mathrm{span}$ 的条件, 但有限性和一个长得很像交换性的性质合在一块可以用单调和单增推出幂等.

引理 8.4.16. 如果一个 $C:\mathcal{P}(X)\to \mathcal{P}(X)$ 是有限、单调、单增的, 且满足 $\forall S\subseteq X\forall a,b\in X(a\in C(S)\wedge 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)$.

$\square$

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

类似地可以验证 $dc{l}_M$ 的性质.

$\square$

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

定理 8.4.17. 如果 $\mathcal{N}\prec \mathcal{M}$, 且 $A\subseteq N\subseteq M$, 则 ${\mathrm{dcl}}_N(A)={\mathrm{dcl}}_M(A)$, ${\mathrm{acl}}_N(A)={\mathrm{acl}}_M(A)$.

证明. 这是因为在语言 ${\mathcal{L}}_A$ 中仍然有 $\mathcal{N}\prec \mathcal{M}$, 而这指出 $phi$ 在 $\mathcal{N}$ 中与在 $\mathcal{M}$ 中定义出相同的对象.

$\square$

推论 8.4.18. 若 $\mathcal{N}\prec \mathcal{M}$, 则 ${\mathrm{dcl}}_M(N)={\mathrm{acl}}_M(N)=N$.

现在回到对型的处理上.

定义 8.4.19. 对指标集 $I$ 和语言 $\mathcal{L}$ 的结构 $\mathcal{M}$ 中的一个以 $I$ 为指标的元素组 $A=\{a_i|i\in I\}\subseteq X$, 我们定义其型为 ${\mathrm{tp}}^{\mathcal{M}}(A)=\{\varphi (x_{i_1},...,x_{i_n})|\mathcal{M}\models \psi (a_{i_1},...,a_{i_n}),i_j\in I,a_{i_j}\in A\}$.

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

对语言 $\mathcal{L}$ 的结构 $\mathcal{M}$ 中的一个有限有序元素组 $\bar{a}=(a_1,...,a_n)$ 和子集 $B\subseteq M$, 我们定义其型为 ${\mathrm{tp}}_B^{\mathcal{M}}(\bar{a})=\{\varphi (x_1,...,x_n)|\mathcal{M}\models \psi (a_1,...,a_n)\}$, 这里 $\varphi$ 是加入了全体 $B$ 中元素为常元的语言 ${\mathcal{L}}_B$ 的公式.

其余定义同理.

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

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

由于 ${\mathrm{Th}}_A(M)$ 自动的是完备一致理论, 我们同 $S_n(T)$ 一样有以下这些结果.

定理 8.4.21. 以下定理对 $S_n^{\mathcal{M}}(A)$ 同样成立.

1.	$S_n^{\mathcal{M}}(A)=\{{\mathrm{tp}}_A^{\mathcal{N}}(\bar{b})|\mathcal{M}\prec \mathcal{N},\bar{b}\in N^n\}$
2.	${\mathcal{L}}_A$ 公式集是部分型, 当且仅当它的每个有限子集都在 $\mathcal{M}$ 中被实现, 当且仅当它是一个完全型的子集. 完全型是极大部分型.
3.	$S_n(A)$ 是一个紧致 $T_2$ 完全不连通零维空间.

证明. 显然.

$\square$

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

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

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

主的意思是必须存在.

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

证明. 这是因为 $p$ 有限可满足, 从而 $\varphi$ 必须被满足, 这又指出 $p$ 被实现.

$\square$

类似地, 我们也可以定义完备理论的主型. 仍然固定一个可数语言 $\mathcal{L}$ 上的完备理论 $T$.

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

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

证明. 对任何 $T$ 的模型 $\mathcal{M}$, 显然有 $S_n(T)=S_n^{\mathcal{M}}(\varnothing )$.

$\square$

我们的目标是以下定理.

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

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

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

我们用这列 $c_i$ 来讨论 $T^{\prime }$ 的见证性.

定义 8.4.27. 称 ${\mathcal{L}}^{\prime }$ 的理论 $T^{\prime }$ 对常元组 $\{c_n|n\in \omega \}$ 具有见证性, 若对每个公式 $\varphi (x)$, $T^{\prime }\models \exists x(\varphi (x))$ 时均有一个 $i\in \omega$ 使得 $T^{\prime }\models \varphi (c_i)$.

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

证明.

$\square$

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

引理 8.4.29. ${\pi }_{\sigma }$ 是连续函数, 且将开闭集映为开闭集.

证明.

$\square$

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

引理 8.4.30. 对非主型 $p\in S_n(T)$, 存在余第一纲集 $V_p\subseteq S$ 使得对每个 $T^{\prime }\in V_p$, 此时的任何 $\sigma \in {\omega }^n$ 均让 $p$ 不被 $\{c_{\sigma (i)}|i\in n\}$ 实现.

证明.

$\square$

最后, 这个定理的证明水到渠成. 第一个引理给出一个余第一纲集 $W$, 第三个引理对每个 $p_i$ 给出一个余第一纲集 $V_i$, Baire 纲定理指出它们全部交起来不空, 因此不妨假定其中有一个理论 $T^{\prime }$. 由于它对 $\{c_n|n\in \omega \}$ 有见证性, 我们有 $T$ 的可数模型 $\{c_n\}$. 显然这个模型省略了每个 $p_i$.

$\square$