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 . 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 -model *M* of
,
REC is properly included in
*M*, and each
is definable in *M*. The recursion-theoretic
analog of Theorem 1.1 is:

if *X* is definable, then
.

*Proof.*Use exactly the same construction and argument as for Theorem
1.1, replacing
sets by
subsets
of .

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

if *X* is definable from
*Y*, then .

*Proof.*Use exactly the same construction and argument as for Theorem
1.3, replacing
sets by
subsets
of .

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

*Proof.*The proof is analogous to the arguments of §2.