レーヴェンハイム・スコーレム定理｜モデルのサイズに関する驚きの結果
レーヴェンハイム・スコーレム定理（Löwenheim-Skolem theorem）は、モデルのサイズに関する驚くべき結果を与えます。一階述語論理の表現力の限界を示すと同時に、モデルの構造について深い洞察を提供します。
下向きレーヴェンハイム・スコーレム定理
下向き版は次のように述べられます。
可算言語 L の理論 T が無限モデルを持つなら、T は可算モデルを持つ。
つまり、どんなに大きな無限モデルがあっても、可算（自然数と同じ濃度）のモデルも必ず存在します。
実数全体 ℝ のような非可算集合を台集合とする構造にも、可算な「縮小版」が存在する。
レーヴェンハイムが1915年に証明し、スコーレムが1920年に改良した。
上向きレーヴェンハイム・スコーレム定理
上向き版は次のように述べられます。
可算言語 L の理論 T が無限モデルを持つなら、任意の無限濃度 κ に対して、T は濃度 κ のモデルを持つ。
無限モデルがあれば、どんなに大きなモデルも構成できます。
大きなモデルから小さな（可算）モデルへ。
小さなモデルから大きな（任意の濃度の）モデルへ。
スコーレムのパラドックス
レーヴェンハイム・スコーレム定理は、「スコーレムのパラドックス」と呼ばれる哲学的問題を提起します。
集合論（ZFC）は、非可算集合の存在を証明します。しかし、ZFC 自体は可算言語で書かれた理論なので、レーヴェンハイム・スコーレム定理により可算モデルを持ちます。可算モデルの中で「非可算集合が存在する」という文は真ですが、外から見るとその「非可算集合」は実際には可算です。
可算モデルの中で「非可算」と見なされるものは、外から見ると可算。「非可算」は相対的な概念。
非可算性は、モデル内部の全単射の不在を意味する。外部から見た濃度とは異なる概念。
証明の概略
下向き定理の証明は、証人を追加してモデルを構成するヘンキンの方法を使います。
理論 T のモデル M が存在するとき、M の可算部分集合を選び、それが閉じるように要素を追加していきます。具体的には、∃x φ(x) が真ならその証人を追加します。可算個のステップで可算モデルが得られます。
上向き定理の証明は、コンパクト性定理を使います。新しい定項を κ 個追加し、それらが互いに異なることを要求する文を加えます。有限部分集合は元のモデルで充足でき、コンパクト性定理より全体もモデルを持ちます。
定項を κ 個追加
「どの2つも異なる」という文を追加
コンパクト性定理を適用
濃度 κ のモデルを得る
一階論理の限界
レーヴェンハイム・スコーレム定理は、一階論理の表現力の限界を示しています。
一階論理では、「ちょうど可算無限個の要素がある」とか「非可算無限個の要素がある」といった性質を特徴づけることができません。モデルのサイズを制御できないのです。
自然数を「同型を除いて一意に」特徴づけることも、一階論理では不可能です。ペアノ算術の非標準モデルが存在するのはこのためです。
完全性定理、コンパクト性定理が成り立つ。決定可能な断片もある。
濃度の区別ができない。カテゴリカルな理論を書けない。
次回からは、証明論の話題に移り、形式的体系の概念を学びます。
