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

レーヴェンハイム–スコーレムの定理（英: Löwenheim–Skolem theorem）とは、可算な一階の理論が無限モデルを持つとき、全ての無限濃度 κ について大きさ κ のモデルを持つ、という数理論理学の定理である。そこから、一階の理論はその無限モデルの濃度を制御できない、そして無限モデルを持つ一階の理論は同型の違いを除いてちょうど1つのモデルを持つようなことはない、という結論が得られる。

シグネチャ（非論理記号の一覧）には、関数記号の集合 S_func、関係記号の集合 S_rel、関数記号と関係記号のアリティを表す関数 ${\displaystyle \operatorname {ar} \colon S_{\mathrm {func} }\cup S_{\mathrm {rel} }\rightarrow \mathbb {N} _{0}}$ から成る（0項の関数記号は、定項記号と呼ばれる）。一階述語論理では、シグネチャを言語 (language) とも呼ぶ。シグネチャに含まれる関数記号と関係記号の集合が可算であるとき、そのシグネチャは可算であると言い、一般にシグネチャの濃度とは、そこに含まれる全記号の集合の濃度を意味する。

一階の理論 (theory) は、固定されたシグネチャと、そのシグネチャにおける固定された文（自由変項のない論理式）の集合で構成される。その論理式の集合は論理的帰結の下で閉じている。理論はその理論を生成する一連の公理で指定されたり、構造を与えてその構造を満足する文で理論を構成したりすることが多い。

シグネチャ σ があるとき、σ の構造 M とは、σ にある記号群の具体的な解釈である。それには、基盤となる集合（それ自体もしばしば "M" で表される）とσの関数記号および関係記号の解釈が含まれる。M におけるσの定数記号の解釈は、単に M の元である。より一般化すれば、n引数の関数記号 f の解釈は、Mⁿ から M への関数である。同様に関係記号 R の解釈は M 上の n項関係であり、すなわち Mⁿ の部分集合である。

σ構造 M の部分構造 (substructure) は、σの全ての関数の解釈の下で閉じた（つまり、σの全定数記号の解釈を含む）M の部分集合 N を取り、関係記号の解釈を N に制限することで得られる。初等部分構造 (elementary substructure) はその非常に特殊な場合であり、元の構造と全く同じ一階の文を満たす。（このときNはMの初等的拡張(elementary extension)という。）

この定理の現代的な形式は、本項目の導入部で行っている可算なシグネチャのバージョンよりも一般的で強い。

一般化されたレーヴェンハイム–スコーレムの定理では、あらゆるシグネチャ σ、あらゆる無限濃度の σ構造 M、あらゆる無限濃度 κ ≥ |σ| について、|N| = κ となる σ構造 N があり、

• κ < |M| なら、N は M の初等的部分構造であり、
• κ > |M| なら、N は M の初等的拡張である。

この定理は、上の箇条書きされた部分に対応して2つに分割されることが多い。ある構造がより小さい濃度の初等部分構造を持つとする定理の部分を下方レーヴェンハイム–スコーレムの定理 と呼ぶ。ある構造がより大きい濃度の初等拡張を持つとする定理の部分を上方レーヴェンハイム–スコーレムの定理 と呼ぶ。

冒頭の簡単な言明の場合、理論の無限のモデルとは、ここでいう M である。定理の上方部分の証明は、いくらでも大きな有限のモデルを持つ理論は無限のモデルを持たねばならないことをも示す。この事実を定理の一部とする場合もある。

自然数を N、実数を R とする。この定理によれば、(N, +, ×, 0, 1) の理論（真の一階算術の理論）には非可算なモデルがあり、(R, +, ×, 0, 1) の理論（実閉体の理論）には可算なモデルがある。もちろん同型の違いを除いて、(N, +, ×, 0, 1) と (R, +, ×, 0, 1) を特徴付ける公理化が存在する。レーヴェンハイム–スコーレムの定理は、それらの公理化が一階ではあり得ないことを示している。例えば、線型順序の完備性は実数が完備な順序体であることを特徴付けるのに使われるが、その線型順序の完備性は一階の性質ではない。

