紧致性定理

我们证明逆否命题:若 $\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$ 有模型。