3.2

(a)
\(T_1 \vdash \theta\) かつ \(T_0 \nvdash \theta\) となる文 \(\theta\) をとる． \(T_0 + \neg \theta\) において \(X_0\) を numerate する論理式 \(\xi_0(x)\) をとる． いま \(T_0 \dashv T_1\) なので Exercse 3.1 より \(T_0\) と \(T_1\) において \(X_1\) を numerate する論理式 \(\xi_1(x)\) がとれる． \[ \xi(x) = \xi_1(x) \land (\theta \lor \xi_0(x)) \] と定める．

• \(n \in X_0\) ならば \(T_0 + \neg \theta \vdash \xi_0(n)\) なので \(T_0 \vdash \theta \lor \xi_0(n)\) である． また \(X_0 \subseteq X_1\) より \(n \in X_1\) なので \(T_0 \vdash \xi_1(n)\) である． したがって \(T_0 \vdash \xi(n)\) がいえた．
• \(T_0 \vdash \xi(n)\) ならば \(T_0 \vdash \theta \lor \xi_0(n)\) なので \(T_0 + \neg \theta \vdash \xi_0(n)\) となり \(n \in X_0\) がいえる．
• \(n \in X_1\) ならば \(T_1 \vdash \xi_1(n)\) である． また \(T_1 \vdash \theta\) なので \(T_1 \vdash \theta \lor \xi_0(n)\) である． したがって \(T_1 \vdash \xi(n)\) となる．
• \(T_1 \vdash \xi(n)\) ならば \(T_1 \vdash \xi_1(n)\) なので \(n \in X_1\) である．

以上より \(\xi(x)\) は \(T_0\) と \(T_1\) のそれぞれにおいて \(X_0\) と \(X_1\) を numerate する．

(b)
各 \(i < n\) について，\(T_i \nvdash \theta_i\) かつ \(T_{i+1} \vdash \theta_i\) となる文 \(\theta_i\) をとる． このとき \({\sf Q} \dashv T_0 + \neg \theta_i \dashv \cdots \dashv T_i + \neg \theta_i\) なので Exercise 3.1 のコメントより，全ての \(T_j + \neg \theta_i\) (\(j \leq i\))において \(X_i\) を numerate する論理式 \(\xi_i(x)\) がとれる． また \({\sf Q} \dashv T_0 \dashv \cdots \dashv T_n\) なので再び Execise 3.1 のコメントより，全ての \(T_i\) において \(X_n\) を numerate する論理式 \(\xi_n(x)\) がとれる． \[ \xi(x) = \xi_n(x) \land \bigwedge_{i < n}(\theta_i \lor \xi_i(x)) \] と定める． \(i < n\) とする．

• \(k \in X_i\) とする．
  • \(j < i\) について \(T_i \vdash \theta_j\) なので \(T_i \vdash \theta_i \lor \xi_j(k)\).
  • \(i \leq j < n\) について \(T_i + \neg \theta_j \vdash \xi_j(k)\) なので \(T_1 \vdash \theta_j \lor \xi_j(k)\) である．
  • \(k \in X_n\) なので \(T_i \vdash \xi_n(k)\) である．
  以上より \(T_i \vdash \xi(k)\) となる．
• \(T_i \vdash \xi(k)\) ならば \(T_i \vdash \theta_i \lor \xi_i(k)\) なので \(T_i + \neg \theta_i \vdash \xi_i(k)\) となり \(k \in X_i\) がいえる．
• \(k \in X_n\) ならば \(T_n \vdash \xi_n(k)\) である． また \(T_n \vdash \bigwedge_{j < n}\theta_j\) なので \(T_n \vdash \bigwedge_{j < n}(\theta_j \lor \xi_j(k))\) である． したがって \(T_n \vdash \xi(k)\) となる．
• \(T_n \vdash \xi(k)\) ならば \(T_n \vdash \xi_n(k)\) なので \(k \in X_n\) である．

以上より \(\xi(x)\) は各 \(T_i\) において \(X_i\) を numerate する．

(c)
\(T_1 \vdash \theta\) とする． \[ {\sf Q} \vdash \varphi \leftrightarrow \neg \sigma(\theta \lor \varphi) \] を満たす文 \(\varphi\) をとる．

\(T_0 \dashv T_0 + \theta \dashv T_1\) であるから，\(\sigma(x)\) は \(T_0 + \theta\) において \({\rm Th}(T_0 + \theta)\) を numerate する． \(T_0 + \theta \vdash \theta \lor \varphi\) なので \(T_0 + \theta \vdash \sigma(\theta \lor \varphi)\) となり，\(T_0 + \theta \vdash \neg \varphi\) である．

つまり \(T_0 \dashv T_0 + \neg \varphi \dashv T_1\) であるから，\(\sigma(x)\) は \(T_0 + \neg \varphi\) において \({\rm Th}(T_0 + \neg \varphi)\) を numerate する． \(T_0 + \neg \varphi \vdash \neg \varphi\) なので \(T_0 + \neg \varphi \vdash \sigma(\theta \lor \varphi)\) であり，\(T_0 + \neg \varphi \vdash \theta \lor \varphi\) となる． よって \(T_0 + \neg \varphi \vdash \theta\) である．

以上より \(T_0 \vdash \theta \lor \varphi\) がいえた． \(\sigma(x)\) は \(T_0\) において \({\rm Th}(T_0)\) を numerate するので，\(T_0 \vdash \sigma(\theta \lor \varphi)\) だから \(T_0 \vdash \neg \varphi\) である． したがって \(T_0 \vdash \theta\) となる．

以上のことから \(T_1 \dashv T_0\) が分かった．

(d)
\(i = 0, 1\) とする． \(T_i \vdash \theta_i\) かつ \(T_{1-i} \nvdash \theta_i\) となる文 \(\theta_i\) がとれる． \(T_i \dashv T_i + \neg \theta_{1 - i}\) なので Exercise 3.1 より \(T_i\) と \(T_i + \neg \theta_{1-i}\) の両方において \(X_i\) を numerate する論理式 \(\xi_i(x)\) がとれる． \[ \xi(x) = (\xi_0(x) \lor \theta_1) \land (\xi_1(x) \lor \theta_0) \] と定める．

• \(n \in X_i\) とすると \(T_i \vdash \xi_i(n) \land \theta_i\) なので \(T_i \vdash \xi(n)\) である．
• \(T_i \vdash \xi(n)\) とすると \(T_i \vdash \xi_i(n) \lor \theta_{1-i}\) である． \(T_i + \neg \theta_{1 - i} \vdash \xi_i(n)\) なので \(n \in X_i\) である．

以上より \(\xi(x)\) は \(T_i\) において \(X_i\) を numerate する．