勒文海姆–斯科倫定理

佇數理邏輯內底，經典Löwenheim–Skolem 定理這聲稱對標識 ( signature ) 為 $ < \ mathbf { C } , \ mathbf { F } , \ mathbf { R } , \ sigma > $ 的任何會當數一階邏輯語言 _ L _ 和 _ L _-結構 M，存在一个可數無限基本子結構 _ N _ $ \ subseteq $ _ M _。 這个定理的自然佮有用的推論是所有一致 _ L _-理論攏有可數的模型。

遮的標識由常量集合 $ \ mathbf { C } $、函數集合 $ \ mathbf { F } $、關係符號集合 $ \ mathbf { R } $、和表示函數和關係符號的元數的函數 $ \ sigma : \ mathbf { F } \ cup \ mathbf { R } \ rightarrow \ mathbb { N } $ 組成。佇這个頂下文中 _ L _-結構，由底層集合 ( 定定指示講「_ M _」) 和 _ L _ 的函數和關係符號的釋義組成。_ L _ 的常量佇咧 _ M _ 中的釋義就是講 _ M _ 的成員。類似的，$ \ sigma ( f ) \ $-元函數 $ f \ in \ mathbf { F } $ 予人派做 _ M _ 中的 $ \ sigma ( f ) \ $-元函數 $ M ^ { \ sigma ( f ) } \ rightarrow M $ 的圖，而且 $ \ sigma ( R ) \ $-元關係 $ R \ in \ mathbf { R } $ 的釋義予人派做 _ M _ 中的 $ \ sigma ( R ) \ $-元關係。語言 _ L _ 是可數，若佇咧 _ L _ 嘿的常量、函數佮關係符號是可數的。

例

一个周知的不可數模型是所有實數的集合，帶有次序的關係 " < " 成做唯一的關係，佮加法佮乘法做為函數。有序域的公理是一階句；上細上界公理毋是一階的是二階的。這个定理蘊涵了實數域的某一个可數無限的子域，所以無仝實數，但滿足了實數域所滿足的所有一坎句。( 做為數的順序，伊袂當滿足上細上界公理 )。比如講，特定濟項式方程有解說 ( 佇這个模型內底 ) 的斷言是一坎句，因此咧斷言矣其存在的會當幾若模型中是真的，若是唯若是伊實數內底是真正。

數學家考慮的多數學結構，特別是多數範圍的多數成員，是遮定義意義上的模型。Löwenheim–Skolem 定理共咱講若𪜶是不可數的，𪜶袂使予任何一階句的集合唯一性的選取出來。

證明梗概

著在模型 _ M _ 著了後真正是落形式的一坎句

$ \ forall x \ \ exists y \ R ( x , y ) $

抑是

$ \ forall x _ { 一 } \ \ cdots \ \ forall x _ { n } \ \ exists y _ { 一 } \ \ cdots \ \ exists y _ { m } R ( x _ { 一 } , \ dots , x _ { n } , y _ { 一 } , \ dots , y _ { m } ) $

有一个Skolem 函數_ f _，就是講映射 _ x _ 到斷言矣其存在的 _ y _ 的函數，予得

$ \ forall x \ R ( x , f ( x ) ) $

佇咧 _ M _ 中為真。因為有足濟按呢 _ y _ 的值，著愛啟用選擇公理來推出 Skolem 函數的存在。

這个模型的某一寡成員會當直接用一階公式來定義，就是講乎，𪜶的存在予人如下形式的句句咧斷言

$ \ exists y _ { 一 } \ \ cdots \ \ exists y _ { m } R ( y _ { 一 } , \ dots , y _ { m } ) $

並且因為干焦會當數加一階公式，干焦會當數多个成員會當用這種方式直接定義。

證明的想法是：開始佇這个模型的所有一階會當定義成員的集合，並接著佇咧所有 Skolem 函數落去共伊閉合。這个閉包定上濟是可數無限的。這个模型的子集是這个定理斷言矣其存在的子模型。

閣較一般的 " Löwenheim–Skolem 定理 "

