緊緻性定理

若可滿足一族一階句子的任意有限條,則可全部滿足

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

命題演算的緊緻性定理是吉洪諾夫定理(它聲稱緊緻空間的積是緊緻的)應用於緊緻Stone空間的結果。

應用

編輯

從這個定理可以得出,如果某個一階句子對於特徵值為零的所有都成立,則存在着一個常數p,使得這個句子對特徵值大於p的所有域都成立。這可以被看作為如下:假定S是要考慮的句子。那麼它的否定~S,和域公理與句子的無限序列1+1 ≠ 0, 1+1+1 ≠ 0, ...一起,不能被假定所滿足。所以這些句子的有限子集是不可滿足的,意味着S在有足夠大特徵值的這些域中成立。

從這個定理還得出,有一個無限模型的任何理論都有任意大基數的模型。所以,有着帶有不可數多個自然數的皮亞諾算術有非標準模型。非標準分析是出現無限個自然數的另一個例子,是不能被任何公理化所排除的可能事物,也是緊緻性定理的一個推論。

證明

編輯

緊緻性定理可以使用哥德爾完備性定理來證明,它確立了一組句子是可滿足的,當且僅當沒有矛盾可以證明自它們。事實上,緊緻性定理等價於哥得爾完備性定理,並且二者都等價於超濾子引理,它是弱形式的選擇公理。因為證明總是有限的,所以只涉及有限多個給定句子,就得出了緊緻性定理。

哥德爾最初就是以這種方式證明緊緻性定理的,但是後來又找到了緊緻性定理的一些「純語意」證明,就是說提及「真理」但不提及「可證明性」的證明。這些證明倚賴於依仗選擇公理的超乘積

證明:固定一個一階語言L,並設Σ為L-句子的搜集,使得所有L-句子的子搜集i ⊆ Σ都有模型 。還設 是這些結構的直接乘積,和I是Σ的有限子集的搜集。對於I中每個i設Ai := { jI : ji}。所有這些集合Ai的家族形成一個濾子(filter),所以有一個超濾子(ultrafilter)U包含形如Ai的所有集合。

現在對於Σ中任何公式φ我們有:

  • 集合A{φ}U
  • 只要j ∈ A{φ},則φ ∈ j,因此φ在 中成立
  • 帶有φ在 中成立的性質的所有j的集合是A{φ}的超集,因此也在U

使用Łoś定理我們看到φ在超乘積 中成立。所以這個超乘積滿足Σ中所有的公式。

緊緻性定理(版本2)

編輯

緊緻性定理的定義

編輯

緊緻性定理定義:

1)在一階邏輯中,如果我們有一個公式集合(記作) 並且 是一個不滿足式的公式集合,那麼 至少有一個有限個數元素的子集(記作)  )並且 也是不滿足式的集合
我們注意到:
2)(換一句話說),如果我們有一個公式集合(記作) 並且 是一個可滿足式的公式集合,那麼對於所有 有限個數元素的子集(記作)  ( ) ,  也是可滿足式的集合
3)(換一句話說),前提假設我們有一個子句(Clause)集合(記作)S,並且S中的所有子句是封閉的(Clause Fermee,也就是說子句中不含有變數),如果S是不可滿足式的子句集合,當且僅當S至少有一個子集合S',S'是有限集合併且S'是不可滿足的集合
我們注意到:
在3)中我們把公式集合 轉化成子句集合S,(根據定理: ),我們說 的可滿足性和轉化成的子句集合S的可滿足性是等價的

緊緻性定理的證明

編輯

我們對1)的證明如下: 在證明前,我們需要知道如下定義:

a)完備性(Completude)定理的定義:前提假設我們有一個有限個數元素的子句集合(記作)S並且S中不含有變數(符號),如果S是不可滿足的集合,那麼S必定擁有一個駁斥(Refutation)
b)駁斥(Refutation)的定義:一個子句集合S的駁斥是一個通過應用衍生方法產生的一系列子句 並且最後的 是一個空子句,我們叫做S擁有(或接受)一個駁斥,記作 
我們注意到當S擁有一個駁斥時,那麼很顯然集合S是有限的,產生的子句 也是有限的,這是因為我們不能再運用衍生規則產生其它新的子句
c)衍生(Derivation)的定義:從一個子句集合S,通過應用解決規則(regle de resolution)或因式分解規則(regle de factorisation)產生得到的一系列子句 叫做衍生
d)正確性(Correction)定理的定義:前提S是一個不含變數符號的子句集合,如果子句C是子句集合S通過應用解決規則或因式分解規則所的到的子句,那麼子句C是子句集合S的邏輯子序列(Consequence Logique),記作 ,也就是說集合S的所有模型(或稱解釋,指派)也是子句C的模型
e)邏輯子序列(Consequence Logique)的定義:一個公式(或公式集合) 是另一個公式(或公式集合) 的邏輯子序列,當且僅當所有 的模型(或稱解釋,指派)是 的模型,記做 
證明:
根據完備性定理我們可以知道子句集合S擁有一個駁斥,那麼對應的集合 也擁有駁斥,那麼這兩個集合都是有限的,所以一個S的子集合S'在衍生駁斥中也是有限的,我們根據正確性定理可以知道,通過應用衍生規則,S'也是不可滿足的,那麼很顯然存在對應於S'的公式集合  )來說,由於 含有以子句形式的集合S',那麼集合 必定是不可滿足的
 

參見

編輯