(a)
\(\delta_f(x, y)\) を \({\sf Q}\) において \(f\) を define する \(\Sigma_1\) 論理式とする． \[ {\sf Q} \vdash \varphi \leftrightarrow \exists y (\delta_f(\varphi, y) \land \forall z \leq y \neg {\rm
Prf}(\varphi, z)) \] を満たす \(\Sigma_1\) 文 \(\varphi\) をとる．
- \(T \nvdash \varphi\) と仮定すると，\({\sf Q} \vdash \delta_f(\varphi, f(\varphi)) \land \forall z \leq f(\varphi) \neg {\rm Prf}(\varphi, z))\) なので \({\sf Q} \vdash \varphi\) となるためおかしい． したがって \(T
\vdash \varphi\) である．
- \(T\) における \(\varphi\) の証明 \(p\) で \(p \leq f(\varphi)\) となるものがあると仮定すると，\({\sf Q} \vdash \exists z \leq f(\varphi) {\rm Prf}(\varphi, z)\) かつ \({\sf Q} \vdash \forall y(\delta_f(\varphi, y)
\leftrightarrow y =f(\varphi))\) なので \({\sf Q} \vdash \neg \varphi\) となるためおかしい． したがって \(T\) における \(\varphi\) の最小の証明は \(f(\varphi)\) より大きい．
(b)
\(\delta_f(x, y)\) を \({\sf Q}\) において \(f\) を define する \(\Sigma_1\) 論理式とする． 全ての \(n \in \mathbb{N}\) について \[ {\sf Q} \vdash \xi(n) \leftrightarrow \forall y (\delta_f(n, y) \to \forall z \leq y
\neg {\rm Prf}(\xi(n), z)) \] を満たす \(\Pi_1\) 論理式 \(\xi(x)\) をとる．
- \(T \nvdash \xi(n)\) と仮定すると，\({\sf Q} \vdash \forall z \leq f(n) \neg {\rm Prf}(\xi(n), z)\) かつ \({\sf Q} \vdash \forall y(\delta_f(n, y) \leftrightarrow y = f(n))\) なので \({\sf Q} \vdash
\xi(n)\) となるためおかしい． したがって \(T \vdash \xi(n)\) である．
- \(T\) における \(\xi(n)\) の証明 \(p\) で \(p \leq f(n)\) となるものが取れるとすると，\({\sf Q} \vdash \delta_f(n, f(n)) \land \exists z \leq f(n) {\rm Prf}(\xi(n), z)\) なので \({\sf Q} \vdash \neg \xi(n)\)
となるためおかしい． したがって \(T\) における \(\xi(n)\) の最小の証明は \(f(n)\) より大きい．