2.18

\(\tau(x)\) を \(T\) の PR binumeration とする. \(X\) は r.e. なので \(X = \{k : \exists m\ T \vdash \rho(k, m)\}\) となる PR 論理式 \(\rho(x, y)\) がとれる.

\({\sf PA} \vdash \tau^*(x) \leftrightarrow \tau(x) \land \forall z \leq x \neg \rho(\neg {\rm Con}_{\tau^*}, z))\)

となる PR 論理式 \(\tau^*(x)\) をとる.

いま \(\neg {\rm Con}_{\tau^*} \in X\) と仮定すると,ある \(m\) があって \(T \vdash \rho(\neg {\rm Con}_{\tau^*}, m)\) である. \(T \vdash \forall z \leq x \neg \rho(\neg {\rm Con}_{\tau^*}, z) \to x \leq m\) なので \(T \vdash \tau^*(x) \to \tau(x) \land x \leq m\) である. したがって Chapter 1 Fact 6 より \(T \vdash {\rm Con}_{\tau|m} \to {\rm Con}_{\tau^*}\) である. \(T\) は reflexive なので \(T \vdash {\rm Con}_{\tau|m}\) であるから,\(T \vdash {\rm Con}_{\tau^*}\) となる. これは \(X\) が monoconsistent with \(T\) であることに反する. したがって \(\neg {\rm Con}_{\tau^*} \notin X\) である.

上で示したことから,任意の \(k\) について \(T \vdash \forall z \leq k \neg \rho(\neg {\rm Con}_{\tau^*}, z)\) となる.

  • \(k \in X\) ならば \(T \vdash \tau(k) \land \forall z \leq k \neg \rho(\neg {\rm Con}_{\tau^*}, z)\) なので \(T \vdash \tau^*(k)\) である.
  • \(k \notin X\) ならば \(T \vdash \neg \tau(k)\) なので \(T \vdash \neg \tau^*(k)\) である.

よって \(\tau^*(x)\) は \(T\) の PR binumeration である.