Löwenheim–Skolem の定理 | 数理論理

1 言語と理論の濃度

有限、高々可算、可算、および非可算という用語は、「等濃度と可算性」の§E1.18 定義 1.2に従う。可算かつ無限である集合を可算無限と呼び、高々可算な集合の特徴づけには§E1.18 定理 3.3を用いる。また、選択公理を仮定し、「基数とアレフ」の§E1.21 定理 2.2に従って、任意の集合の濃度を、その集合と等濃な基数によって表す。

$L$ の非論理記号集合の濃度を $|L|$ と書き、

\kappa(L,T)=\max(\aleph_0,|L|,|T|)

とおく。

補題 1.1. 集合サイズの有限項言語 $L$ と任意の理論 $T\subseteq\operatorname{Sent}(L)$ について、

|T|\le\max(\aleph_0,|L|)

である。したがって

\kappa(L,T)=\max(\aleph_0,|L|)

である。

証明.§E16.11 補題 2.1により $|\operatorname{Sent}(L)|\le\max(\aleph_0,|L|)$ である。 $T\subseteq\operatorname{Sent}(L)$ なので同じ上界が $T$ にも成り立つ。 $\kappa(L,T)$ の定義へ代入すると表示した等式を得る。▨

この評価で、各非論理記号の項数が有限であることを用いている。記号が集合個あっても、各文は有限長なので、文全体は記号集合上の有限列全体より多くならない。

2 小さいモデルの存在

定理 2.1. $L$ を集合サイズの有限項言語、 $T\subseteq\operatorname{Sent}(L)$ を充足可能な理論とする。このとき、ある $L$ 構造 $M$ が存在して

M\models T, \qquad |M|\le\kappa(L,T)=\max(\aleph_0,|L|)

となる。

証明. $T$ は充足可能なので、健全性により構文的に無矛盾である。§E16.12 定理 4.1は、無矛盾な $T$ に対して $|M|\le\kappa(L,T)$ を満たす項モデルの還元 $M\models T$ を与える。補題 1.1により $\kappa(L,T)=\max(\aleph_0,|L|)$ である。▨

系 2.2. $L$ が有限または可算であり、 $L$ 理論 $T$ が充足可能なら、 $T$ は有限または可算なモデルをもつ。 $T$ が有限モデルをもたないなら、 $T$ は可算無限モデルをもつ。

証明. $|L|\le\aleph_0$ なので、定理 2.1が与えるモデルの濃度は高々 $\aleph_0$ である。 $T$ が有限モデルをもたない場合、そのモデルは有限ではないため、濃度がちょうど $\aleph_0$ である。▨

注意 2.3 (与えられたモデルとの包含関係は主張しない). $N\models T$ が与えられていても、定理 2.1が構成する $M$ は $N$ の部分構造または初等部分構造であるとは限らない。定理が主張するのは、同じ理論 $T$ を満たす小さいモデルがどこかに存在することである。

3 指定濃度のモデル

次に、無限モデルを一つもつ理論から、指定した濃度ちょうどのモデルを構成する。下界だけを作るのでは不十分である。新定数がモデルの濃度を少なくとも $\lambda$ にし、拡大言語に対する小さいモデルの定理が同じモデルの濃度を高々 $\lambda$ にする。

定理 3.1 (上方 Löwenheim–Skolem の定理). $L$ を集合サイズの有限項言語、 $T\subseteq\operatorname{Sent}(L)$ を無限モデルをもつ理論とする。 $\lambda$ を

\lambda\ge\max(\aleph_0,|L|)

を満たす任意の無限濃度とする。このとき、濃度がちょうど $\lambda$ である $L$ 構造 $M$ が存在して $M\models T$ となる。

証明の方針は、 $\lambda$ 個の新定数をすべて相異なると要求することである。任意の有限個の要求は元の無限モデルで満たすことができる。コンパクト性で全要求を同時に満たし、項モデルの濃度上界で余分に大きいモデルを小さくする。

証明. $I$ を濃度 $\lambda$ の集合とし、 $i\in I$ ごとに新しい定数記号 $c_i$ を加える。拡大言語を

L_\lambda=L\cup\{c_i\mid i\in I\}

とする。§E16.11 系 2.2 (4)により $|L_\lambda|=\lambda$ である。

$L_\lambda$ 理論

\Delta=T\cup\{c_i\ne c_j\mid i,j\in I,\ i\ne j\}

を考える。 $\Delta_0\subseteq_{\mathrm{fin}}\Delta$ を任意に取る。 $\Delta_0$ に現れる新定数は有限個である。固定した無限モデル $N\models T$ の台集合から、その有限個の定数へ相異なる要素を割り当てることができる。残りの新定数には任意の一要素を割り当てる。この $L_\lambda$ 拡大は $\Delta_0\cap T$ と、 $\Delta_0$ に現れるすべての不等式を満たす。したがって $\Delta$ の各有限部分集合は充足可能である。

§E16.13 定理 1.1により $\Delta$ は充足可能である。ここで、コンパクト性が与える任意のモデルをそのまま選ばず、拡大言語 $L_\lambda$ と理論 $\Delta$ に定理 2.1を適用する。

「基数算術」の§E1.22 定義 1.1と§E1.22 系 3.3を無限基数 $\lambda$ に適用すると、

|I\times I|=|I|\cdot|I|=\lambda\cdot\lambda=\lambda

