コンパクト性定理

compactness theorem

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

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

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

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

定理

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

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

前提知識として

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

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

というのがある

『情報理論のための数理論理学』.iconでは、これは自明として扱われている

ここの証明も確認したいなmrsekut.icon

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

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

証明

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

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

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

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

$ \Leftrightarrow$ \Gammaが無矛盾

∵ 演繹の有限性

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

$ \Leftrightarrow$ \Gammaが充足可能

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

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

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

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

https://gyazo.com/5f69f216da6c2869c74a1f9beece75a1

これはかなり非直感的だmrsekut.icon

参考