レーヴェンハイム=スコーレムの定理 は、一階述語論理の理論について、「無限のモデルを1つでも持つなら、可算のモデルも、もっと大きいモデルも、あらゆる無限の大きさのモデルを持つ」ことを述べる定理です。

言い換えると、一階述語論理の文をいくら並べても、「無限の構造がどれくらい大きいか」を決めることはできません。自然数のつもりで書いた公理にも非可算のモデルがあり、実数のつもりで書いた公理にも可算のモデルがあります。

この定理は、完全性定理 と深く結びついています。完全性定理の証明は、副産物として可算のモデルを作るので、そこからレーヴェンハイム=スコーレムの定理が出てきます。歴史的には逆に、スコーレムの研究の中に完全性定理がほぼ含まれていました。この記事では、定理の主張と証明の考え方を見たあと、6章で2つの定理の関係を詳しく解説します。

1. 定理の主張

1.1 準備:部分構造と初等部分構造

一階の言語 L\mathcal{L} を固定します。L\mathcal{L} の構造 M\mathcal{M} の領域を MM と書き、その大きさ(濃度)を ∣M∣|M| と書きます。∣L∣|\mathcal{L}| は言語の記号の個数です。

構造 M\mathcal{M} の領域の部分集合 NN が、関数記号と定数記号の解釈で閉じているとき、関係を NN に制限して得られる構造 N\mathcal{N} を、M\mathcal{M} の 部分構造 といいます。

部分構造の中でも、元の構造と同じ文が成り立つものが重要です。

特に、N⪯M\mathcal{N} \preceq \mathcal{M} なら、N\mathcal{N} と M\mathcal{M} ではまったく同じ文が成り立ちます。一階述語論理の文では、2つの構造を区別できないということです。

1.2 下方と上方

定理は、モデルを小さくする「下方」と、大きくする「上方」の2つの部分からなります。

2つを合わせると、次のようにまとめられます(文献 [10])。

レーヴェンハイム=スコーレムの定理

無限の構造 M\mathcal{M} と、κ≥∣L∣+ℵ0\kappa \ge |\mathcal{L}| + \aleph_0 を満たす任意の無限基数 κ\kappa に対して、大きさ κ\kappa の構造 N\mathcal{N} で、M\mathcal{M} の初等部分構造か初等拡大になっているものが存在する。

言語が可算の場合、つまり普通の数学の理論では、次の形がいちばんよく使われます。

2. 歴史:名前が3人分ある定理

この定理は、20年以上にわたって、何人もの手で少しずつ形を変えてきました(以下は主に文献 [10] による)。

  • レーヴェンハイム(1915年):「充足可能な一階の文は、可算の領域で充足可能である」ことを示しました(文献 [1])。論文の主題はパースとシュレーダーの関係算で、記法もシュレーダーのものでした。証明には、当時まだ発表されていなかったケーニヒの補題にあたる議論が、証明なしに使われていたというのが通説です。ただし、証明は完全だとみる再評価もあります(文献 [10])。
  • スコーレム(1920年):可算個の文の集合に一般化し、正しい証明を与えました(文献 [2])。今日 スコーレム標準形 と呼ばれるものを使い、選択公理に頼る証明で、「モデル M\mathcal{M} を持つ可算の理論は、M\mathcal{M} の 可算の部分構造 で充足される」という強い形を示しています。
  • スコーレム(1922年):選択公理を使わない証明を与えました(文献 [3])。その代わり、結論は「何らかの可算のモデルを持つ」という弱い形です。この講演は、ヘルシンキで開かれた第5回スカンジナビア数学者会議のもので、後で述べる スコーレムのパラドックス が初めて示されたのもこの論文です(文献 [11])。
  • マルツェフ(1936年):大きいモデルの存在、つまり上方の部分を含む一般の形を証明しました(文献 [4])。マルツェフは、タルスキが1928年のセミナーで証明していたというスコーレムの注記を引用しています。そのため、この定理は レーヴェンハイム=スコーレム=タルスキの定理 と呼ばれることもあります(文献 [10])。

3. 下方の証明:スコーレム関数で閉じる

下方の定理の証明の考え方は、「存在する」と言われたものを、残らず拾い集める ことです。

3.1 タルスキ=ヴォートの判定法

部分構造が初等部分構造かどうかは、次の判定法で確かめられます。

