緊緻性定理

緊緻性定理是符號邏輯和模型論中的基本事實，它斷言一階句子的（可能無限的）集合是可滿足的（就是說有一個模型），當且僅當它的所有有限子集是可滿足的。

命題演算的緊緻性定理是吉洪諾夫定理（它聲稱緊緻空間的積是緊緻的）應用於緊緻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定理