理論が範疇的 categorical であるとは、同型の違いを除いて唯一のモデルを持つことを意味する。この用語は1904年、オズワルド・ヴェブレンが考案したもの^[1]で、その後しばらくの間、数学者らは集合論を範疇的な一階の理論で記述することで、数学の堅固な基盤を築けると考えていた。レーヴェンハイム-スコーレムの定理はこの希望への最初の打撃となった。なぜなら、その定理によれば無限のモデルを持つ一階の理論は範疇的にはなり得ないからである。さらに1931年、ゲーデルの不完全性定理によって希望は完全に打ち砕かれた。

レーヴェンハイム-スコーレムの定理から導かれる結論の多くは、一階とそうでないものの違いがはっきりしていなかった20世紀初頭の論理学者にとっては直観に反していた。例えば、真の算術 (true arithmetic) には非可算なモデルがあり、それらは一階のペアノ算術を満足するが、同時に帰納的でない部分集合を持つ。さらに悩ましかったのは、集合論の可算なモデルの存在である。それにもかかわらず、集合論は実数が非可算であるという文を満たさなければならない。この直観に反するような状況はスコーレムのパラドックスと呼ばれ、可算性 (countability) は絶対的 (absolute) ではないことを示している。

以下の記述は主に Dawson (1993) に基づいている。モデル理論の初期の歴史を理解するには、統語論的整合性（一階論理の推論規則を使って導かれるものには矛盾がないこと）と充足可能性（satisfiability、モデルがあること）を区別しなければならない。驚くことに、ゲーデルの完全性定理が同値であることを証明する以前なのに、整合性 (consistency) という用語はどちらの意味にも使われていた。

後にモデル理論となる重要な成果は、レオポルト・レーヴェンハイム（英語版） が "Über Möglichkeiten im Relativkalkül"（1915年）で発表した下記の「レーヴェンハイムの定理」であった^[2]。

全ての可算なシグネチャ σ について、充足可能な全てのσ文は可算モデルにおいて充足可能である。

しかし、レーヴェンハイムの証明は間違っていた。1920年、トアルフ・スコーレムは後にスコーレム標準形と呼ばれるようになる論理式を使って選択公理に基づいた正しい証明を行った^[3]。

モデル M で充足可能な全ての可算な理論は、M の可算な部分構造において充足可能である。

1923年、スコーレムは選択公理を使わない以下のような弱い形の定理も証明した^[4]。

あるモデルで充足可能な全ての可算な理論は、可算なモデルにおいても充足可能である。

さらに1929年、スコーレムは1920年の成果を単純化した^[5]。そして Anatoly Ivanovich Maltsev (Анато́лий Ива́нович Ма́льцев, 1936年) が完全に汎用的な形式でレーヴェンハイム-スコーレムの定理を証明した^[6]。彼が引用したスコーレムのメモによれば、アルフレト・タルスキが1928年にこの定理を既に証明していたという。このため一般化した定理を「レーヴェンハイム-スコーレム-タルスキの定理」とも呼ぶ。しかし、タルスキは自分が証明したことを覚えておらず、彼がコンパクト性定理を使わずにどうやって証明しえたのかは謎のままである。

スコーレムの名が下方の定理（下降定理）だけでなく上方の定理（上昇定理）にも付与されているのは、ある意味で皮肉である。

「私は、系 6.1.4 を慣例に従って上方レーヴェンハイム-スコーレムの定理と呼ぶ。しかし、実のところスコーレムは非可算集合の存在を信じておらず、したがってこの定理の意味するところを信じてすらいなかった」 - Hodges (1993)

「スコーレムは … その結論を意味がないとして拒絶した。タルスキは … スコーレムの形式主義的観点に立つなら、上方の定理を無意味だとするなら下方レーヴェンハイム-スコーレム定理も無意味とすべきではないか、と非常に適切に応えた」 - Hodges (1993)

「トアルフ・スコーレムは亡くなる直前まで、この定理に彼の名が冠せられていることに憤慨していたという。彼は非可算集合の存在そのものが不合理であるとし、実在しないと考えていた」 - Poizat (2000)

