20201111『数理論理学』輪講のノート

「任意の解釈\(I\)について\([\![\varphi]\!]_I=[\![\psi]\!]_I\)」という関係を\(\varphi\equiv\psi\)、
「任意の解釈\(I\)について\([\![\varphi]\!]_I\leq[\![\psi]\!]_I\)」という関係を\(\varphi\preceq\psi\)
と書くことにし、推論の妥当性や恒真式の話はいったん忘れて、\(\equiv\)が同値関係、\(\preceq\)が半順序関係であることを示します。
（\(\equiv\)が同値関係であること）
・反射律：同じ論理式の真偽値は解釈によらず等しいから、任意の論理式\(\varphi\)について\(\varphi\equiv\varphi\)である。
・対称律：\(\varphi\equiv\psi\)と仮定し、解釈\(I\)を任意にとる。仮定から\([\![\varphi]\!]_I=[\![\psi]\!]_I\)すなわち\([\![\psi]\!]_I=[\![\varphi]\!]_I\)、これが任意の\(I\)で成り立つから\(\psi\equiv\varphi\)である。
・推移律：\(\varphi\equiv\psi\)かつ\(\psi\equiv\chi\)と仮定し、解釈\(I\)を任意にとる。仮定により\([\![\varphi]\!]_I=[\![\psi]\!]_I=[\![\chi]\!]_I\)、これが任意の\(I\)で成り立つから\(\varphi\equiv\chi\)である。■
（\(\preceq\)が半順序関係であること）
・反射律：\(\varphi\equiv\psi\)と仮定し、解釈\(I\)を任意にとる。仮定から\([\![\varphi]\!]_I=[\![\psi]\!]_I\)ゆえ\([\![\varphi]\!]_I\leq[\![\psi]\!]_I\)、これが任意の\(I\)で成り立つから\(\varphi\preceq\psi\)である。*1
・反対称律：\(\varphi\preceq\psi\)かつ\(\psi\preceq\varphi\)と仮定し、解釈\(I\)を任意にとる。仮定により\([\![\varphi]\!]_I\leq[\![\psi]\!]_I\)かつ\([\![\psi]\!]_I\leq[\![\varphi]\!]_I\)ゆえ\([\![\varphi]\!]_I=[\![\psi]\!]_I\)、これが任意の\(I\)で成り立つから\(\varphi\equiv\psi\)である。
・推移律：\(\varphi\preceq\psi\)かつ\(\psi\preceq\chi\)と仮定し、解釈\(I\)を任意にとる。仮定により\([\![\varphi]\!]_I\leq[\![\psi]\!]_I\leq[\![\chi]\!]_I\)、これが任意の\(I\)で成り立つから\(\varphi\preceq\chi\)である。■

半順序一般の性質として（反射律と反対称律から容易に導かれる）\[\varphi\equiv\psi\Leftrightarrow\varphi\preceq\psi かつ\psi\preceq\varphi\]が成り立ち、いま\(\varphi\preceq\psi\)は\(\varphi\models\psi\)の定義に一致するので、\(\varphi\equiv\psi\)を\(\varphi\ \mathbin{\style{display: inline-block; transform: scaleX(-1)}{\vDash}}\vDash\psi\)と書くのは不自然ではないと感じられます。さらに、\(\varphi\preceq\psi\)（\(\varphi\models\psi\)）の定義は「\(\varphi\rightarrow\psi\)が恒真式」、\(\varphi\equiv\psi\)（\(\varphi\ \mathbin{\style{display: inline-block; transform: scaleX(-1)}{\vDash}}\vDash\psi\)）の定義は「\(\varphi\leftrightarrow\psi\)が恒真式」と各々言い換えられるため、「推論の妥当性」（2つの論理式の間の関係）を「単一の論理式の恒真性」にすり替えて議論することが可能となります。

*1:ここでは\(\equiv\)を等号と見た上での半順序関係を考えているので、\(\varphi\preceq\varphi\)を言うだけでは不十分である。