命題論理の完全性定理について - ちょーさんメモ出張版気まぐれブログ

今回は趣味でやってる基礎論の話題について書こうと思います。

といってもそんな大した話ではなく，古典一階命題論理の完全性定理について自分の覚え書きのためも兼ねてつらつらと書いていきます。

数理論理学pdf
モデル存在定理
完全性定理
おわりに

数理論理学pdf

まず、以前に基礎論布教用に命題論理について基本を一通りまとめたpdfを書きました。

論理式の定義から完全性定理までをカバーしています。

この完全性定理の証明なのですが、できるだけ直接に完全性定理を示そうとしたところなんか微妙な証明になった気がするのでここでは別の証明をざっくり追ってみようと思います。

以下、ノーテーションはpdfに従うものとします。

モデル存在定理

pdfの最後の方でも触れた通りモデル存在定理という定理があります。

　モデル存在定理

　　論理式の集合 $\Gamma$ について $\Gamma$ が無矛盾ならば $\Gamma$ はモデルをもつ．

今回はこの定理を証明し、これを用いて完全性定理を示していきます。

モデル存在定理を示すためにpdfと同様に2つの補題を用います。

　Zornの補題

　　空でない帰納的順序集合 $X$ には極大元が存在する．

　　特に任意の $x\in X$ について $x\leq x^\ast$ となる極大元 $x^\ast\in X$ が存在する．

　演繹定理

　　論理式の集合 $\Gamma$ ，論理式 $\varphi,\psi$ について

$\Gamma\cup\{\varphi\}\vdash\psi\ \Leftrightarrow\ \Gamma\vdash\varphi\to\psi$

これらの補題についてはpdfを参照とします。ただし演繹定理の方は今回は明示的には用いません。

以上の準備の下にモデル存在定理を証明していきます。

（証明） $\Gamma$ を無矛盾な論理式の集合とする．

論理式全体の集合を $\Phi$ とおく． $\mathcal{A}$ を無矛盾な $\Phi$ の部分集合全体の集合とする．

このとき $\mathcal{A}$ は包含関係について帰納的順序集合となることがわかる． $\Gamma\in\mathcal{A}$ なのでZornの補題より $\Gamma\subset\Gamma^\ast$ となる極大元 $\Gamma^\ast\in\mathcal{A}$ がとれる．

$\Gamma^\ast$ は次の性質を持っている．（ここで演繹定理を用いる）

$\mbox{任意の論理式}\varphi\mbox{について}\ \varphi\in\Gamma^\ast\mbox{または}\neg\varphi\in\Gamma^\ast$

またこの性質から $\Gamma^\ast$ について次の性質が従う．

　　 $\psi\wedge\chi\in\Gamma^\ast \ \Leftrightarrow\ \psi\in\Gamma^\ast\mbox{かつ}\chi\in\Gamma^\ast$

　　　 $\psi\vee\chi\in\Gamma^\ast \ \Leftrightarrow\ \psi\in\Gamma^\ast\mbox{または}\chi\in\Gamma^\ast$

　　　 $\ \psi\to\chi\in\Gamma^\ast \ \Leftrightarrow\ \psi\notin\in\Gamma^\ast\mbox{または}\chi\in\Gamma^\ast$

$\neg\psi\in\Gamma^\ast \ \Leftrightarrow\ \psi\notin\Gamma^\ast\hspace{0.9cm}$

そこで写像 $\mathcal{M}\colon\Omega\to\{0,1\}$ を次のように定義する．

$\mathcal{M}(X)=1\hspace{1.0em}(X\in\Gamma^\ast\mbox{のとき})$

$\ \mathcal{M}(X)=0\hspace{1.0em}(X\notin\Gamma^\ast\mbox{のとき})$

このとき前述の $\Gamma^\ast$ の性質より

$\mbox{任意の論理式}\varphi\mbox{について}\ \mathcal{M}\models\varphi\ \Leftrightarrow\ \varphi\in\Gamma^\ast$

が成り立つ．

よって $\Gamma\subset\Gamma^\ast$ であることより $\mathcal{M}$ は $\Gamma$ のモデルである． $\rule{4mm}{4mm}$

この証明では極大無矛盾集合とよばれる $\Gamma^\ast$ がキーになっています。pdfでの完全性定理の証明も本質的にはこれと同じ方法をとっています。

完全性定理

では実際にモデル存在定理を用いて完全性定理を証明しましょう。

　完全性定理

　　 $\Gamma$ を論理式の集合， $\varphi$ を論理式とするとき

$\Gamma\models\varphi\Rightarrow\Gamma\vdash\varphi$

（証明）対偶を示す．つまり $\Gamma\vdash\hspace{-0.8em}\backslash \varphi$ を仮定して $\Gamma\models\hspace{-1.0em}\backslash\ \varphi$ を示す．ここで $\Gamma\models\varphi$ とは $\Gamma$ の任意のモデルで $\varphi$ が真であることだったので $\Gamma\models\hspace{-1.0em}\backslash\ \varphi$ を示すには $\varphi$ が偽となる $\Gamma$ のモデルが存在することを言えばよい．

$\Gamma\vdash\hspace{-0.8em}\backslash \varphi$ のとき， $\Gamma\cup\{\neg\varphi\}$ が無矛盾であることがわかる．よってモデル存在定理より $\Gamma\cup\{\neg\varphi\}$ のモデル $\mathcal{M}$ が存在するが，この $\mathcal{M}$ は $\varphi$ が偽となる $\Gamma$ のモデルである． $\rule{4mm}{4mm}$

見る人が見ればすぐにわかるかと思いますがこの証明は鹿島先生の『数理論理学』を参考にしたもの（というかこの部分に関してはまるっきりそのもの）です。

完全性定理の証明は数理論理学の中でも最初に悩むことになる非自明なところなのですが、このように対偶をとることでモデル存在定理に帰着しモデル存在定理はZornの補題から無矛盾極大集合をとることで示されると思えば理解しやすいのではないかと思います。

ただしこの方法は命題論理だから通用するもので、述語論理では存在量化記号に対してデリケートな問題が残るので言語の拡大などの方法でもう少し調整をする必要があります。このあたりがまた悩むところですね…

おわりに

以上で命題論理の完全性定理が証明できました。本当はもう少し、完全性定理とモデル存在定理とコンパクト性定理の同値性辺りまで書こうかと思ったのですが疲れたのでまたいつか気が向いたときに書くことにします。

参考文献はpdfに載せてあります。数理論理学の入門としてオススメの順番に並べてあるので興味のある人は上の方にあるタイトルを適当に開いてみるといいかと思います。