勒文海姆–斯科倫定理

在數理邏輯中，經典勒文海姆–斯科倫定理（Löwenheim–Skolem theorem）聲稱對於標識（signature）為 ${\displaystyle <\mathbf {C} ,\mathbf {F} ,\mathbf {R} ,\sigma >}$ 的任何可數一階邏輯語言 L 和 L-結構 M，存在一個可數無限基本子結構 N ${\displaystyle \subseteq }$ M。 這個定理的自然和有用的推論是所有一致的 L-理論都有可數的模型。

這裏的標識由常量集合 ${\displaystyle \mathbf {C} }$、函數集合 ${\displaystyle \mathbf {F} }$、關係符號集合 ${\displaystyle \mathbf {R} }$、和表示函數和關係符號的元數的函數 ${\displaystyle \sigma :\mathbf {F} \cup \mathbf {R} \rightarrow \mathbb {N} }$ 組成。在這個上下文中 L-結構，由底層集合(經常指示為「M」)和 L 的函數和關係符號的釋義組成。L 的常量在 M 中的釋義就是 M 的成員。類似的，${\displaystyle \sigma (f)\ }$-元函數 ${\displaystyle f\in \mathbf {F} }$ 被指派為 M 中的 ${\displaystyle \sigma (f)\ }$-元函數 ${\displaystyle M^{\sigma (f)}\rightarrow M}$ 的圖，而${\displaystyle \sigma (R)\ }$-元關係 ${\displaystyle R\in \mathbf {R} }$ 的釋義被指派為 M 中的 ${\displaystyle \sigma (R)\ }$-元關係。語言 L 是可數的，如果在 L 中的常量、函數和關係符號是可數的。

例子

一個周知的不可數模型是所有實數的集合，帶有次序關係 "<" 作為唯一的關係，和加法與乘法作為函數。有序域的公理是一階句子；最小上界公理不是一階的而是二階的。這個定理蘊涵了實數域的某個可數無限的子域，因此不同於實數域，但滿足了實數域所滿足的所有一階句子。(作為可數的有序域，它不能滿足最小上界公理)。例如，特定多項式方程有解(在這個模型中)的斷言是一階句子，因此在斷言了其存在的可數子模型中是真的，若且唯若它在實數域中是真的。

數學家考慮的多數數學結構，特別是多數範疇的多數成員，是這裏定義意義上的模型。勒文海姆–斯科倫定理告訴我們如果它們是不可數的，它們不能被任何一階句子的集合唯一性的選取出來。

證明梗概

對於在模型 M 中為真的如下形式的一階句子

${\displaystyle \forall x\ \exists y\ R(x,y)}$

或

${\displaystyle \forall x_{1}\ \cdots \ \forall x_{n}\ \exists y_{1}\ \cdots \ \exists y_{m}R(x_{1},\dots ,x_{n},y_{1},\dots ,y_{m})}$

有一個Skolem 函數 f，就是說映射 x 到斷言了其存在的 y 的函數，使得

${\displaystyle \forall x\ R(x,f(x))}$

在 M 中為真。因為有很多這樣的 y 的值，必須啟用選擇公理來推出 Skolem 函數的存在。

這個模型的某些成員可以直接用一階公式來定義，就是說，它們的存在被如下形式的句子所斷言

${\displaystyle \exists y_{1}\ \cdots \ \exists y_{m}R(y_{1},\dots ,y_{m})}$

並且因為只有可數多個一階公式，只有可數多個成員可以用這種方式直接定義。

證明的想法是: 開始於這個模型的所有一階可定義成員的集合，並接着在所有 Skolem 函數下閉合它。這個閉包必定最多是可數無限的。這個模型的子集是這個定理斷言了其存在的子模型。

更一般的 "勒文海姆–斯科倫定理"

上述定理假定了有限或可數無限的語言。更一般的勒文海姆–斯科倫定理做其他有關基數的假定。類似於這個經典定理的某些定理，斷言更小的子模型的存在(「向下」勒文海姆–斯科倫定理)；其他一些斷言更大基數的模型的存在(「向上」勒文海姆–斯科倫定理)。

勒文海姆-斯科倫定理在一階邏輯中的定義和證明

勒文海姆-斯科倫定理: 如果 ${\displaystyle \Delta }$ 是一個含有有限可數個數的命題組成的集合，並且集合 ${\displaystyle \Delta }$ 是可以滿足的(${\displaystyle \Delta }$ SAT),那麼至少存在一個模型(或叫作指派，或叫作解釋 (Interpretation)) 用符號記作 I, ${\displaystyle I\models \Delta }$ ,且這個模型 I 指派解釋也是可數的

證明:

前提:在語言集合L中如果我們有一個可滿足式的有限可數命題公式的集合 ${\displaystyle \Delta }$，且${\displaystyle \phi \in \Delta }$,${\displaystyle \phi }$是${\displaystyle \Delta }$中的命題公式

如果我們有一個集合，用字母記作 S ,並且 ${\displaystyle S=\bigcup _{\phi \in \Delta }CL(\phi )}$，其中集合 ${\displaystyle CL(\phi )}$是由命題公式${\displaystyle \phi }$轉換成子句結構(Clause)所組成的集合，我們有一個定理(記作Th): 如果${\displaystyle \psi }$是可滿足式的(Satisfaisable)公式，若且唯若Clause(${\displaystyle \psi }$)也是可滿足式的，通過這個定理，我們確保S是可滿足的，並且也是可數的

如果我們有一個基於語言集合L的等價公理集合，記作${\displaystyle E_{=}}$(該集合是為了用於Skolemisation方法中,也就是${\displaystyle \phi }$在轉化成Clause(${\displaystyle \phi }$)過程中，去除有限量詞${\displaystyle \exists }$的方法Skolemisation,化為Skolem範式)

那麼很顯然 ${\displaystyle S\bigcup E_{=}}$ 也是可滿式的集合，那麼 ${\displaystyle IF(S\bigcup E_{=})}$ 同樣是可滿足的

由於語言集合L中的元素是可數的 所以${\displaystyle IF(S\bigcup E_{=})}$ 是也是有限可數的集合

如果我們有一個模型，記作 I 且 ${\displaystyle I\models IF(S\bigcup E_{=})}$,赫爾不蘭特定理(Theoreme de Herbrand)告訴我們如果我們要構造一個模型M,並且${\displaystyle M\models S\bigcup E_{=}}$，那麼模型M的模型解釋指派域(記作)D是一個以I(t)為元素的指派域(其中t是在S中的所有的項)，那麼模型M是通過Congurence關係來解釋指派等價性關係(Egalite)

由於我們說語言理合L是可數的，那麼指派解釋域D也是可數的

那麼我們可以構造另一個模型M'，並且基於解釋域 ${\displaystyle D/M_{=}}$(我們通過等價關係來指派解釋等價性)且${\displaystyle M'\models S}$,那麼M'必然也是可數的，那麼根據Th定理，${\displaystyle M'\models S}$ ,那麼我們就可以說 ${\displaystyle M'\models \Delta }$

所以我們證明了勒文海姆-斯科倫定理

參見

• Skolem悖論
• 模型論

引用

• Wilfrid Hodges (1997), "A Shorter Model Theory", Cambridge University Press, ISBN 0521587131
• María Manzano (1999), "Model Theory", Oxford University Press, ISBN 0198538510
• Rothmaler, Philipp (2000), "Introduction To Model Theory", CRC