コンパクト性定理とレーヴェンハイム-スコーレムの定理

コンパクト性定理とレーヴェンハイム-スコーレムの定理は、一階理論が記述できる構造を規定する2つの基礎的な結果であり、一階論理の力と固有の限界の両方を明らかにします。

Definition

コンパクト性定理は、一階文の集合が充足可能であるのは、その任意の有限部分集合が充足可能である場合にかぎる、と述べています。レーヴェンハイム-スコーレムの定理は、無限モデルを持つ任意の一階理論は、その言語の濃度以上の任意の無限濃度においてモデルを持つ、と述べています。

Scope

このトピックでは、コンパクト性定理とその完全性定理または超積による証明、モデルの濃度に関する下方および上方レーヴェンハイム-スコーレムの定理、算術および解析の非標準モデルの存在を含むそれらの標準的な帰結、そしてスコーレムのパラドックスについて扱います。

Core questions

• 理論の有限充足可能性がモデルを保証するのはなぜですか？
• これらの定理は、算術と実数の非標準モデルをどのように生成しますか？
• なぜ、いかなる一階理論も濃度に関して無限構造を特徴づけることができないのですか？
• スコーレムのパラドックスとは何ですか、そしてそれはどのように解決されますか？

Key theories

コンパクト性定理

文の集合の任意の有限部分集合がモデルを持つならば、その集合全体もモデルを持つ。これは完全性定理から導かれるか、超積を用いて意味論的に証明できる。

下方レーヴェンハイム-スコーレムの定理

任意の無限構造は、その言語の濃度以下の濃度の初等部分構造を持つ。したがって、無限モデルを持つ可算理論は可算モデルを持つ。

上方レーヴェンハイム-スコーレムの定理

任意の無限モデルは、より大きな任意の濃度のモデルに初等的に拡張できる。したがって、一階理論はその無限モデルのサイズを固定することはできない。

Clinical relevance

これらの定理はモデル理論の主力であり、コンパクト性定理は結果を証明または転送するための非標準モデルを構築するために使用され、レーヴェンハイム-スコーレムの定理は、自然数または実数の1階公理化が常に意図しないモデルを許容する理由を説明し、論理的枠組みの選択に影響を与えます。

History

レーヴェンハイムは1915年に下方定理の一種を証明し、スコーレムは1920年代を通じてそれを一般化し、洗練させました。コンパクト性定理はゲーデルによって完全性定理の系として得られ、マルツェフによって非可算言語に拡張されました。マルツェフはこれを最初に利用して代数定理を導き出し、応用モデル理論への道を開きました。

Key figures

• Leopold Loewenheim
• Thoralf Skolem
• Kurt Goedel
• Anatoly Maltsev

Seminal works

• changkeisler1990
• marker2002
• hodges1993

Frequently asked questions

算術の非標準モデルとは何ですか？

コンパクト性定理により、算術の公理に、すべての数詞よりも大きい定数を追加することができます。結果として得られる無矛盾な理論は、標準的な自然数を超えた無限の要素を含むモデルを持ちます。このようなモデルは、標準的なモデルと全く同じ一階文を充足します。

スコーレムのパラドックスとは何ですか？

下方レーヴェンハイム-スコーレムの定理は、集合論が非可算集合の存在を証明するにもかかわらず、集合論の可算モデルを与えるというものです。この解決策は、非可算性がモデルに相対的であるということです。モデルが非可算と見なす集合は、モデルの内部では自然数との全単射を持ちませんが、外部には存在します。