コンパクト性定理

論理式の集合\Gammaに対し、

その任意の有限部分集合が個別に充足可能ならば、

\Gamma全体を同時に充足する解釈が存在する

「コンパクト性定理」という名前は位相空間のコンパクトに由来する

定理

\Gammaを命題論理式の集合とする

\Gammaが充足可能である \Leftrightarrow\Gammaの任意の有限部分集合が充足可能

前提知識として

命題論理式の2つの集合\Gamma_1\subset\Gamma_2があるときに、

\Gamma_2が充足可能なら、\Gamma_1は充足可能になる

というのがある

では、これは自明として扱われている

ここの証明も確認したいな

コンパクト性定理で着目するのは、これに加えて逆が成り立つということ

つまり\Gamma_1\subset\Gamma_2のとき、\Gamma_1が充足可能なら、\Gamma_2が充足可能になる

証明

ヘンキンの定理を使うと簡単に証明ができる

本来、コンパクト性は意味論の世界の話であるのに、構文論の世界に行って戻ってくる以下の証明は邪道だと言う人もいるらしい

\Gammaのあらゆる有限部分集合が充足可能

\Leftrightarrow\Gammaのあらゆる有限部分集合が無矛盾

∵ 健全性

\Leftrightarrow\Gammaが無矛盾

∵ 演繹の有限性

もしくは、対偶を考えてもわかりやすい

\Leftrightarrow\Gammaが充足可能

∵ 完全性定理

↑で健全性と完全性を使っているが、

結局はヘンキンの定理の\Leftarrowと\Rightarrowを使っている感じだな

ただ、ヘンキンの定理は完全性定理を証明するため(?)に産まれたので、完全性定理をの解説の直後で紹介する本が多い、って感じなのかな

↓昔のメモ、これは合ってるのか？

これはかなり非直感的だ

参考

『情報理論のための数理論理学』 p.25-