レーヴェンハイム-スコーレムの定理は、モデル理論や数理論理学の教科書には必ずといってよいほど登場する。

• Löwenheim, Leopold (1915), “Über Möglichkeiten im Relativkalkül”, Mathematische Annalen 76 (4): 447–470, doi:10.1007/BF01458217, ISSN 0025-5831 
  • Löwenheim, Leopold (1977), “On possibilities in the calculus of relatives”, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, pp. 228-251, ISBN 0-674-32449-8  (online copy, p. 228, - Google ブックス)
• Maltsev, Anatoly Ivanovich (1936), “Untersuchungen aus dem Gebiete der mathematischen Logik”, Matematicheskii Sbornik, n.s. 1: 323–336 
• Skolem, Thoralf (1920), “Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen”, Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse 6: 1–36 
  • Skolem, Thoralf (1977), “Logico-combinatorical investigations in the satisfiability or provabilitiy of mathematical propositions: A simplified proof of a theorem by L. Löwenheim and generalizations of the theorem”, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, pp. 252-263, ISBN 0-674-32449-8  (online copy, p. 252, - Google ブックス)
• Skolem, Thoralf (1922), “Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre”, Mathematikerkongressen i Helsingfors den 4–7 Juli 1922, Den femte skandinaviska matematikerkongressen, Redogörelse: 217–232 
  • Skolem, Thoralf (1977), “Some remarks on axiomatized set theory”, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (3rd ed.), Cambridge, Massachusetts: Harvard University Press, pp. 290-301, ISBN 0-674-32449-8  (online copy, p. 290, - Google ブックス)
• Skolem, Thoralf (1929), “Über einige Grundlagenfragen der Mathematik”, Skrifter utgitt av det Norske Videnskaps-Akademi i Oslo, I. Matematisk-naturvidenskabelig Klasse 7: 1–49 
• Veblen, Oswald (1904), “A System of Axioms for Geometry”, Transactions of the American Mathematical Society 5 (3): 343–384, doi:10.2307/1986462, ISSN 0002-9947, JSTOR 1986462, https://jstor.org/stable/1986462 

• Badesa, Calixto (2004), The Birth of Model Theory: Löwenheim's Theorem in the Frame of the Theory of Relatives, Princeton, NJ: Princeton University Press, ISBN 978-0-691-05853-5 ; A more concise account appears in chapter 9 of Leila Haaparanta, ed. (2009), The Development of Modern Logic, Oxford University Press, ISBN 978-0-19-513731-6 
• Brady, Geraldine (2000), From Peirce to Skolem: A Neglected Chapter in the History of Logic, Elsevier, ISBN 978-0-444-50334-3 
• Dawson, John W., Jr. (1993), “The compactness of First-Order Logic: From Gödel to Lindström”, History and Philosophy of Logic 14: 15–37, doi:10.1080/01445349308837208 
• Hodges, Wilfrid (1993), Model theory, Cambridge: Cambridge Univ. Pr., ISBN 978-0-521-30442-9 
• Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer, ISBN 978-0-387-98655-5 

• Sakharov, Alex and Weisstein, Eric W. "Löwenheim-Skolem Theorem". mathworld.wolfram.com (英語).
• Burris, Stanley N., Contributions of the Logicians, Part II, From Richard Dedekind to Gerhard Gentzen
• Burris, Stanley N., Downward Löwenheim–Skolem theorem
• Simpson, Stephen G. (1998), Model Theory

