Recursion-Theoretic Analogs

The results of §§1 and 2 are in the realm of hyperarithmetical theory. We now present the analogous results in the realm of recursion theory, concerning models of $\mathsf{WKL}_0$. For background on this topic, see Simpson [5, §§VIII.2 and XI.2].

Let REC denote the set of recursive reals. It is well known that, for any $\omega$-model M of $\mathsf{WKL}_0$, REC is properly included in M, and each $X\in\mathrm{REC}$ is definable in M. The recursion-theoretic analog of Theorem 1.1 is:

Theorem 3.1   There exists a countable $\omega$-model of $\mathsf{WKL}_0$ satisfying

$\forall X\,($if X is definable, then $X\in\mathrm{REC})$.

Proof.Use exactly the same construction and argument as for Theorem 1.1, replacing $\Sigma^1_1$ sets by $\Pi^0_1$ subsets of $2^\omega$.$\Box$

Remark 3.2   Theorem 3.1 is originally due to Friedman [2, Theorem 1.10, unpublished] (see also [3, Theorem 1.6]). It was later proved again by Simpson [6] (see also Simpson/Tanaka/Yamazaki [7]). All three proofs of Theorem 3.1 are different from one another.

Let $\le_T$ denote Turing reducibility, i.e., $X\le_TY$ if and only if X is computable using Y as an oracle. The recursion-theoretic analog of Theorem 1.3 is:

Theorem 3.3   There exists a countable $\omega$-model of $\mathsf{WKL}_0$ satisfying

$(**)\qquad\forall X\,\forall Y\,($if X is definable from Y, then $X\le_TY)$.

Proof.Use exactly the same construction and argument as for Theorem 1.3, replacing $\Sigma^1_1$ sets by $\Pi^0_1$ subsets of $2^\omega$.$\Box$

The recursion-theoretic analog of Theorems 2.4 and 2.7 is:

Theorem 3.4   $\mathsf{WKL}_0+(**)$ is conservative over $\mathsf{WKL}_0$ for arithmetical sentences.

Proof.The proof is analogous to the arguments of §2. $\Box$

Remark 3.5   Theorems 3.3 and 3.4 are originally due to Simpson [6]. The proofs given here are different from the proofs that were given in [6].