コンパクト性定理：無限と有限をつなぐ重要な定理 - 記号論理学

コンパクト性定理（compactness theorem）は、モデル理論の基本定理の一つです。無限と有限をつなぐ橋渡しの役割を果たし、数学のさまざまな分野で応用されています。

コンパクト性定理の主張

コンパクト性定理は次のように述べられます。

論理式の集合 Γ がモデルを持つための必要十分条件は、Γ の任意の有限部分集合がモデルを持つことである。

言い換えれば、Γ が充足不能なら、Γ のある有限部分集合が充足不能です。無限個の式すべてを満たせない場合、有限個の式だけでもう矛盾しているのです。

名前の由来

「コンパクト性」という名前は、位相空間論のコンパクト性に由来します。

論理式の集合に適切な位相を入れると、モデルの集合がコンパクト空間になります。コンパクト空間では、開被覆が有限部分被覆を持つという性質があり、これがコンパクト性定理に対応しています。

証明の概略

コンパクト性定理は、完全性定理から導けます。

Γ からある式 φ が論理的に帰結するなら（Γ ⊨ φ）、完全性定理より証明可能です（Γ ⊢ φ）。証明は有限なので、Γ の有限部分集合 Γ₀ から証明できます。

Γ が充足不能なら、Γ ⊨ ⊥（矛盾）なので、有限部分集合から矛盾が導けます。つまり有限部分集合が充足不能です。

応用例：無限モデルの存在

コンパクト性定理の典型的な応用を見てみましょう。

T を任意の有限モデルを持つ理論とします（すべての有限サイズのモデルが存在）。このとき、T は無限モデルも持ちます。

証明：T に「少なくとも n 個の要素がある」という文 ψₙ を追加した集合を考えます。T ∪ {ψ₁, ψ₂, ψ₃, …} の任意の有限部分集合は、十分大きな有限モデルで充足されます。コンパクト性定理より、全体もモデルを持ち、それは無限モデルです。

応用例：非標準モデル

自然数の理論（ペアノ算術）にコンパクト性定理を適用すると、興味深い結果が得られます。

ペアノ算術の公理に、「c はすべての標準的自然数より大きい」という無限個の文を追加します。各有限部分集合には十分大きな自然数でモデルを与えられます。よって、コンパクト性定理より全体にモデルが存在し、それは「無限大の自然数」c を含む非標準モデルです。

コンパクト性定理の限界

コンパクト性定理は強力ですが、二階論理では成り立ちません。

「ちょうど有限個の要素がある」という性質は、二階論理では表現できますが、一階論理では表現できません。コンパクト性定理があるため、一階論理では有限性を特徴づけられないのです。

次回は、レーヴェンハイム・スコーレム定理について学びます。