表 話 編 歴 論理学
関連項目 学術的領域 議論学 価値論 批判的思考 再帰理論 形式意味論 論理史 非形式論理学 計算機科学における論理学（英語版） 数理論理学 数学 メタ論理学 メタ数学 モデル理論 哲学的論理学 哲学 論理学の哲学 数学の哲学 証明論 集合論 論理学の歴史 基本概念 アブダクション 分析的と総合的の区別（英語版） 二律背反 アプリオリ 演繹 定義(内包と外延) 記述 帰納 推論 論理的帰結 論理形式（英語版） 論理的含意（英語版） 論理的真理 名前 必要十分条件 意味 パラドックス 可能世界論 前提 確率 理性 推理 参考 意味論 命題 サブスティトゥーション（英語版） 統語論（英語版） 真理 真理値 妥当性 数学記号の表
哲学的論理学 批判的思考と非形式論理学 分析 曖昧 信念 信用性（英語版） 根拠 説明 説明力（英語版） 事実 誤謬 探究 意見 節約 根拠 プロパガンダ 思慮分別（英語版） 推理 関連 修辞学 厳格 漠然（英語版） 論理学の哲学 構成主義 真矛盾主義 虚構主義 有限主義（英語版） 形式主義 直観主義 論理的原子論（英語版） 論理主義 唯名論 プラトニック実在論（英語版） プラグマティズム 実在論
メタ論理学と超数学 カントールの定理 決定問題 チャーチのテーゼ 無矛盾性 実効的方法（英語版） 数学基礎論 ゲーデルの完全性定理 ゲーデルの不完全性定理 健全性 完全性 決定可能性 解釈 レーヴェンハイム-スコーレムの定理 メタ定理（英語版） 充足可能性 独立性（英語版） 独立 タイプとトークンの区別 使用と言及の区別
数理論理学 基幹 形式言語 構成規則 形式体系 演繹システム（英語版） 形式的証明 形式意味論 論理式 集合 元 クラス 古典論理 公理 自然演繹 推論規則 有限関係（英語版） 定理 論理的帰結 公理系 型理論 記号 統語論（英語版） 理論（英語版） 名辞論理学（英語版） 命題 推論 論証 妥当性 三段論法 反対の正方形 ベン図 命題論理とブール論理 ブール関数 命題論理 論理演算 真理値表 原子論理式 リテラル 述語論理 量化 全称記号 存在記号 一階述語論理 二階述語論理 高階述語論理 単項述語計算（英語版） 標準形 連言標準形 選言標準形 否定標準形 冠頭標準形 スコーレム標準形 節標準形 集合論 集合 空集合 数え上げ 外延 有限集合 関数 部分集合 冪集合 可算集合 帰納的集合 定義域 値域 順序対 非可算集合 モデル理論 モデル（英語版） 解釈（英語版） 超準モデル 有限モデル理論 真理値 妥当性 証明論 形式的証明 演繹システム（英語版） 形式体系 定理 論理的帰結 推論規則 統語論（英語版） 再帰理論 再帰 帰納的集合 帰納的可算集合 決定問題 チャーチ＝チューリングのテーゼ 計算可能関数 原始再帰関数 表現 真理値表 クワイン・マクラスキー法 カルノー図 存在グラフ 概念地図 オイラー図 ベン図 スパイダー図 タブローの方法 Xバー理論 構文木 構文解析
非古典論理 様相論理学 真理様相（英語版） 価値様相（英語版） 義務論理 信念様相（英語版） 認識論理 時相論理 線形時相論理 直観主義 直観論理 構成的解析（英語版） ハイディング算術（英語版） 直観主義型理論 構成的集合論（英語版） ファジィ論理 真理の程度（英語版） ファジィルール（英語版） ファジィ集合 ファジィ有限要素（英語版） ファジィ集合演算（英語版） 部分構造論理 構造規則（英語版） 適切さの論理 線形論理 矛盾許容論理 真矛盾主義 様相記述論理（英語版） 存在論 オントロジー言語（英語版）
論理学者 アンダーソン アリストテレス イブン・ルシュド イブン・スィーナー ベイン（英語版） バーワイズ（英語版） ベルナイス ブール ブーロス（英語版） カントール カルナップ チャーチ クリュシッポス カリー ド・モルガン フレーゲ ギーチ ゲンツェン ゲーデル ヒルベルト クリーネ クリプキ ライプニッツ レーヴェンハイム（英語版） ペアノ パース パトナム クワイン ラッセル シュレーダー（英語版） スコトゥス スコーレム スマリヤン タルスキ チューリング ホワイトヘッド オッカムのウィリアム ウィトゲンシュタイン ツェルメロ
カテゴリ