完全性定理
公理と推論規則によって、得られる論理式は全てトートロジーであり、これは世界の全てのトートロジーを漏れなく得られる
定理
$ \vDash\varphi\Leftrightarrow\vdash\varphi
色々渋い点があるので捕捉mrsekut.icon
「完全性」自体は本来は$ \vDash\varphi\Rightarrow\vdash\varphiの方向のみのことだが、
健全でなくて完全であるのは無意味なので、
両方向($ \Leftrightarrow)のことを言って初めて完全だと定義している
それと、上のは空集合に対して、$ \{\}\vDash\varphi\Leftrightarrow\{\}\vdash\varphiが成り立つことを主張している
これを$ \Gammaに対しての主張にするとさらに厳しい条件になる
$ \vDash\varphi\Leftarrow\vdash\varphiのことを健全性定理と呼ぶ 歴史
みたいな話があった気がするmrsekut.icon
完全性定理の証明のためのいくつかのアプローチ
直接的に証明するもの
ref 『学んでみよう！記号論理』.iconpp.144-152
これと『情報理論のための数理論理学』.icon p.44は同じ？
$ X^\ast_1,\cdots,X^\ast_n\vdash \varphi^\ast
記号の意味はあとで書くmrsekut.icon
証明も後で確認
補題を使って証明
論理式$ \varphi(X_1,\cdots,X_n)がトートロジーならば、証明可能である