3.1

Theorem 1' より,\(T_1\) において \(X\) を correctly numerate する \(\Sigma_1\) 論理式 \(\xi(x)\) がとれる. このとき \[ T_1 \vdash \xi(n) \iff n \in X \] である. また \begin{align*} T_0 \vdash \xi(n) & \Rightarrow T_1 \vdash \xi(n) \\ & \Rightarrow \xi(n)\ \text{は true}\\ & \Rightarrow T_0 \vdash \xi(n) \end{align*} なので \[ T_0 \vdash \xi(n) \iff T_1 \vdash \xi(n) \] となるため, \[ T_0 \vdash \xi(n) \iff n \in X \] も成り立つ.


コメント

この結果は次のように拡張できる.

\({\sf Q} \dashv T_0 \dashv \cdots \dashv T_n\) とすると,各 r.e. 集合 \(X\) に対して,全ての \(T_i\) において \(X\) を numerate する \(\Sigma_1\) 論理式 \(\xi(x)\) が存在する.

\(\because\)

\(T_n\) において \(X\) を correctly numerate する \(\Sigma_1\) 論理式 \(\xi(x)\) をとる. このとき \[ k \in X \iff T_n \vdash \xi(k) \] である. また各 \(i < n\) について \begin{align*} T_i \vdash \xi(k) & \Rightarrow T_n \vdash \xi(k) \\ & \Rightarrow \xi(k)\ \text{は true}\\ & \Rightarrow T_i \vdash \xi(k) \end{align*} なので \[ T_i \vdash \xi(k) \iff T_n \vdash \xi(k) \] となるため, \[ T_i \vdash \xi(k) \iff k \in X \] も成り立つ. よって \(\xi(x)\) は全ての \(T_i\) において \(X\) を numerate する.