意味論と構文論

論理学に関する記号とその意味も参考

意味論と構文論の対応 ref p.265

意味論と構文論

これらは本来、別物の独立した概念

ある公理系が、意味論と構文論が同値であることを証明するのが完全性定理の証明

良い公理系(?)は、同値になる

A_1,A_2,\cdots,A_n\vDash C\Leftrightarrow A_1,A_2,\cdots,A_n\vdash Cが成り立つ

なるもの

健全性と完全性

以下の2つが同値であることを主張する

構文論での\Gamma\vdash\varphi

意味論での\Gamma\vDash\varphi

つまり\Gamma\vdash\varphi\Leftrightarrow\Gamma\vDash\varphi

これの\Gamma\vdash\varphi\Rightarrow\Gamma\vDash\varphiが健全性

構文→意味だね

証明可能、なら、成り立つ

これの\Gamma\vdash\varphi\Leftarrow\Gamma\vDash\varphiが完全性

構文←意味だね

成り立つ、なら、証明可能

参考