-
緊緻性定理
鎖定
- 中文名
- 緊緻性定理
- 外文名
- Compactness theorem
- 適用領域
- 符號邏輯;模型論
- 應用學科
- 數學
緊緻性定理定義
1)在一階邏輯中,如果我們有一個公式集合(記作)
並且
是一個不滿足式的公式集合,那麼
至少有一個有限個數元素的子集(記作)
(
)並且
也是不滿足式的集合
2) 注意到,如果有一個公式集合(記作)
並且
是一個可滿足式的公式集合,那麼對於所有
有限個數元素的子集(記作)
(
) ,
也是可滿足式的集合
3)也就是,前提假設我們有一個子句(Clause)集合(記作)S,並且S中的所有子句是封閉的(Clause Fermee,也就是説子句中不含有變量),如果S是不可滿足式的子句集合,當且僅當S至少有一個子集合S',S'是有限集合並且S'是不可滿足的集合
在3)中,我們把公式集合
轉化成子句集合S,(根據定理:
),
的可滿足性和轉化成的子句集合S的可滿足性是等價的。
緊緻性定理證明
我們對1)的證明如下: 在證明前,我們需要知道如下定義:
a)完備性(Completude)定理的定義:前提假設我們有一個有限個數元素的子句集合(記作)S並且S中不含有變量(符號),如果S是不可滿足的集合,那麼S必定擁有一個駁斥(Refutation)。
注意到當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',那麼集合
必定是不可滿足的
[2]
。
緊緻性定理應用
從這個定理可以得出,如果某個一階句子對於特徵值為零的所有域都成立,則存在着一個常量p,使得這個句子對特徵值大於p的所有域都成立。這可以被看作為如下:假定S是要考慮的句子。那麼它的否定~S,和域公理與句子的無限序列1+1 ≠ 0, 1+1+1 ≠ 0, ...一起,不能被假定所滿足。所以這些句子的有限子集是不可滿足的,意味着S在有足夠大特徵值的這些域中成立。
從這個定理還得出,有一個無限模型的任何理論都有任意大基數的模型。所以,有着帶有不可數多個自然數的皮亞諾算術有非標準模型。非標準分析是出現無限個自然數的另一個例子,是不能被任何公理化所排除的可能事物,也是緊緻性定理的一個推論
[3]
。
緊緻性定理也可用於探討一些數學命題間的和諧性、獨立性問題,例如可以用它證明數論中一些待解問題相對於自然數一階理論的一些較弱子理論的和諧性或獨立性。
- 參考資料
-
- 1. [1]緊緻性定理 .中國百姓網[引用日期2016-12-12]
- 2. [2]呂義忠. 緊緻性定理的純語義證明[J]. 南京大學學報(自然科學版),1989,04:573-576.
- 3. [3]萬展翔,陳國龍. 緊緻性定理在羣論中的應用[J]. 洛陽師範學院學報,2014,02:4-5.
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:12次歷史版本
- 最近更新: 本命年本命年44