つまり、「M\mathcal{M} で存在が言える要素の候補が、いつも NN の中にも見つかる」なら、NN は初等部分構造です。論理式の複雑さについての帰納法で示せます。難しいのは ∃\exists の場合だけで、そこをこの条件がちょうど補います。

3.2 スコーレム関数と閉包

そこで、存在の候補を選ぶ関数を用意します。選択公理を使い、論理式 φ(y,x1,…,xn)\varphi(y, x_1, \dots, x_n) ごとに、次の性質を持つ関数 fφ:Mn→Mf_\varphi : M^n \to M を選びます(文献 [10])。

M⊨∃y φ(y,aˉ)  ⟹  M⊨φ(fφ(aˉ),aˉ)\mathcal{M} \models \exists y\, \varphi(y, \bar{a}) \;\Longrightarrow\; \mathcal{M} \models \varphi(f_\varphi(\bar{a}), \bar{a})

fφf_\varphi は、「存在するなら、その1つを指し示す」関数です。これを スコーレム関数 といいます。

大きさ κ\kappa の部分集合 A⊆MA \subseteq M から始めて、スコーレム関数の値を付け加える操作をくり返します。

A0=A,Ak+1=Ak∪{ fφ(aˉ)∣φ は論理式, aˉ∈Ak },N=⋃kAkA_0 = A, \qquad A_{k+1} = A_k \cup \{\, f_\varphi(\bar{a}) \mid \varphi \text{ は論理式},\ \bar{a} \in A_k \,\}, \qquad N = \bigcup_{k} A_k

NN はすべてのスコーレム関数で閉じているので、タルスキ=ヴォートの判定法の条件を満たし、N⪯M\mathcal{N} \preceq \mathcal{M} となります。

大きさについては、論理式は ∣L∣+ℵ0|\mathcal{L}| + \aleph_0 個しかないので、1回の操作で増える要素は ∣Ak∣+∣L∣+ℵ0|A_k| + |\mathcal{L}| + \aleph_0 個以下です(文献 [10])。κ≥∣L∣+ℵ0\kappa \ge |\mathcal{L}| + \aleph_0 なので、これを可算回くり返しても大きさは κ\kappa のままです。こうして、大きさ κ\kappa の初等部分構造が得られます。

4. 上方の証明:新しい定数をたくさん入れる

上方の定理は、コンパクト性定理 から導けます。

M\mathcal{M} を無限の構造とし、大きさ κ\kappa のモデルが欲しいとします。証明の流れは次のとおりです(文献 [10]、[12])。

  1. M\mathcal{M} の要素ごとに定数を加え、M\mathcal{M} で成り立つ文をすべて集めます(M\mathcal{M} の 初等図式)。これを満たす構造は、M\mathcal{M} を初等部分構造として含みます。
  2. さらに、新しい定数 cic_i(i<κi < \kappa)を κ\kappa 個加え、異なる定数どうしが異なることを表す文 ci≠cjc_i \neq c_j(i≠ji \neq j)をすべて加えます。
  3. この文の集合の有限部分には、ci≠cjc_i \neq c_j が有限個しか含まれません。M\mathcal{M} は無限なので、有限個の cic_i に M\mathcal{M} の異なる要素を割り当てれば満たせます。よって、コンパクト性定理により、全体もモデルを持ちます。
  4. そのモデルには異なる要素が少なくとも κ\kappa 個あり、M\mathcal{M} の初等拡大になっています。大きすぎる場合は、下方の定理で、M\mathcal{M} と cic_i たちを含む大きさ κ\kappa の初等部分構造に縮めます。

同じ議論から、「いくらでも大きい有限モデルを持つ理論は、無限のモデルを持つ」ことも分かります(文献 [10])。

5. 定理が教えること

5.1 無限の構造は、一階述語論理では決めきれない

ある理論のモデルが、同型を除いてただ1つに決まるとき、その理論は 範疇的 であるといいます。この言葉はヴェブレンが1904年に導入しました(文献 [10])。

レーヴェンハイム=スコーレムの定理により、無限のモデルを持つ一階の理論は、大きさの違うモデルを必ず持つので、範疇的にはなりえません。これは、数学を一階の理論で「ただ1つの構造」として基礎づけようとする期待への最初の打撃でした。その期待は、1931年のゲーデルの不完全性定理で完全に崩れます(文献 [10])。

