紧致性定理

紧致性定理是符号逻辑和模型论中的基本事实，它断言一阶句子的（可能无限的）集合是可满足的（就是说有一个模型），当且仅当它的所有有限子集是可满足的。

命题演算的紧致性定理是吉洪诺夫定理（它声称紧致空间的积是紧致的）应用于紧致Stone空间的结果。

应用

从这个定理可以得出，如果某个一阶句子对于特征值为零的所有域都成立，则存在着一个常量p，使得这个句子对特征值大于p的所有域都成立。这可以被看作为如下：假定S是要考虑的句子。那么它的否定~S，和域公理与句子的无限序列1+1 ≠ 0, 1+1+1 ≠ 0, ...一起，不能被假定所满足。所以这些句子的有限子集是不可满足的，意味着S在有足够大特征值的这些域中成立。

从这个定理还得出，有一个无限模型的任何理论都有任意大基数的模型。所以，有着带有不可数多个自然数的皮亚诺算术有非标准模型。非标准分析是出现无限个自然数的另一个例子，是不能被任何公理化所排除的可能事物，也是紧致性定理的一个推论。

证明

紧致性定理可以使用哥德尔完备性定理来证明，它确立了一组句子是可满足的，当且仅当没有矛盾可以证明自它们。事实上，紧致性定理等价于哥得尔完备性定理，并且二者都等价于超滤子引理，它是弱形式的选择公理。因为证明总是有限的，所以只涉及有限多个给定句子，就得出了紧致性定理。

哥德尔最初就是以这种方式证明紧致性定理的，但是后来又找到了紧致性定理的一些“纯语义”证明，就是说提及“真理”但不提及“可证明性”的证明。这些证明倚赖于依仗选择公理的超乘积：

证明：固定一个一阶语言L，并设Σ为L-句子的搜集，使得所有L-句子的子搜集i ⊆ Σ都有模型${\mathcal {M}}_{i}$。还设$\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}$是这些结构的直接乘积，和I是Σ的有限子集的搜集。对于I中每个i设A_i := { j ∈ I : j ⊇ i}。所有这些集合A_i的家族形成一个滤子（filter），所以有一个超滤子（ultrafilter）U包含形如A_i的所有集合。

现在对于Σ中任何公式φ我们有：

• 集合A_{φ}在U中
• 只要j ∈ A_{φ}，则φ ∈ j，因此φ在${\mathcal {M}}_{j}$中成立
• 带有φ在${\mathcal {M}}_{j}$中成立的性质的所有j的集合是A_{φ}的超集，因此也在U中

使用Łoś定理我们看到φ在超乘积$\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U$中成立。所以这个超乘积满足Σ中所有的公式。

紧致性定理（版本2）

紧致性定理的定义

紧致性定理定义：

1）在一阶逻辑中，如果我们有一个公式集合（记作）$\Delta$并且$\Delta$是一个不满足式的公式集合，那么$\Delta$至少有一个有限个数元素的子集（记作）$\Delta ^{\prime }$（$\Delta ^{\prime }\subseteq \Delta$）并且$\Delta ^{\prime }$也是不满足式的集合

我们注意到：

2)（换一句话说），如果我们有一个公式集合（记作）$\Delta$并且$\Delta$是一个可满足式的公式集合，那么对于所有$\Delta$有限个数元素的子集（记作）$\Delta ^{\prime }$ ($\Delta ^{\prime }\subseteq \Delta$) , $\Delta ^{\prime }$也是可满足式的集合

3)（换一句话说），前提假设我们有一个子句（Clause）集合（记作）S，并且S中的所有子句是封闭的（Clause Fermee，也就是说子句中不含有变量），如果S是不可满足式的子句集合，当且仅当S至少有一个子集合S'，S'是有限集合并且S'是不可满足的集合

我们注意到：

在3)中我们把公式集合$\Delta$转化成子句集合S，（根据定理：$\Delta SAT\Leftrightarrow Clause(\Delta )SAT$），我们说$\Delta$的可满足性和转化成的子句集合S的可满足性是等价的

紧致性定理的证明

我们对1)的证明如下： 在证明前，我们需要知道如下定义：

a)完备性（Completude）定理的定义：前提假设我们有一个有限个数元素的子句集合（记作）S并且S中不含有变量（符号），如果S是不可满足的集合，那么S必定拥有一个驳斥（Refutation）

b)驳斥（Refutation）的定义：一个子句集合S的驳斥是一个通过应用派生方法产生的一系列子句$C_{1},C_{2},......C_{n}$并且最后的$C_{n}$是一个空子句，我们叫做S拥有（或接受）一个驳斥，记作$S\vdash \Box$

我们注意到当S拥有一个驳斥时，那么很显然集合S是有限的，产生的子句$C_{1},C_{2},......C_{n}$也是有限的，这是因为我们不能再运用派生规则产生其它新的子句

c)派生（Derivation）的定义：从一个子句集合S,通过应用解决规则（regle de resolution）或因式分解规则（regle de factorisation）产生得到的一系列子句$C_{1},C_{2},......C_{n}$叫做派生

d)正确性（Correction）定理的定义：前提S是一个不含变量符号的子句集合，如果子句C是子句集合S通过应用解决规则或因式分解规则所的到的子句，那么子句C是子句集合S的逻辑子序列（Consequence Logique），记作$S\models C$，也就是说集合S的所有模型（或称解释，指派）也是子句C的模型

e)逻辑子序列（Consequence Logique）的定义：一个公式（或公式集合）$\phi$是另一个公式（或公式集合）$\psi$的逻辑子序列，当且仅当所有$\psi$的模型（或称解释，指派）是$\phi$的模型，记做$\psi \models \phi$

证明：

根据完备性定理我们可以知道子句集合S拥有一个驳斥，那么对应的集合$\Delta$也拥有驳斥，那么这两个集合都是有限的，所以一个S的子集合S'在派生驳斥中也是有限的，我们根据正确性定理可以知道，通过应用派生规则,S'也是不可满足的，那么很显然存在对应于S'的公式集合$\Delta ^{'}$（$\Delta ^{'}\subseteq \Delta$）来说，由于$\Delta$含有以子句形式的集合S',那么集合$\Delta ^{'}$必定是不可满足的

$\Box$

参见

• 布尔代数主题列表
• 哥德尔完备性定理
• Löwenheim-Skolem定理