(a)
- \(k \in X_0\) とする．\(\rho_0\) のとり方より，ある \(m\) が存在して \({\sf Q} \vdash \rho_0(k,m)\)．一方 \(X_0\) と \(X_1\) は disjoint なので \(k \notin X_1\) である．したがって \(\rho_1\) のとり方より，任意の \(n\) について \({\sf Q}
\nvdash \rho_1(k,n)\)．\(\rho_1\) は PR 論理式なので \({\sf Q} \vdash \forall z \leq m \neg \rho_1(k,z)\) となるため \({\sf Q} \vdash \xi(k)\) である．
- \(k \in X_1\) とする． 先ほどと同様に，ある \(m\) について \({\sf Q} \vdash \rho_1(k,m)\) かつ \({\sf Q} \vdash \forall y < m \neg \rho_0(k,y)\)． つまり \({\sf Q} \vdash \forall y(m \leq y \rightarrow \exists z
\leq y \rho_1(k,z))\) かつ \({\sf Q} \vdash \forall y(\rho_0(k,y) \rightarrow m \leq y)\)． したがって \({\sf Q} \vdash \neg \xi(k)\) となる．
(b)
\(X_0\), \(X_1\) を recursively inseparable な r.e. 集合とすると，\(X_0\) と \(X_1\) に対して (a) の条件を満たす \(\Sigma_1\) 論理式 \(\xi(x)\) がとれる．
- \(Y_0 = \{k : T \vdash \xi(k)\}\)
- \(Y_1 = \{k : T \vdash \neg \xi(k)\}\)
とすると \(Y_0\) と \(Y_1\) は \(X_0 \subseteq Y_0\), \(X_1 \subseteq Y_1\), \(Y_0 \cap Y_1 = \emptyset\) を満たす r.e. 集合である．
いま \(Y_0 \cup Y_1 = \omega\) と仮定すると，\(Y_0 \cap Y_1 = \emptyset\) なので \(Y_0 = \omega \setminus Y_1\) であり \(Y_0\) は recursive となる． \(X_0 \subseteq Y_0\) かつ \(X_1 \cap Y_0 = \emptyset\) なので \(X_0\),
\(X_1\) の recursively inseparability に反する． したがって \(Y_0 \cup Y_1 \neq \omega\) である．
\(k \notin Y_0 \cup Y_1\) をとれば \(T \nvdash \xi(k)\) かつ \(T \nvdash \neg \xi(k)\) である． また \(\xi(k)\) が true とすると \(\xi(k)\) は \(\Sigma_1\) なので \(T \vdash \xi(k)\) となるためおかしい． 以上より \(\neg \xi(k)\) は
\(T\) において undecidable かつ true な \(\Pi_1\) 文である．
(c)
- \(X_0 = \{\varphi \in \Pi_1 : T \vdash \varphi\}\)
- \(X_1 = \{\varphi \in \Sigma_1 : T \vdash \varphi\}\)
とする．
- \(X_0\) が recursive であると仮定すると，Corollary 1.3(a) より \(X_0\) を \(T\) において binumerate する \(\Sigma_1\) 論理式 \(\xi(x)\) が存在する． いま \(\Pi_1\) 文 \(\pi\) を
\({\sf Q} \vdash \pi \leftrightarrow \neg \xi(\pi)\)
となるようにとると
\(\pi \in X_0 \iff T \vdash \pi \iff T \vdash \neg \xi(\pi) \iff \pi \notin X_0\)
となるため矛盾する． よって \(X_0\) は recursive でない．
- \(X_1\) が recursive であると仮定すると，\(X_1\) を \(T\) において binumerate する \(\Pi_1\) 論理式がとれるため，同様に矛盾する． よって \(X_1\) は recursive ではない．