具体的には、次のようなモデルがあります(文献 [10])。

  • 自然数:自然数の構造 (N,+,×,0,1)(\mathbb{N}, +, \times, 0, 1) で成り立つ一階の文をすべて集めた理論(真の算術)にも、非可算のモデル がある。そのモデルは一階の帰納法の公理をすべて満たすが、帰納法が成り立たない部分集合を持つ。
  • 実数:実数の体 (R,+,×,0,1)(\mathbb{R}, +, \times, 0, 1) で成り立つ一階の文をすべて集めた理論(実閉体の理論)にも、可算のモデル がある。実数を特徴づける「上限を持つ」という性質(順序の完備性)は、一階の文では書けない。

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

いちばん有名な帰結は、集合論そのものに定理を当てはめたときに現れます(文献 [11]、[15])。

集合論の公理系 ZFC は可算の言語(記号は ∈\in だけ)で書かれています。ZFC がモデルを持つなら、下方の定理により 可算のモデル M\mathcal{M} を持ちます。ところが ZFC は「非可算の集合が存在する」(たとえば実数の集合は非可算である)ことを証明します。すると、

  • M\mathcal{M} の中には、M\mathcal{M} が「非可算」と判断する集合 mm がある。
  • しかし M\mathcal{M} 全体が可算なので、mm の要素も外から見れば可算個しかない。

これが スコーレムのパラドックス です。

6. 完全性定理との関係

ここからが本題です。レーヴェンハイム=スコーレムの定理と完全性定理は、主張の見た目はまったく違います。

完全性定理レーヴェンハイム=スコーレムの定理
主張正しい文は証明できる(Γ⊨φ⇒Γ⊢φ\Gamma \models \varphi \Rightarrow \Gamma \vdash \varphi)モデルの大きさは自由に変えられる
証明の体系主役出てこない(意味論だけの定理)
中心の問い証明とモデルは一致するかどんな大きさのモデルがあるか

ところが、証明の中身を見ると、2つの定理は同じ根から生えています。

6.1 完全性定理の証明は、可算のモデルを作る

完全性定理の記事 で見たように、完全性定理の証明は、記号からモデルを作る ものでした。

  • ゲーデル流:変数 v0,v1,v2,…v_0, v_1, v_2, \dots を要素とするモデルを作る。領域は自然数と同一視できるので、可算 です(文献 [16])。
  • ヘンキン流:可算の言語に証人の定数を加えた言語 L∗\mathcal{L}^* の閉項を要素とするモデルを作る。L∗\mathcal{L}^* も可算なので、閉項も 可算個 です(文献 [6])。

どちらの証明も、モデルを作る材料が記号だけなので、作ったモデルは記号の個数より大きくなりえません。これだけで、下方の定理(の弱い形)が出てきます。

この証明では選択公理を使っていません。結論も「何らかの可算のモデルを持つ」という形で、これはちょうどスコーレムの1922年の形にあたります。2章で見たように、元のモデル M\mathcal{M} の 部分構造 として可算のモデルを取り出す1920年の強い形には、スコーレム関数(選択公理)が必要でした。完全性定理の証明は、元のモデルとは無関係に、記号から新しくモデルを作るので、取り出すのではなく作り直す形になります。

6.2 大きい言語では、任意の大きさのモデルが出る

ヘンキン自身が論文で指摘しているとおり、この方法は非可算個の記号を持つ言語にも広げられます(文献 [6])。文を並べる部分を、ツォルンの補題(または超限帰納法)に置き換えるだけです。そのとき作られるモデルも閉項からなるので、その大きさは言語の大きさ ∣L∣+ℵ0|\mathcal{L}| + \aleph_0 以下です。

これを使うと、6.1 の証明と同じ考え方で、上方の向きも出てきます。Γ\Gamma が無限のモデルを持つとき、新しい定数 cic_i を κ\kappa 個と、ci≠cjc_i \neq c_j をすべて加えると、

  • 言語の大きさは κ\kappa なので、ヘンキンのモデルの大きさは κ\kappa 以下
  • 異なる定数が κ\kappa 個あるので、モデルの大きさは κ\kappa 以上

となり、ちょうど大きさ κ\kappa のモデル が得られます。完全性定理(とその証明)だけで、「無限のモデルを持つ理論は、∣L∣+ℵ0|\mathcal{L}| + \aleph_0 以上のあらゆる大きさのモデルを持つ」ことが分かるわけです。初等部分構造・初等拡大の形にしたいときは、4章のように初等図式を加えて同じことをします。

6.3 完全性定理からコンパクト性定理へ

