3.4

\(\Sigma_1\) 論理式 \(\exists y \rho(x, y)\) が \(T\) において \(X_1\) を correctly numerate するような PR 論理式 \(\rho(x, y)\) をとる． \(\xi(x)\) を，各 \(k\) 対して \[ {\sf Q} \vdash \xi(k) \leftrightarrow \exists y(\rho(k, y) \land \forall z \leq y \neg {\rm Prf}(\xi(k) \lor \xi_0(k), z)) \] を満たす \(\Sigma_1\) 論理式とする．

• \(k \in X_0\) とすると，\(T \vdash \xi_0(k)\) なので \(T \vdash \xi(k) \lor \xi_0(k)\) である．
• \(k \in X_1\) かつ \(T \nvdash \xi(k) \lor \xi_0(k)\) とする．\(\exists y \rho(x, y)\) が \(X_1\) を correctly numerate することから \(T \vdash \rho(k, l)\) となる \(l\) がとれる． したがって \(T \vdash \xi(k)\) となり，\(T \vdash \xi(k) \lor \xi_0(k)\) となるためおかしい． したがって \(k \in X_1\) ならば \(T \vdash \xi(k) \lor \xi_0(k)\) である．
• \(T \vdash \xi(k) \lor \xi_0(k)\) かつ \(n \notin X_1\) ならば \(T \vdash \neg \xi(k)\) なので \(T \vdash \xi_0(k)\) となる． よって \(k \in X_0\) がいえる． つまり \(T \vdash \xi(k) \lor \xi_0(k)\) ならば \(k \in X_0 \cup X_1\) である．

以上より \(\xi(x) \lor \xi_0(x)\) は \(T\) において \(X_0 \cup X_1\) を numerate することが分かった．

ここで \(\Sigma_n\) 論理式 \(\xi_1(x)\) を \[ \xi_1(x) = (\xi(x) \lor \xi_0(x)) \land \exists y \rho(x, y) \] と定める．

• 上で示した通り \(k \in X_1\) ならば \(T \vdash \xi(k) \lor \xi_0(k)\) かつ \(T \vdash \exists y \rho(k, y)\) なので \(T \vdash \xi_1(k)\) である．
• \(T \vdash \xi_1(k)\) ならば \(T \vdash \exists y \rho(k ,y)\) なので \(k \in X_1\) である．

したがって \(\xi_1(x)\) は \(T\) において \(X_1\) を numerate する．

\({\sf Q} \vdash \xi(k) \to \exists y \rho(k, y)\) であることを考えて変形すれば \begin{align*} {\sf Q} \vdash \xi_0(k) \lor \xi_1(k) & \leftrightarrow \xi_0(k) \lor (\xi(x) \lor \xi_0(x)) \land \exists y \rho(x, y)) \\ & \leftrightarrow \xi(k) \lor \xi_0(k) \end{align*} を得る． \(\xi(x) \lor \xi_0(x)\) は \(T\) において \(X_0 \cup X_1\) を numerate するので，\(\xi_0(x) \lor \xi_1(x)\) も \(T\) において \(X_0 \cup X_1\) を numerate する．