頂頭伊定理假定有限抑是會當無限的語言。閣較一般的 Löwenheim-Skolem 做其他有關基數的假定。類似於這个經典定理的某一寡定理，斷言閣較細的模型的存在 (「向下跤」Löwenheim-Skolem 定理 )；其他一寡斷言閣較大的基數的模型的存在 (「向頂懸」Löwenheim-Skolem 定理 )。

勒文海姆-斯科倫定理佇一階邏輯內底的定義佮證明

勒文海姆-斯科倫定理: 若是 $ \ Delta $ 是一个含有有限可數個數的命題組成的集合，並且集合 $ \ Delta $ 是會當滿足的( $ \ Delta $ SAT ) , 遐爾仔上無存在一个模型 ( 抑是叫做指派，抑是叫做解說 ( Interpretation ) ) 用符號記作I, $ I \ models \ Delta $ , 而且這个模型 I 指派解說嘛是可數的

證明 :

前提：佇語言集合 L 啊如果阮有一个會當滿足式的有限可數命題公式的集合 $ \ Delta $，而且 $ \ phi \ in \ Delta $ , $ \ phi $ 是 $ \ Delta $ 中的命題公式

咱若有一个集合，用字母記作 S , 並且 $ S=\ bigcup _ { \ phi \ in \ Delta } CL ( \ phi ) $，其中集合 $ CL ( \ phi ) $ 是由命題公式 $ \ phi $ 轉做子句結構 ( Clause ) 所組成的集合，阮有一个定理 ( 記作 Th ) : 若是 $ \ psi $ 是會當滿足式的 ( Satisfaisable ) 公式，若是唯一 Clause ( $ \ psi $ ) 嘛是會當滿足式的，通過這个定理，阮確保 S 是會當滿足的，並且嘛會用得數的

咱若是有一个基於語言集合 L 的等價公理集合，記作 $ E _ {=} $ ( 彼个集合是為著用於 Skolemisation 方法內底，也就是講 $ \ phi $ 咧轉化做 Clause ( $ \ phi $ ) 過程當中，去除有限量詞 $ \ exists $ 的方法 Skolemisation , 化為 Skolem 範式 )

遐爾真顯然 $ S \ bigcup E _ {=} $ 嘛是會當滿式的集合，遐爾 $ IF ( S \ bigcup E _ {=} ) $ 平平是會當滿足的

因為語言集合 L 中的元素是可數的所以 $ IF ( S \ bigcup E _ {=} ) $ 是也有限可數的集合

咱若是講咱有一个模型，記作 I 而且 $ I \ models IF ( S \ bigcup E _ {=} ) $ , 赫爾不蘭特定理 ( Theoreme de Herbrand ) 共咱講若是咱想欲構造一个模型 M , 並且 $ M \ models S \ bigcup E _ {=} $，遐爾仔模型 M 的模型解說指派域 ( 記作 ) D 是一个以 I ( t ) 這个元素的指派域 ( 其中 t 是佇咧 S 中的所有的項 )，遐爾仔模型 M 是通過 Congurence 關係來解說指派等等價性關係 ( Egalite )

因為咱講語言理合 L 是可數，遐爾指派解說域 D 嘛是可數

咱會當構造另外一个模型 M'，並且因為解說域 $ D / M _ {=} $ ( 咱通過等價關係來指派解說等價性 ) 而且 $ M'\ models S $ , 遐爾 M'必須嘛是可數的，遐爾仔根據 Th 定理，$ M'\ models S $ , 咱就會當講 $ M'\ models \ Delta $

所以阮證明矣勒文海姆-斯科倫定理

參見

• Skolem 鋪論
• 模型論

引用

• Wilfrid Hodges ( 一千九百九十七 ) , " A Shorter Model Theory " , Cambridge University Press , ISBN 五鋪兩千一百五十八鋪七千一百三十一
• María Manzano ( 一千九百九十九 ) , " Model Theory " , Oxford University Press , ISBN 一鋪九千八百五十三鋪八千五百十
• Rothmaler , Philipp ( 兩千 ) , " Introduction To Model Theory " , CRC