[科普中國(guó)]-緊致性定理

緊致性定理是符號(hào)邏輯和模型論中的基本事實(shí)，它斷言一階句子的（可能無限的）集合是可滿足的（就是說有一個(gè)模型），當(dāng)且僅當(dāng)它的所有有限子集是可滿足的。命題演算的緊致性定理是吉洪諾夫定理（它聲稱緊致空間的積是緊致的）應(yīng)用于緊致Stone空間的結(jié)果。

定義緊致性定理定義1：

1）在一階邏輯中，如果我們有一個(gè)公式集合（記作） 并且 是一個(gè)不滿足式的公式集合，那么 至少有一個(gè)有限個(gè)數(shù)元素的子集（記作） （ ）并且 也是不滿足式的集合

2) 注意到，如果有一個(gè)公式集合（記作） 并且 是一個(gè)可滿足式的公式集合，那么對(duì)于所有 有限個(gè)數(shù)元素的子集（記作） ( ) , 也是可滿足式的集合

3)也就是，前提假設(shè)我們有一個(gè)子句（Clause）集合（記作）S，并且S中的所有子句是封閉的（Clause Fermee，也就是說子句中不含有變量），如果S是不可滿足式的子句集合，當(dāng)且僅當(dāng)S至少有一個(gè)子集合S'，S'是有限集合并且S'是不可滿足的集合

在3)中，我們把公式集合 轉(zhuǎn)化成子句集合S，（根據(jù)定理： ）， 的可滿足性和轉(zhuǎn)化成的子句集合S的可滿足性是等價(jià)的。

證明我們對(duì)1)的證明如下： 在證明前，我們需要知道如下定義：

a)完備性（Completude）****定理的定義：前提假設(shè)我們有一個(gè)有限個(gè)數(shù)元素的子句集合（記作）S并且S中不含有變量（符號(hào)），如果S是不可滿足的集合，那么S必定擁有一個(gè)駁斥（Refutation）。

b)駁斥（Refutation）的定義：一個(gè)子句集合S的駁斥是一個(gè)通過應(yīng)用衍生方法產(chǎn)生的一系列子句 并且最后的 是一個(gè)空子句，我們叫做S擁有（或接受）一個(gè)駁斥，記作 。

注意到當(dāng)S擁有一個(gè)駁斥時(shí)，那么很顯然集合S是有限的，產(chǎn)生的子句 也是有限的，這是因?yàn)槲覀儾荒茉龠\(yùn)用衍生規(guī)則產(chǎn)生其它新的子句

c) 衍生（Derivation）的定義：從一個(gè)子句集合S,通過應(yīng)用解決規(guī)則（regle de resolution）或因式分解規(guī)則（regle de factorisation）產(chǎn)生得到的一系列子句 叫做衍生

d) 正確性（Correction）定理的定義：前提S是一個(gè)不含變量符號(hào)的子句集合，如果子句C是子句集合S通過應(yīng)用解決規(guī)則或因式分解規(guī)則所的到的子句，那幺子句C是子句集合S的邏輯子序列（Consequence Logique），記作，也就是說集合S的所有模型（或稱解釋，指派）也是子句C的模型

e) 邏輯子序列（Consequence Logique）的定義：一個(gè)公式（或公式集合）是另一個(gè)公式（或公式集合）的邏輯子序列，當(dāng)且僅當(dāng)所有的模型（或稱解釋，指派）是的模型，記做

證明：

根據(jù)完備性定理我們可以知道子句集合S擁有一個(gè)駁斥，那么對(duì)應(yīng)的集合也擁有駁斥，那么這兩個(gè)集合都是有限的，所以一個(gè)S的子集合S'在衍生駁斥中也是有限的，我們根據(jù)正確性定理可以知道，通過應(yīng)用衍生規(guī)則,S'也是不可滿足的，那么很顯然存在對(duì)應(yīng)于S'的公式集合（）來說，由于含有以子句形式的集合S',那么集合必定是不可滿足的2。

應(yīng)用從這個(gè)定理可以得出，如果某個(gè)一階句子對(duì)于特征值為零的所有域都成立，則存在著一個(gè)常量p，使得這個(gè)句子對(duì)特征值大于p的所有域都成立。這可以被看作為如下：假定S是要考慮的句子。那么它的否定~S，和域公理與句子的無限序列1+1 ≠ 0, 1+1+1 ≠ 0, ...一起，不能被假定所滿足。所以這些句子的有限子集是不可滿足的，意味著S在有足夠大特征值的這些域中成立。

從這個(gè)定理還得出，有一個(gè)無限模型的任何理論都有任意大基數(shù)的模型。所以，有著帶有不可數(shù)多個(gè)自然數(shù)的皮亞諾算術(shù)有非標(biāo)準(zhǔn)模型。非標(biāo)準(zhǔn)分析是出現(xiàn)無限個(gè)自然數(shù)的另一個(gè)例子，是不能被任何公理化所排除的可能事物，也是緊致性定理的一個(gè)推論3。

緊致性定理也可用于探討一些數(shù)學(xué)命題間的和諧性、獨(dú)立性問題，例如可以用它證明數(shù)論中一些待解問題相對(duì)于自然數(shù)一階理論的一些較弱子理論的和諧性或獨(dú)立性。

本詞條內(nèi)容貢獻(xiàn)者為:

孫和軍 - 副教授 - 南京理工大學(xué)