レーヴェンハイム・スコーレム定理｜モデルのサイズに関する驚きの結果

レーヴェンハイム・スコーレム定理（Löwenheim-Skolem theorem）は、モデルのサイズに関する驚くべき結果を与えます。一階述語論理の表現力の限界を示すと同時に、モデルの構造について深い洞察を提供します。

下向きレーヴェンハイム・スコーレム定理

下向き版は次のように述べられます。

可算言語 L の理論 T が無限モデルを持つなら、T は可算モデルを持つ。

つまり、どんなに大きな無限モデルがあっても、可算（自然数と同じ濃度）のモデルも必ず存在します。

上向きレーヴェンハイム・スコーレム定理

上向き版は次のように述べられます。

可算言語 L の理論 T が無限モデルを持つなら、任意の無限濃度 κ に対して、T は濃度 κ のモデルを持つ。

無限モデルがあれば、どんなに大きなモデルも構成できます。

スコーレムのパラドックス

レーヴェンハイム・スコーレム定理は、「スコーレムのパラドックス」と呼ばれる哲学的問題を提起します。

集合論（ZFC）は、非可算集合の存在を証明します。しかし、ZFC 自体は可算言語で書かれた理論なので、レーヴェンハイム・スコーレム定理により可算モデルを持ちます。可算モデルの中で「非可算集合が存在する」という文は真ですが、外から見るとその「非可算集合」は実際には可算です。

証明の概略

下向き定理の証明は、証人を追加してモデルを構成するヘンキンの方法を使います。

理論 T のモデル M が存在するとき、M の可算部分集合を選び、それが閉じるように要素を追加していきます。具体的には、∃x φ(x) が真ならその証人を追加します。可算個のステップで可算モデルが得られます。

上向き定理の証明は、コンパクト性定理を使います。新しい定項を κ 個追加し、それらが互いに異なることを要求する文を加えます。有限部分集合は元のモデルで充足でき、コンパクト性定理より全体もモデルを持ちます。

一階論理の限界

レーヴェンハイム・スコーレム定理は、一階論理の表現力の限界を示しています。

一階論理では、「ちょうど可算無限個の要素がある」とか「非可算無限個の要素がある」といった性質を特徴づけることができません。モデルのサイズを制御できないのです。

自然数を「同型を除いて一意に」特徴づけることも、一階論理では不可能です。ペアノ算術の非標準モデルが存在するのはこのためです。

次回からは、証明論の話題に移り、形式的体系の概念を学びます。