緊緻性定理
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目沒有列出任何參考或來源。 (2020年5月24日) |
緊緻性定理是符號邏輯和模型論中的基本事實,它斷言一階句子的(可能無限的)集合是可滿足的(就是說有一個模型),若且唯若它的所有有限子集是可滿足的。
命題演算的緊緻性定理是吉洪諾夫定理(它聲稱緊緻空間的積是緊緻的)應用於緊緻Stone空間的結果。
應用
[編輯]從這個定理可以得出,如果某個一階句子對於特徵值為零的所有域都成立,則存在著一個常數p,使得這個句子對特徵值大於p的所有域都成立。這可以被看作為如下:假定S是要考慮的句子。那麼它的否定~S,和域公理與句子的無限序列1+1 ≠ 0, 1+1+1 ≠ 0, ...一起,不能被假定所滿足。所以這些句子的有限子集是不可滿足的,意味著S在有足夠大特徵值的這些域中成立。
從這個定理還得出,有一個無限模型的任何理論都有任意大基數的模型。所以,有著帶有不可數多個自然數的皮亞諾算術有非標準模型。非標準分析是出現無限個自然數的另一個例子,是不能被任何公理化所排除的可能事物,也是緊緻性定理的一個推論。
證明
[編輯]緊緻性定理可以使用哥德爾完備性定理來證明,它確立了一組句子是可滿足的,若且唯若沒有矛盾可以證明自它們。事實上,緊緻性定理等價於哥得爾完備性定理,並且二者都等價於超濾子引理,它是弱形式的選擇公理。因為證明總是有限的,所以只涉及有限多個給定句子,就得出了緊緻性定理。
哥德爾最初就是以這種方式證明緊緻性定理的,但是後來又找到了緊緻性定理的一些「純語意」證明,就是說提及「真理」但不提及「可證明性」的證明。這些證明倚賴於依仗選擇公理的超乘積:
證明:固定一個一階語言L,並設Σ為L-句子的搜集,使得所有L-句子的子搜集i ⊆ Σ都有模型。還設是這些結構的直接乘積,和I是Σ的有限子集的搜集。對於I中每個i設Ai := { j ∈ I : j ⊇ i}。所有這些集合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',那麼集合必定是不可滿足的
參見
[編輯]
|