|N_\lambda|\le\max(\aleph_0,|L_\lambda|,|\Delta|)=\lambda

を満たすものを与える。

$N_\lambda\models c_i\ne c_j$ がすべての相異なる $i,j$ について成り立つため、 $i\mapsto c_i^{N_\lambda}$ は $I$ から $|N_\lambda|$ への単射である。したがって $|N_\lambda|\ge\lambda$ である。上下の評価を合わせると $|N_\lambda|=\lambda$ となる。元の言語への還元

M=N_\lambda\mathbin{\upharpoonright}L

は台集合を変えず、 $T$ のすべての文を満たす。ゆえに $M\models T$ かつ $|M|=\lambda$ である。▨

系 3.2. $L$ が有限または可算であり、 $L$ 理論 $T$ が無限モデルを一つもつなら、任意の無限濃度 $\lambda$ について、濃度がちょうど $\lambda$ であるモデル $M\models T$ が存在する。

証明. $|L|\le\aleph_0$ なので、任意の無限濃度 $\lambda$ は $\lambda\ge\max(\aleph_0,|L|)$ を満たす。定理 3.1を適用すればよい。▨

例 3.3 (無限線形順序の濃度). 線形順序の言語は一つの二項関係記号だけをもち、可算である。線形順序の理論は整数の通常の順序を無限モデルとしてもつ。したがって、任意の無限濃度 $\lambda$ について、濃度 $\lambda$ の線形順序が存在する。この結論は線形順序を具体的に定義する方法とは別に、コンパクト性と項モデルの濃度評価から得られる。

4 二つの濃度方向の関係

定理 4.1 (Löwenheim–Skolem のモデル存在形). 集合サイズの有限項言語 $L$ と $L$ 理論 $T$ について、次が成り立つ。

$T$ が充足可能なら、濃度が高々 $\max(\aleph_0,|L|)$ であるモデルが存在する。
$T$ が無限モデルをもつなら、すべての無限濃度 $\lambda\ge\max(\aleph_0,|L|)$ について、濃度がちょうど $\lambda$ であるモデルが存在する。

証明.(1)は定理 2.1であり、(2)は定理 3.1である。▨

注意 4.2 (一階理論は無限濃度を一つに固定することができない). $T$ が無限モデルを一つもち、そのすべてのモデルの濃度が一つの無限濃度 $\kappa$ に等しいと仮定する。選択公理のもとで「基数とアレフ」の§E1.21 定理 2.2を用い、

\mu=\max\{\kappa,|L|,\aleph_0\}

を一つの基数として取る。§E1.21 定理 3.1を集合 $\mu$ に適用する。恒等写像 $\mu\to\mu$ は単射であるから、同定理の第1項により $\mu<\hbar(\mu)$ である。また、同定理の第2項により $\hbar(\mu)$ は基数である。 $\lambda=\hbar(\mu)$ とおけば $\lambda>\max\{\kappa,|L|,\aleph_0\}$ であり、上方 Löwenheim–Skolem の定理が濃度 $\lambda$ のモデルを与え、仮定に反する。したがって、集合サイズの一階理論は、モデルの濃度を一つの無限濃度だけへ固定することができない。

5 扱わない下方定理

与えられた構造 $N$ と部分集合 $A\subseteq|N|$ から、 $A$ を含む小さい初等部分構造 $M\preccurlyeq N$ を構成する形の下方 Löwenheim–Skolem の定理には、初等部分構造、初等埋め込み、Skolem 包、および Tarski–Vaught 判定法が必要である。本記事はこれらを定義せず、同定理を主張しない。本記事の小さいモデルは、理論 $T$ の項モデルとして新たに構成され、もとの任意のモデルの部分構造である必要はない。

6 演習

問題 6.1.

$T\subseteq\operatorname{Sent}(L)$ から $|T|\le\max(\aleph_0,|L|)$ が従う理由を説明せよ。
上方 Löwenheim–Skolem の証明で、同じ $\lambda$ に対する下界と上界をそれぞれ与える箇所を特定せよ。
元のモデルが無限であるという仮定を、有限充足可能性のどこで用いるか説明せよ。
小さいモデルの存在定理と、初等部分構造としての下方 Löwenheim–Skolem の定理の結論を区別せよ。

解答 (確認問題の解答).

$L$ の文は、記号集合へ有限個の論理記号と構文タグを加えた集合上の有限列へ単射する。有限列全体の濃度は§E16.11 補題 2.1により高々 $\max(\aleph_0,|L|)$ であり、 $T$ は文集合の部分集合である。
相異なる定数の解釈 $i\mapsto c_i^{N_\lambda}$ が $|N_\lambda|\ge\lambda$ を与える。拡大言語と理論の濃度がともに高々 $\lambda$ であることと、小さいモデルの存在定理が $|N_\lambda|\le\lambda$ を与える。
$\Delta$ の有限部分に現れる有限個の新定数へ、相異なる要素を割り当てる箇所で用いる。元のモデルが有限なら、要求される定数の個数が台集合の濃度を超える有限部分を満たすことができない。
小さいモデルの存在定理は、 $T$ を満たす何らかの小さいモデルを与えるだけである。初等部分構造版は、与えられたモデル $N$ の内部に、指定した集合を含む小さい部分構造 $M$ を取り、 $M$ と $N$ がすべての一階論理式について同じ真理を共有することまで主張する。

▨

§E16.14Löwenheim–Skolem の定理