Next: Some Additional Results Up: A Symmetric -Model Previous: Conservation Results

# 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:

Theorem 3.1   There exists a countable -model of satisfying
if X is definable, then .

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

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 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:

Theorem 3.3   There exists a countable -model of satisfying
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:

Theorem 3.4   is conservative over for arithmetical sentences.

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

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].

Next: Some Additional Results Up: A Symmetric -Model Previous: Conservation Results
Stephen G Simpson
2000-05-23