紧致性定理

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

命题演算的紧致性定理是 吉洪诺夫定理(它声称紧致空间的积是紧致的)应用于紧致 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^'$ ($\Delta^' \subseteq \Delta$) 并且 $\Delta^'$ 也是不满足式的集合

我们注意到:

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

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定理