2.8

(a)

\(T \nvdash \psi \to \varphi\) なので \(T + \psi + \neg \varphi\) は無矛盾である． \(\theta\) を Theorem 2 で得られる \(T + \psi + \neg \varphi\) の \(\Pi_1\) Rosser 文とする． \(\Gamma\) が \(\Sigma_1\) のときは \(\rho\) を \(\neg \theta\)，それ以外のときは \(\rho\) を \(\theta\) としてとる． このとき \(\rho\) は \(T + \psi + \neg \varphi\) において undecidable な \(\Gamma\) 文となる．

と定める．

• \(T \vdash \varphi \to \theta\) は明らか．
• \(T \vdash \theta \land \neg \psi \to \varphi\) と \(T \vdash \varphi \to \psi\) より \(T \vdash \theta \to \psi\) がいえる．
• \(T \vdash \theta \to \varphi\) とすれば \(T \vdash \psi \land \rho \to \varphi\) なので \(T + \psi + \neg \varphi \vdash \neg \rho\) となりおかしい． よって \(T \nvdash \theta \to \varphi\) である．
• \(T \vdash \psi \to \theta\) とすれば \(T \vdash \psi \to \varphi \lor \rho\)，つまり \(T + \psi + \neg \varphi \vdash \rho\) となりおかしい． よって \(T \nvdash \psi \to \theta\) である．

(b)

\(\Pi_1\) 文 \(\theta\) を

を満たすようにとる．

• \(S \vdash \theta\) と仮定すると，\(S \nvdash \neg \theta\) かつ \(T \vdash {\rm Pr}_S(\theta)\). よって \(T \nvdash \neg {\rm Pr}_S(\theta)\)．\(S\) における \(\theta\) の証明を \(p\) とすると，\({\sf Q} \vdash {\rm Prf}_S(\theta, p)\) かつ \({\sf Q} \vdash \forall z \leq p (\neg {\rm Prf}_S(\neg \theta,z) \land \neg {\rm Prf}_T(\neg {\rm Pr}_S(\theta),z))\)．よって \({\sf Q} \vdash \neg \theta\) つまり \(S \vdash \neg \theta\) となり矛盾する． したがって \(S \nvdash \theta\)．
• \(S \vdash \neg \theta\) と仮定すると，\(S \nvdash \theta\) かつ \(T \vdash {\rm Pr}_S(\neg \theta)\). よって \(T \nvdash \neg {\rm Pr}_S(\neg \theta)\)．\(S\) における \(\neg \theta\) の証明を \(p\) とすると，\({\sf Q} \vdash {\rm Prf}_S(\neg \theta, p)\) かつ \({\sf Q} \vdash \forall y< p (\neg {\rm Prf}_S(\theta,y) \land \neg {\rm Prf}_T(\neg {\rm Pr}_S(\neg \theta),y))\)．つまり \({\sf Q} \vdash \forall y(p \leq y \rightarrow \exists z \leq y {\rm Prf}_S(\neg \theta,z))\) かつ \({\sf Q} \vdash \forall y(({\rm Prf}_S(\theta,y) \lor {\rm Prf}_T(\neg {\rm Pr}_S(\neg \theta),y)) \rightarrow p \leq y)\)．よって \({\sf Q} \vdash \theta\) つまり \(S \vdash \theta\) となり矛盾する． したがって \(S \nvdash \neg \theta\)．
• いま \(T \vdash \neg {\rm Pr}_S(\theta)\) または \(T \vdash \neg {\rm Pr}_S(\neg \theta)\) と仮定し，\(p\) を \(T\) における \(\neg {\rm Pr}_S(\theta)\) の証明または \(\neg {\rm Pr}_S(\neg \theta)\) の証明のうち最小のものとする．
  • \(p\) が \(\neg {\rm Pr}_S(\theta)\) の証明のとき，\({\sf Q} \vdash \forall y(p \leq y \rightarrow \exists z \leq y {\rm Prf}_T(\neg {\rm Pr}_S(\theta), z))\) かつ \({\sf Q} \vdash \forall y(({\rm Prf}_S(\theta,y) \lor {\rm Prf}_T(\neg {\rm Pr}_S(\neg \theta),y)) \rightarrow p \leq y)\)．よって \({\sf Q} \vdash \theta\) となり矛盾．
  • \(p\) が \(\neg {\rm Pr}_S(\neg \theta)\) の証明のとき，\({\sf Q} \vdash {\rm Prf}_T(\neg {\rm Pr}_S(\neg \theta), p)\) かつ \({\sf Q} \vdash \forall z \leq p (\neg {\rm Prf}_S(\neg \theta,z) \land \neg {\rm Prf}_T(\neg {\rm Pr}_S(\theta),z))\)．よって \({\sf Q} \vdash \neg \theta\) となり矛盾．
  したがって \(T \nvdash \neg {\rm Pr}_S(\theta)\) かつ \(T \nvdash \neg {\rm Pr}_S(\neg \theta)\)．