(a)
\(T \nvdash \varphi\) となる \(\Gamma\) 文 \(\varphi\) と再帰的関数 \(f\) に対して，そのような \(\Gamma\) 文 \(\theta\) がとれないと仮定する． すなわち，任意の \(\Gamma\) 文 \(\theta\) について，\(T \vdash \theta\) でありかつ \(q\) が \(T +
\varphi\) における \(\theta\) の証明ならば，\(f(q)\) 以下に \(T\) における \(\theta\) の証明が取れるとする．
\(g(\psi)\) を \(T + \varphi\) における \(\varphi \lor \psi\) の証明とすると，\(g(x)\) は再帰的関数である． \(\psi\) を任意の \(\Gamma\) 文とする．
したがって \begin{align*} T + \neg \varphi \vdash \psi & \iff T \vdash \varphi \lor \psi \\ & \iff f(g(\psi))\ \text{以下に}\ T\ \text{における}\ \varphi \lor \psi\ \text{の証明がある．} \end{align*}
となるため，\({\rm Th}(T + \neg \varphi) \cap \Gamma\) は再帰的である． よって \(T + \neg \varphi\) において \({\rm Th}(T + \neg \varphi) \cap \Gamma\) を binumerate する \(\Gamma^d\) 論理式 \(\tau(x)\) がとれる． \[ {\sf Q}
\vdash \gamma \leftrightarrow \neg \tau(\gamma) \] となる \(\Gamma\) 文 \(\gamma\) をとる． このとき \begin{align*} T + \neg \varphi \vdash \gamma & \Rightarrow \gamma \in {\rm Th}(T + \neg \varphi) \cap
\Gamma \\ & \Rightarrow T + \neg \varphi \vdash \tau(\gamma)\\ & \Rightarrow T + \neg \varphi \vdash \neg \gamma \end{align*} \begin{align*} T + \neg \varphi \nvdash \gamma &
\Rightarrow \gamma \notin {\rm Th}(T + \neg \varphi) \cap \Gamma \\ & \Rightarrow T + \neg \varphi \vdash \neg \tau(\gamma)\\ & \Rightarrow T + \neg \varphi \vdash \gamma \end{align*} なので
\(T + \neg \varphi \vdash \gamma\) と \(T + \neg \varphi \nvdash \gamma\) のいずれの場合も矛盾する．
以上より，条件を満たす \(\gamma\) 文 \(\theta\) がとれることが分かった．
(b)
\(T \nvdash \varphi\) となる文 \(\varphi\) と再帰的関数 \(f\) をとる． \({\sf Q}\) において \(f\) を define する \(\Sigma_1\) 論理式 \(\delta_f(x, y)\) をとる． \[ {\sf Q} \vdash \psi \leftrightarrow \exists y \exists
u({\rm Prf}_{T+\varphi}(\varphi \lor \psi, y) \land \forall z < y \neg {\rm Prf}_{T + \varphi}(\varphi \lor \psi, z) \land \delta_f(y, u) \land \forall v \leq u \neg {\rm Prf}_T(\varphi \lor
\psi, v)) \] を満たす \(\Sigma_1\) 文 \(\psi\) をとる．
したがって \(T + \varphi\) における \(\varphi \lor \psi\) の最小の証明 \(p\) に対して，\(f(p)\) 以下に \(T\) における \(\varphi \lor \psi\) の証明はない．