4章の上方の証明で使ったコンパクト性定理も、完全性定理からすぐに出ます(文献 [12])。

ゲーデルは1930年の論文(文献 [7])で、可算個の文についてのコンパクト性定理にあたる結果を得ており、非可算の場合はマルツェフが1936年に示しました(文献 [12])。2章で見たとおり、上方の定理を一般の形で証明したのも、1936年のマルツェフです。

なお、選択公理を仮定しない集合論(ZF)の上では、コンパクト性定理と完全性定理は互いに同値で、どちらもブール代数の素イデアル定理と同値であることが知られています(文献 [12])。

まとめると、次のような関係になります。

完全性定理から出てくるもの

  • 作ったモデルは、記号の個数より大きくならない → 下方レーヴェンハイム=スコーレムの定理(弱い形、6.1)
  • 導出は有限個の前提しか使わない → コンパクト性定理(6.3)
  • 言語を大きくすれば、モデルも大きくできる(6.2)、またはコンパクト性定理と新しい定数(4章) → 上方レーヴェンハイム=スコーレムの定理

6.4 歴史的には、レーヴェンハイム=スコーレムが先

ここまでは「完全性定理からレーヴェンハイム=スコーレムの定理が出る」という向きでした。しかし歴史の順番は逆です。

  • レーヴェンハイム(1915年)とスコーレム(1920年、1922年)の仕事は、ゲーデルの完全性定理(1929–1930年)より前です。
  • ゲーデルは、スコーレムがレーヴェンハイム=スコーレムの定理の証明で使った方法を応用して、論理式を ∀xˉ ∃yˉ ψ\forall \bar{x}\, \exists \bar{y}\, \psi の形に帰着させました(文献 [16])。
  • 一階述語論理の完全性は、スコーレムが1920年代前半に証明し、1928年の論文で論じた結果から、系として導けるものでした。しかし、スコーレム自身はそれを完全性定理として述べてはいません(文献 [17])。ゲーデルは後年、スコーレムの研究に暗に解答が含まれていたことを当時は知らなかったと、1964年のファン・ハイエノールト宛ての手紙で認めています(文献 [18])。

スコーレムに足りなかったのは、モデルの構成を 形式的な証明可能性 と結びつけ、「構成が失敗するのは、矛盾が証明できるときだけ」と述べる視点でした。ゲーデルの貢献はまさにそこにあったといえます。

つまり2つの定理は、同じ構成(記号から可算の領域の上にモデルを組み立てる) を、別の角度から見たものと捉えられます。

  • 「その構成はいつ失敗するか」に注目すると、完全性定理(失敗するのは、矛盾が証明できるときだけ)
  • 「その構成で何ができるか」に注目すると、レーヴェンハイム=スコーレムの定理(作ったモデルは可算)

6.5 リンドストレームの定理:2つの性質が一階述語論理を特徴づける

1969年、リンドストレームは、この2つの定理の関係をさらに深いところで明らかにしました(文献 [9]、[13])。

つまり、一階述語論理は、「コンパクト性」と「レーヴェンハイム=スコーレムの性質」を両方持つ論理の中で、最も表現力が強い 論理です。6.1〜6.3 で見たとおり、この2つの性質は、どちらも完全性定理の証明から出てくるものでした。

逆に、表現力を上げると、この性質は失われます。たとえば 二階述語論理(性質や集合についても量化できる論理)では、「実数はアルキメデス的な完備順序体としてただ1つに決まる」ように、無限の構造を同型を除いて特徴づけることができます(文献 [14])。その代わり、標準的な意味論のもとでは、

  • コンパクト性もレーヴェンハイム=スコーレムの定理も成り立たない
  • 健全で完全で、しかも機械的に確かめられる証明の体系は存在しない(不完全性定理の系)

ことが知られています(文献 [14])。

完全性定理を持つ(証明で真理を捉えきれる)ことと、無限の大きさを区別できないことは、一階述語論理という同じコインの表と裏 だといえます。

