向上Löwenheim-Skolem定理

在數理邏輯中，經典 **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_{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_ 的函數，使得

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

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

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

　
: $\exists y_{1}\ \cdots \ \exists y_{m}R(y_{1},\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 (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