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

問題解答例:f:id:y_bonten:20210316111650j:plain

練習問題7.35のヒント:(GEN)と(GEN')の一方から他方を相互に導く際に記号がぶつかると混乱をきたしやすいので、(GEN')のほうの記号を書き換えておきます。
(GEN')\(\quad\psi\quad\Longrightarrow\quad\forall\beta(\psi[\beta/\mu])\)
ただし\(\mu\)は\(\psi\)の演繹の前提に含まれる論理式に自由変項として現れていないこと。\(\beta\)は\(\beta\equiv\mu\)であるか、または\(\psi\)に自由変項として現れていないこと。

(GEN)から(GEN')を導くには、\(\mu,\beta\)が(GEN')の但し書きを満たしていると仮定して、(GEN)を適用できないかどうか考えます。このとき(GEN)の\(\varphi,\zeta,\xi\)として何を選べばよいのか、また(GEN)の但し書きに抵触しない状況になっているかどうかを確認します。\(\psi[\beta/\mu][\mu/\beta]\)という論理式が登場し、これは\(\psi\)に書き直したくなりますが、一般には書き直せません。どのような場合に書き直せないのか、今回はその場合を回避できているのか確認します。
(GEN’)から(GEN)を導く際も同様です。