まとめ

  • レーヴェンハイム=スコーレムの定理:一階の理論が無限のモデルを持てば、∣L∣+ℵ0|\mathcal{L}| + \aleph_0 以上のあらゆる大きさのモデル(初等部分構造・初等拡大)を持つ。
  • 下方 はスコーレム関数で「存在するもの」を拾い集めて閉じることで、上方 はコンパクト性定理と新しい定数で示す。
  • 帰結として、無限の構造は一階述語論理では同型を除いて決まらない。集合論に当てはめると、可算・非可算が相対的な概念であること(スコーレムのパラドックス)が分かる。
  • 完全性定理との関係:完全性定理の証明は記号からモデルを作るので、モデルの大きさは言語の大きさで抑えられ、下方の定理が出る。完全性定理からコンパクト性定理が出て、そこから上方の定理が出る。歴史的には、スコーレムの研究の中に完全性定理がほぼ含まれていた。
  • リンドストレームの定理:コンパクト性とレーヴェンハイム=スコーレムの性質の両方を持つ論理の中で、一階述語論理が最も強い。
  • 完全性定理の2つの証明は、完全性定理の2つの証明 で、20世紀の流れは 20世紀の数理論理学の年表 で見られます。

参考文献

本文中の「文献 n」は、以下の番号に対応します。内容と書誌情報は、各ページの記載で確認しました(2026年11月16日)。

一次文献(原論文)

  1. L. Löwenheim, "Über Möglichkeiten im Relativkalkül", Mathematische Annalen, 76(4) (1915), pp. 447–470. doi:10.1007/BF01458217(英訳は文献 [5] に収録)
  2. Th. Skolem, "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen", Videnskapsselskapets Skrifter, I. Matematisk-naturvidenskabelig Klasse, 4 (1920), pp. 1–36.(英訳は文献 [5] に収録)
  3. Th. Skolem, "Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre", Den Femte Skandinaviska Matematikerkongressen, Redogörelse(ヘルシンキ, 1922年7月4–7日), pp. 217–232.(英訳は文献 [5] に収録)
  4. A. I. Maltsev, "Untersuchungen aus dem Gebiete der mathematischen Logik", Matematicheskii Sbornik, Novaya Seriya, 1(43)(3) (1936), pp. 323–336.
  5. J. van Heijenoort 編, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, 1967.(文献 [1] は pp. 228–251、[2] は pp. 252–263、[3] は pp. 290–301 に英訳を収録)
  6. L. Henkin, "The Completeness of the First-Order Functional Calculus", The Journal of Symbolic Logic, 14(3) (1949), pp. 159–166. doi:10.2307/2267044 Cambridge Core
  7. K. Gödel, "Die Vollständigkeit der Axiome des logischen Funktionenkalküls", Monatshefte für Mathematik und Physik, 37 (1930), pp. 349–360.
  8. L. Henkin, "Completeness in the Theory of Types", The Journal of Symbolic Logic, 15(2) (1950), pp. 81–91. Cambridge Core
  9. P. Lindström, "On Extensions of Elementary Logic", Theoria, 35 (1969), pp. 1–11. doi:10.1111/j.1755-2567.1969.tb00356.x

二次文献・解説

  1. "Löwenheim–Skolem theorem", Wikipedia(英語版).(定理の一般形、歴史(主に Dawson(1993年)に基づく記述)、下方・上方の証明の概略、範疇性と自然数・実数のモデルについての帰結)Wikipedia
  2. "Skolem's Paradox", Stanford Encyclopedia of Philosophy(2009年初出、2025年改訂).(パラドックスの内容と解消、スコーレムの1922年の論文での議論)SEP
  3. "Compactness theorem", Wikipedia(英語版).(コンパクト性定理の主張、完全性定理からの導出、ブール代数の素イデアル定理との同値性、ゲーデル(1930年)とマルツェフ(1936年)の結果、上方の定理の証明)Wikipedia
  4. "Lindström's theorem", Wikipedia(英語版). Wikipedia
  5. "Second-order logic", Wikipedia(英語版).(二階述語論理の表現力、完全な証明体系がないこと、コンパクト性とレーヴェンハイム=スコーレムの定理が成り立たないこと、ヘンキン意味論)Wikipedia
  6. "Skolem's paradox", Wikipedia(英語版). Wikipedia
  7. "Original proof of Gödel's completeness theorem", Wikipedia(英語版).(ゲーデルの証明の構成、標準形への帰着、可算のモデル)Wikipedia
  8. "Thoralf Skolem", Wikipedia(英語版).(スコーレムの1920年代の結果と完全性定理の関係)Wikipedia
  9. J. W. Dawson, Jr., "The published work of Kurt Gödel: an annotated bibliography".(ゲーデルの完全性定理の論文と、スコーレムの研究との関係についての注釈)PDF

初等部分構造、タルスキ=ヴォートの判定法、6.1〜6.3 の導出は、モデル理論の標準的な教科書で扱われる事項です。