極大無矛盾集合
maximally consistent set
$ \Gamma^\astと表記
$ \Gamma\subset\Gamma^\ast
$ \Gammaを部分集合として含む
無矛盾で最大の集合
極大無矛盾集合の定義
論理式の集合$ \Deltaが極大無矛盾である
$ \Leftrightarrow$ \Deltaは構文論的に無矛盾であり、$ \Deltaの要素ではない全ての論理式$ Aに対し$ \Delta\cup\{A\}は構文論的に矛盾 $ \Leftrightarrow$ \Deltaは構文論的に無矛盾であり、任意の論理式$ Aについて、$ A,\lnot Aの少なくともが一方が$ \Deltaに属する
これは、$ A,\lnot Aのいずれも含まれない」の否定と捉えるとわかりやすいmrsekut.icon
まだ、いずれかを追加する余地があるということなので、「極大」になっていないということになる
補題
$ \Deltaを言語$ Lで極大無矛盾な閉論理式の集合とする
このとき$ Lの閉論理式$ \varphiについて以下が成り立つ
$ \varphi\in\Delta\Leftrightarrow \Delta\vdash\varphi
$ \Delta\cup\{\varphi\}が無矛盾$ \Rightarrow$ \varphi\in\Delta
つまり、要素は全て証明可能
上の$ \varphi\in\Delta\Leftarrow \Delta\vdash\varphiの証明
$ \Rightarrowは確認していない..mrsekut.icon
$ \Deltaは極大無矛盾集合なので、その定義より
無矛盾であり、
$ \Delta\in\varphiもしくは、$ \Delta\in\lnot\varphiが成り立つ
ここで、$ \Delta\in\lnot\varphiだと仮定すると、
$ \Delta\vdash\varphiかつ$ \Delta\in\lnot\varphiなので、$ \Delta\vdash\bot
これよりは$ \Deltaが無矛盾であることに矛盾
よって$ \Delta\in\varphi