模型论

这令人惊讶:$\Sigma$ 可以是无限的,甚至编码了无穷多条约束,但一致性却只需一次检查有限多条约束。这是从有限的证明(形式推导永远是有限对象)通往无限的语义(模型可以是无限的)的桥梁,也是整个模型论中唯一负责无限模型与非标准模型存在性的定理。

我们证明逆否命题:若 $\Sigma$ 没有模型,则存在有限的 $\Sigma_0 \subseteq \Sigma$ 没有模型。

假设 $\Sigma$ 不可满足。由一阶逻辑的哥德尔完备性定理(语义蕴含与语法可推导性一致:$\Sigma \models \bot$ 当且仅当 $\Sigma \vdash \bot$),$\Sigma$ 不可满足等价于 $\Sigma$ 在语法上不一致,即 $\Sigma \vdash \bot$——从 $\Sigma$ 可以形式地推出矛盾。

按定义,形式推导是一个有限的公式序列,每一步都由一条公理、$\Sigma$ 中的一个前提,或作用于之前行的一条推理规则来证成。由于 $\bot$ 的推导是有限的,它只引用了 $\Sigma$ 中有限多个前提;把它们收集为有限集合 $\Sigma_0 = \{\sigma_1, \dots, \sigma_n\} \subseteq \Sigma$。

仅使用 $\Sigma_0$ 中前提的这同一个有限推导,见证了 $\Sigma_0 \vdash \bot$。由一阶逻辑的可靠性(可推导性蕴含语义蕴含),$\Sigma_0 \models \bot$,即 $\Sigma_0$ 不可满足——它没有模型。

于是我们构造出了一个没有模型的有限 $\Sigma_0 \subseteq \Sigma$,证明了逆否命题。等价地说:若 $\Sigma$ 的每个有限子集都有模型,就不可能存在这样不一致的有限推导,所以 $\Sigma$ 不可能不可满足,因此 $\Sigma$ 有模型。

这说明一阶逻辑无法确定基数:任何具有无限模型的理论(例如域的公理、集合论的公理……)都已经拥有一个可数模型,无论原始模型被构造得多“大”。结合向上版本(任意无限模型都有任意更大基数的初等扩张),这正是斯科伦悖论的根源——一个可数结构可以满足与一个不可数结构完全相同的一阶语句,甚至包括那些从内部“断言”不可数性的语句。

我们把 $N$ 构造为 $M$ 的一列可数递增子集的并,使用塔斯基–沃特判别法:子集 $N \subseteq M$(作为子结构)是初等的,当且仅当对每个 $\mathcal{L}$-公式 $\psi(x, \bar{y})$ 与 $N$ 中每个元组 $\bar{a}$,若存在某个 $b \in M$ 使 $\mathcal{M} \models \psi(b, \bar{a})$,则已经存在这样的见证 $b \in N$。

由于 $\mathcal{L}$ 可数,公式 $\psi(x,\bar y)$ 只有可数多个。从任意可数无穷的 $X_0 \subseteq M$ 出发(因 $M$ 无限故可行)。给定可数的 $X_n$,对每个公式 $\psi(x,\bar y)$ 与 $X_n$ 中的每个元组 $\bar a$(仍只有可数多对,因为 $X_n$ 可数且 $\mathcal{L}$ 可数),若 $\exists b \in M\, \mathcal{M} \models \psi(b,\bar a)$,则(用选择公理)选取一个这样的见证 $b$ 并加入以构成 $X_{n+1}$;这只增加了可数多个新元素,故 $X_{n+1}$ 仍是可数的。

设 $N = \bigcup_{n<\omega} X_n$;可数个可数集之并,故 $N$ 可数(且无限,因 $X_0 \subseteq N$)。我们对 $N$ 验证塔斯基–沃特判别法:给定 $\psi(x,\bar y)$ 与 $N$ 中的 $\bar a$,因 $\bar a$ 是有限元组,它整个落在某个 $X_n$ 中(该链是递增的);若存在见证 $b \in M$ 使 $\psi(b, \bar a)$ 成立,则由 $X_{n+1}$ 的构造,某个见证已被选取并放入 $X_{n+1} \subseteq N$。

由塔斯基–沃特判别法,$N$(带有诱导的 $\mathcal{L}$-结构 $\mathcal{N}$)满足 $\mathcal{N} \preceq \mathcal{M}$。初等子结构与母结构满足完全相同的语句,故 $\mathcal{N}$ 是见证该定理的可数无穷模型。