(a)
\(\Sigma_1\) 文 \(\sigma_0\) と \(\sigma_1\) を \[ T \vdash \sigma_0 \leftrightarrow \exists y ({\rm Prf}({\rm Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1), y) \land \forall z \leq g(y) \neg {\rm Prf}({\rm
Pr}(\sigma_0), z)) \lor \exists u({\rm Prf}({\rm Pr}(\sigma_0), u) \land \forall v \leq u \neg {\rm Prf}({\rm Pr}(\sigma_1), v)), \] \[ T \vdash \sigma_1 \leftrightarrow \exists y ({\rm Prf}({\rm
Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1), y) \land \forall z \leq g(y) \neg {\rm Prf}({\rm Pr}(\sigma_1), z)) \lor \exists v({\rm Prf}({\rm Pr}(\sigma_1), v) \land \forall u < v \neg {\rm
Prf}({\rm Pr}(\sigma_0), u)), \] を満たすものとして取る． \begin{align*} T \vdash {\rm Pr}({\rm Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1)) \land \neg {\rm Pr}({\rm Pr}(\sigma_0)) & \to \sigma_0 \\ & \to
{\rm Pr}(\sigma_0)\\ & \to {\rm Pr}({\rm Pr}(\sigma_0)) \end{align*} なので \[ T \vdash {\rm Pr}({\rm Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1)) \to {\rm Pr}({\rm Pr}(\sigma_0)) \] である． また \[ T
\vdash {\rm Pr}({\rm Pr}(\sigma_0)) \to \exists u({\rm Prf}({\rm Pr}(\sigma_0), u) \land \forall v \leq u \neg {\rm Prf}({\rm Pr}(\sigma_1), v)) \lor \exists v({\rm Prf}({\rm Pr}(\sigma_1), v)
\land \forall u < v \neg {\rm Prf}({\rm Pr}(\sigma_0), u)) \] であるから， \[ T \vdash {\rm Pr}({\rm Pr}(\sigma_0)) \to \sigma_0 \lor \sigma_1 \] となる． したがって \begin{align*} T \vdash {\rm Pr}({\rm
Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1)) & \to \sigma_0 \lor \sigma_1\\ & \to {\rm Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1) \end{align*} なので Löb の定理より \(T \vdash {\rm Pr}(\sigma_0) \lor {\rm
Pr}(\sigma_1)\) となる． \(T\) における \({\rm Pr}(\sigma_0) \lor {\rm Pr}(\sigma_1)\) の最小の証明 \(p\) をとる．
\(T\) における \({\rm Pr}(\sigma_0)\) と \({\rm Pr}(\sigma_1)\) の証明をそれぞれ \(q_0, q_1\) とする．
以上より \(g(p)\) 以下に \({\rm Pr}(\sigma_0)\) と \({\rm Pr}(\sigma_1)\) の証明は存在しない．
(b)
まず \(g\) は provably increasing としてよい． \(\Sigma_1\) 文 \(\chi_0\) と \(\chi_1\) を \[ T \vdash \chi_0 \leftrightarrow \exists y ({\rm Prf}({\rm Pr}(\chi_0) \lor {\rm Pr}(\chi_1), y) \land \forall z
\leq g(y) \neg {\rm Prf}({\rm Pr}(\chi_0), z)), \] \[ T \vdash \chi_1 \leftrightarrow \exists z({\rm Prf}({\rm Pr}(\chi_0), z) \land \forall y < z(g(y) < z \to \neg {\rm Prf}({\rm
Pr}(\chi_0) \lor {\rm Pr}(\chi_1), y)), \] を満たすものとして取る． \(g\) は provably increasing なので \(T \vdash \chi_0 \to \neg \chi_1\) である． \begin{align*} T \vdash {\rm Pr}({\rm Pr}(\chi_0) \lor {\rm
Pr}(\chi_1)) & \to \chi_0 \lor \chi_1\\ & \to {\rm Pr}(\chi_0) \lor {\rm Pr}(\chi_1) \end{align*} なので Löb の定理より \(T \vdash {\rm Pr}(\chi_0) \lor {\rm Pr}(\chi_1)\) である． \(T\) における \({\rm
Pr}(\chi_0) \lor {\rm Pr}(\chi_1)\) の最小の証明を \(p\) とする．
いま \(T \nvdash {\rm Pr}(\chi_0)\) と仮定すると，\(T \vdash {\rm Prf}({\rm Pr}(\chi_0) \lor {\rm Pr}(\chi_1), p) \land \forall z \leq g(p) \neg {\rm Prf}({\rm Pr}(\chi_0), z)\) なので \(T \vdash \chi_0\)，つまり \(T \vdash {\rm Pr}(\chi_0)\) となるためおかしい． したがって \(T \vdash {\rm Pr}(\chi_0)\) である． \(T\) は \(\Sigma_1\)-健全なので \(T \vdash \chi_0\) である． したがって \(T \vdash \neg \chi_1\) となる．
\(T\) における \({\rm Pr}(\chi_0)\) の最小の証明を \(q\) とする． \(q \leq g(p)\) と仮定すると，\(T \vdash \neg \chi_0\) となるためおかしい． したがって \(g(p) < q\) であり，つまり \(g(p)\) 以下に \({\rm Pr}(\chi_0)\) の証明は存在しない．
ヒント通りにやっていない．