B. Turing’s and Feferman’s Results on Recursive Progressions

We will give a proof of Turing’s completeness Theorem 5.2 to be able to discuss its scope. Moreover, we shall also look at Feferman’s much stronger result about progressions based on the uniform reflection principle. As to the hierarchies that have been studied most frequently, please refer to section 5.2. The existence of primitive recursive functions $n\mapsto {\psi }_n$ in the definition of the different progressions is an easy consequence of the primitive recursion theorem.^[49] If all axioms of T a true (in the standard model) it can be shown for all $a\in \mathcal{O}$ by transfinite induction on $\left|a\right|$ that ${\mathbf{T}}_a$ is a true theory (in a sufficiently strong metatheory). For numbers a outside $\mathcal{O}$ the theories ${\mathbf{T}}_a$ bear no interest. They may actually be inconsistent. For example, the recursion theorem ensures that there exists an e such that $\{e\}(0)=\text{suc}(\lim (e))$. As ${\mathbf{T}}_{\{e\}(0)}\subseteq {\mathbf{T}}_{\lim (e)}$ and ${\mathbf{T}}_{\{e\}(0)}$ proves the consistency of ${\mathbf{T}}_{\lim (e)}$, both theories are inconsistent.

Recall that Turing’s completeness result, Theorem 5.2, asserts that for any true ${\mathrm{\Pi }}_1^0$ sentence $\varphi$ a number $a_{\varphi }\in \mathcal{O}$ with $\left|a_{\varphi }\right|=\omega +1$ can be constructed such that ${\mathbf{T}}_{a_{\varphi }}⊢\varphi$. Moreover, the function $\varphi \mapsto a_{\varphi }$ is primitive recursive. The proof proceeds as follows: Let $\theta$ be $\mathrm{\forall }x\psi (x)$ with $\psi$ primitive recursive. Define e by the recursion theorem such that, provably in PA,

Note that $\{e\}$ is total (by induction on n). As $\theta$ is true, we have $\{e\}(n)=n_{\mathcal{O}}$ for all n. Thus $\lim (e)$ belongs to $\mathcal{O}$ and $|\lim (e)|=\omega$. We claim that the consistency of ${\mathbf{T}}_{\lim (e)}$ entails that $\theta$ is true. For if $\theta$ were false we would have $\mathrm{\neg }\psi (\overline{m})$ for some m and thus ${\mathbf{T}}_{\{e\}(n)}={\mathbf{T}}_{\text{suc}(\lim (e))}$ for all $n\ge m$. But, by design, ${\mathbf{T}}_{\text{suc}(\lim (e))}$ proves the consistency of ${\mathbf{T}}_{\lim (e)}$ and ${\mathbf{T}}_{\{e\}(n)}$ is a subtheory of ${\mathbf{T}}_{\lim (e)}$ for all n. Thus ${\mathbf{T}}_{\lim (e)}$ would prove its own consistency, rendering it inconsistent (by Gödel’s second incompleteness theorem). The foregoing reasoning can be formalized in PA and a fortiori in ${\mathbf{T}}_{\text{suc}(\lim (e))}$. As a result, ${\mathbf{T}}_{\text{suc}(\lim (e))}⊢\theta$.

This proof is based on the trick of coding the truth of $\theta$ as a member of $\mathcal{O}$. It shows that the infinitely many iterated consistency axioms $\text{Con}({\mathbf{T}}_0),\text{Con}({\mathbf{T}}_1),\dots$ of ${\mathbf{T}}_{\text{suc}(\lim (e))}$ play no role in proving $\theta$. The reason why one has to go to stage $\omega +1$ is simply that only at stage $\omega$ a non-standard definition of the axioms of $\bigcup _{n<\omega }{\mathbf{T}}_n$ can be introduced. And actually a non-standard definition of the axioms of ${\mathbf{T}}_0$ would serve the same purpose. Setting $\vartheta (v_0):\iff \psi (v_0)\vee (\mathrm{\exists }x\mathrm{\neg }\psi (x)\wedge v_0=⌜0=1⌝)$, the theory ${\mathbf{T}}_0^{\prime }$ defined by the ${\mathrm{\Sigma }}_1^0$-formula $\vartheta$ has the same axioms as ${\mathbf{T}}_0$, but the consistency of ${\mathbf{T}}_0^{\prime }$ implies $\theta$ (provably so in PA). Also note that epistemologically recognizing that $\text{suc}(\lim (e))$ is in $\mathcal{O}$ hinges on us knowing that $\theta$ is true, and hence nothing is gained by further knowing that ${\mathbf{T}}_{\text{suc}(\lim (e))}⊢\theta$.

The proof of the Theorem 5.2 works with any consistency progression. Turing actually considered slightly stronger progressions in that he used a special version of local reflection progressions, where (R2) is restricted to ${\mathrm{\Pi }}_2^0$-sentences, i.e., sentences of $\mathrm{\forall }\mathrm{\exists }$ form with primitive recursive matrix. He took as one of his main aims to show that these progressions are complete for ${\mathrm{\Pi }}_2^0$-sentences. However, this is not the case as we have shown.

The problem left open after Turing’s thesis, namely whether any stronger progressions can be complete for ${\mathrm{\Pi }}_2^0$-statements, was addressed by Feferman (1962) with the surprising result that progressions based on the uniform reflection principle were not only complete with respect to ${\mathrm{\Pi }}_2^0$-sentences but for all arithmetical sentences.

In contrast to Turing’s result, Theorem 5.2, the proof of B.2 is rather difficult; it also utilizes a theorem from Shoenfield 1959 stating that Peano arithmetic with the recursive $\omega$-rule is complete for arithmetical statements.^[50] However, as far as mathematical knowledge is concerned, the same circularity as in Turing’s completeness theorem obtains in Theorem B.2 in that recognizing an $a\in \mathcal{O}$ with ${\mathbf{T}}_a⊢\psi$ is at least as hard as recognizing that $\psi$ is true. The starting point for constructing such an $a\in \mathcal{O}$ therefore is the truth of $\psi$ and as in Turing’s theorem one proceeds to cook up a via an application of the primitive recursion theorem, albeit this time a very intricate one.