查看“︁紧致性定理”︁的源代码

{{unreferenced|time=2020-05-24}}
{{NoteTA
|G1 = IT
|G2 = Math
}}
'''紧致性定理'''是[[数理逻辑|符号逻辑]]和[[模型论]]中的基本事实，它断言[[一阶逻辑|一阶]]句子的（可能[[无限集合|无限]]的）集合是可满足的（就是说有一个[[模型论|模型]]），[[当且仅当]]它的所有有限[[子集]]是可满足的。

[[命题演算]]的紧致性定理是[[吉洪诺夫定理]]（它声称[[紧致空间]]的积是紧致的）应用于紧致[[Stone布爾代數表示定理|Stone空间]]的结果。

== 应用 ==

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

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

== 证明 ==

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

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

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

现在对于Σ中任何公式φ我们有：
* 集合A<sub>{φ}</sub>在''U''中
* 只要''j'' ∈ A<sub>{φ}</sub>，则φ ∈ ''j''，因此φ在<math>\mathcal M_j</math>中成立
* 带有φ在<math>\mathcal M_j</math>中成立的性质的所有''j''的集合是A<sub>{φ}</sub>的超集，因此也在''U''中
使用[[超乘积|Łoś定理]]我们看到φ在超乘积<math>\prod_{i \subseteq \Sigma}\mathcal{M}_i/U</math>中成立。所以这个超乘积满足Σ中所有的公式。

==紧致性定理（版本2）==

===紧致性定理的定义===
紧致性定理定义：
:1）在一阶逻辑中，如果我们有一个公式集合（记作）<math> \Delta </math>并且<math> \Delta </math>是一个'''不满足式的'''公式集合，那么<math> \Delta </math>至少有一个有限个数元素的子集（记作）<math> \Delta^\prime </math>（<math> \Delta^\prime \subseteq \Delta  </math>）并且<math> \Delta^\prime </math>也是不满足式的集合
:我们注意到：
:2)（换一句话说），如果我们有一个公式集合（记作）<math> \Delta </math>并且<math> \Delta </math>是一个'''可满足式的'''公式集合，那么对于所有<math> \Delta </math>有限个数元素的子集（记作）<math> \Delta^\prime </math> (<math> \Delta^\prime \subseteq \Delta  </math>) , <math> \Delta^\prime </math>也是可满足式的集合
:3)（换一句话说），前提假设我们有一个子句（Clause）集合（记作）S，并且S中的所有子句是'''封闭的'''（Clause Fermee，也就是说子句中不含有变量），如果S是不可满足式的子句集合，当且仅当S至少有一个子集合S'，S'是有限集合并且S'是不可满足的集合
:我们注意到：
:在3)中我们把公式集合<math> \Delta </math>转化成子句集合S，（根据定理：<math> \Delta SAT \Leftrightarrow Clause(\Delta) SAT</math>），我们说<math> \Delta </math>的可满足性和转化成的子句集合S的可满足性是'''等价的'''

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

:a)完备性（Completude）定理的定义：前提假设我们有一个有限个数元素的子句集合（记作）S并且S中不含有变量（符号），如果S是不可满足的集合，那么S必定拥有一个驳斥（Refutation）
:b)驳斥（Refutation）的定义：一个子句集合S的驳斥是一个通过应用衍生方法产生的一系列子句<math> C_1,C_2,......C_n</math>并且最后的<math>C_n</math>是一个空子句，我们叫做S拥有（或接受）一个驳斥，记作<math>S \vdash \Box </math>
:我们注意到当S拥有一个驳斥时，那么很显然集合S是有限的，产生的子句<math> C_1,C_2,......C_n</math>也是有限的，这是因为我们不能再运用衍生规则产生其它新的子句
:c)衍生（Derivation）的定义：从一个子句集合S,通过应用解决规则（regle de resolution）或因式分解规则（regle de factorisation）产生得到的一系列子句<math>C_1,C_2,......C_n</math>叫做衍生
:d)正确性（Correction）定理的定义：前提S是一个不含变量符号的子句集合，如果子句C是子句集合S通过应用解决规则或因式分解规则所的到的子句，那么子句C是子句集合S的逻辑子序列（Consequence Logique），记作<math> S \models C </math>，也就是说集合S的所有模型（或称解释，指派）也是子句C的模型
:e)逻辑子序列（Consequence Logique）的定义：一个公式（或公式集合）<math>\phi</math>是另一个公式（或公式集合）<math> \psi </math>的逻辑子序列，当且仅当所有<math> \psi </math>的模型（或称解释，指派）是<math>\phi</math>的模型，记做<math>\psi \models \phi</math>

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

==参见==
* [[布尔代数主题列表]]
* [[哥德尔完备性定理]]
* [[Löwenheim-Skolem定理]]

{{数理逻辑}}

[[Category:模型论]]
[[Category:数学定理|J]]