緊緻性定理

緊緻性定理是符號邏輯和模型論中的基本事實,它斷言一階句子的(可能無限的)集合是可滿足的(就是說有一個模型),若且唯若它的所有有限子集是可滿足的。命題演算的緊緻性定理是吉洪諾夫定理(它聲稱緊緻空間的積是緊緻的)套用於緊緻Stone空間的結果。

定義

緊緻性定理定義 :

緊緻性定理 緊緻性定理
緊緻性定理 緊緻性定理
緊緻性定理 緊緻性定理
緊緻性定理 緊緻性定理
緊緻性定理 緊緻性定理
緊緻性定理 緊緻性定理

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',那么集合必定是不可滿足的 。

套用

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

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

緊緻性定理也可用於探討一些數學命題間的和諧性、獨立性問題,例如可以用它證明數論中一些待解問題相對於自然數一階理論的一些較弱子理論的和諧性或獨立性。

相關詞條

相關搜尋

熱門詞條

聯絡我們