書記が数学やるだけ#955 極大無矛盾集合とヘンキン集合

完全性定理の準備として極大無矛盾集合とヘンキン集合を見ておく。

問題

説明

一階述語論理における完全性定理の証明において、極大無矛盾集合とヘンキン集合は「構文論的な無矛盾集合」から「意味論的なモデル（項モデル）」を構築するための中核的な道具として定義される。

解答

無矛盾性は，意味論的には「Γ のすべての論理式を同時に真にする付値（真理値割り当てモデル） v が存在する」ことである。また極大でないことを示すには反例を用いる。

極大無矛盾性は，Γ が無矛盾であり、かつ任意の論理式 A∈L について、A∈Γ または ¬A∈Γ のいずれかが成り立つこと（完全性）である。極大であることは，新しい式を加えようとすると矛盾することから言える。

リンデンバウムの補題 (Lindenbaum's Lemma)は，「任意の無矛盾な論理式の集合 Σ は、それらを包括する極大無矛盾集合 Γ∗ へと拡張（拡大）可能である」ことを示している。ここでツォルンの補題（選択公理）を導入することで、有限の無矛盾性を、無限の論理式の真偽を決定できる「極大無矛盾集合（＝モデルの設計図）」へと引き上げる。

(2)について，Δ2  には存在命題 ∃xP(x) が含まれている。しかし、言語 L で使用可能なすべての定数記号 c1 ,c2  について、集合に含まれているのは否定形の ¬P(c1 ),¬P(c2 ) だけである。つまり、「存在する」と主張しているにもかかわらず、その証拠となる式（P(c1 ) または P(c2 )）が集合内に1つも存在しないため、ヘンキン特性を満たさない。この集合自体は無矛盾であるが、ヘンキン特性を持たない典型例である。

一階述語論理において、単に ∃xA(x) が成立する（無矛盾である）ことのみからは、その「証人」となる対象にアクセスできない。ヘンキン集合は、言語 L にあらかじめ存在命題の数だけ新しい定数記号（ヘンキン定項）を添加し、∃xA(x)→A(c) という形の公理を矛盾なく内包させることで、「存在するならば、それを指し示す記号が必ず言語内に存在する」という状態を強制する。

一般にモデル M において ∀xA(x) が真であるとは、「領域のすべての要素」について A が成り立つことを意味するが、これは言語の定数記号だけでは網羅できない場合がある（例：実数の集合に対する可算な言語）。しかし、ヘンキン集合上では「すべての要素に名前（定数記号）が割り当たっている」と同等の構造が構文論的に達成されるため、全称量化（∀）の真偽を、言語内の定数記号の全称評価へと完全に一致させることが可能となる。

本記事のもくじはこちら：