INTERPRETING ARITHMETIC IN THE R.E. DEGREES UNDER Σ_{4}-INDUCTION

C. T. CHONG, RICHARD A. SHORE AND YUE YANG

Abstract. We study the problem of the interpretability of arithmetic in the r.e. degrees in models of fragments of Peano arithmetic. The main result states that there is an interpretation φ ↦ φ^{∗} such that every formula φ of Peano arithmetic corresponds to a formula φ^{∗} in the language of the partial ordering of r.e. degrees such that for every model N of Σ_{4}-induction, N ⊧ φ if and only if R_{N} ⊧ φ^{∗}, where R_{N} is the structure whose universe is the collection of r.e. degrees in N. This supplies, for example, statements φ_{m} about the r.e. degrees which are equivalent (over IΣ_{4}) to IΣ_{m} for every m > 4.

§1. Introduction. A basic goal of reverse mathematics is to determine the axiom systems needed to prove particular theorems of mathematics by showing that they are equivalent (over a given base theory) to some specific axiom system. (See [12] for a general introduction to reverse mathematics in the setting of second order arithmetic.) In reverse recursion theory our setting is first order arithmetic and the axiom systems considered are those that include, in addition to the axioms P A^{−} of Peano arithmetic (P A) without induction, the various syntactic levels of induction and bounding axioms, IΣ_{n} and BΣ_{n}, which assert the induction scheme and bounding principle, respectively, for Σ_{n} formulas. (We refer the reader to [3] or [4] for the basic notions of recursion theory in fragments of arithmetic, and to a summary of recent results in the theory.)

The typical goal of reverse recursion theory then is to find recursion theoretic theorems, usually about the r.e. degrees, that are equivalent to IΣ_{n} over some weaker base theory. Examples include the equivalence of the Sacks Splitting Theorem for r.e. degrees with IΣ_{1} (over BΣ_{1}) [7] and of a minimal pair of r.e. degrees with IΣ_{2} (over BΣ_{2}) [2]. Recent work in [14] supplies a similar example for IΣ_{3}. In this paper, we show that over the base theory IΣ_{4} there are sentences φ_{m} about the r.e. degrees which are equivalent to IΣ_{m} for each m > 4. (Of course, these sentences are thus all theorems of P A.) Our proof proceeds by analyzing and extending some of the results of [9] about the definability of (a copy of) the standard model of arithmetic in the r.e. degrees, so as to be able to carry out the necessary arguments in IΣ_{4} to provide an interpretation in the r.e. degrees not of the standard model itself, but only its theory. (The interpretation of the model itself seems to require more induction.) Of course, this suffices for our equivalence results and more. We begin with some background and an outline of our approach.

1991 Mathematics Subject Classification. Primary 03B30, 03D25, 03F30; Secondary 03B25, 03D25, 03D75.

Key words and phrases. reverse mathematics, fragments of arithmetic, recursively enumerable degrees, interpretability of arithmetic.

Richard A. Shore was partially supported by NSF Grant DMS-9802843 and a Visiting Distinguished Professorship at the National University of Singapore.

Meeting \begin{matrix}c \\ ◯ \end{matrix} 1000, Association for Symbolic Logic

Let R denote the collection of recursively enumerable (r.e.) degrees of the set of natural numbers with the partial ordering induced by Turing reducibility. In [9], Nies, Shore and Slaman show that there is an interpretation (in the sense of [5]) of the standard model of arithmetic in R. As a consequence, true arithmetic can be interpreted in Th(R). Since there is an obvious interpretation of R in the standard model, it follows that Th(R) is precisely as complicated as true arithmetic. They also use this interpretation to establish the definability of the classes of high_{n} and low_{n+1} degrees (for n ≥ 1) as well as a weak form of the bi-interpretability conjecture ([9], [8]), that there is a map f definable over R with the property that for each a ∈ R, f(a) is the index (in the code of the standard model in R) of an r.e. set W_{e} such that W′′_{e} has Turing degree a′′.

This interpretation of the standard model in R is achieved through a series of coding schemes each of which defines a class of structures in R. Briefly, a coding scheme S(p⃗) is prescribed via first order formulas (in the language of R) φ_{0}(x, p⃗), φ_{1}(x⃗, p⃗), φ_{2}(x⃗, p⃗), …, φ_{k}(x⃗, p⃗) and ψ(p⃗) where p⃗ denotes a finite sequence of elements of R, and φ_{0} specifies the domain of the structure being defined. The formulas φ_{i}, 0 < i ≤ k, correspond to functions or relations such as addition and multiplication or order which are defined on the domain specified by φ_{0} to make it into the desired type of structure. The formula ψ is a correctness condition which ensures that structures coded by the scheme satisfy certain properties (for example, that the appropriate formulas define functions when so required or that, in addition, the structures defined by such a scheme are models of some finite fragment of Peano arithmetic or even isomorphic to the standard model). For a given coding scheme S, we refer to the structures defined by instances of the parameters p⃗ that satisfy the correctness condition ψ as the models coded via S. For more details and relevant examples see [5] and [9].

We show in this paper that if N is a model of a fragment T of Peano arithmetic including Σ_{4}-induction and R_{N} is the structure of r.e. degrees of N, then there exists an interpretation of Th(N) in R_{N}, i.e. a recursive map φ ↦ φ^{∗} taking formulas φ of Peano arithmetic to ones φ^{∗} in the language of the partial ordering of r.e. degrees, such that N ⊧ φ if and only if R_{N} ⊧ φ^{∗}. A consequence of this is that for n > m ≥ 4, if N_{n} is a model of Σ_{n}-induction, and N_{m} is a model of Σ_{m}-induction but not of Σ_{n}-induction, then the structures R_{N_{n}} and R_{N_{m}} are not elementarily equivalent. More precisely, since we can express the scheme of IΣ_{m} induction by a single formula ψ_{m}, there is a formula ψ_{m}^{∗} in the language of R such that N satisfies IΣ_{m} induction if and only if R_{N} ⊧ ψ_{m}^{∗}. Combining these results with recent ones in [2] and [14], the only case of the general question of whether the amount of induction true in N is faithfully reflected in Th(R_{N}) is when n ≥ 4 and m = 3. We discuss this further in the next section.

There are essentially two key steps to establishing the interpretability of true arithmetic in Th(R). The first involves coding the standard model in R. A basic technique for achieving this is provided by Slaman and Woodin in the construction of what are called SW (Slaman-Woodin) sets. An SW-set ([9]) is defined from a finite set of parameters: Given r.e. degrees b, p, q and r, the Slaman-Woodin set coded by b, p, q, r is the set of minimal elements of {x|b ≤_{T} x ≤_{T} r & q ≤_{T} x ∨ p}. If the parameter b is omitted, we take it to be 0. As shown by Slaman and Woodin, given a recursive partial ordering ≤_{P} one may construct a uniformly r.e. sequence (an SW-set with b = 0) {g_{i}|i ∈ ω} of r.e. degrees and an l ∈ R such that i ≤_{P} j if and only if g_{i} ≤_{T} g_{j} ∨ l. Thus we can define a coding scheme and parameters that determine a recursive coding of the standard model of arithmetic in R by combining the Slaman-Woodin coding of partial orderings with the standard interpretation of an arbitrary theory (here arithmetic) in that of partial orderings.

The second step is to obtain a first order condition on parameters that picks out a subclass of models coded in R which are standard. This is achieved via a Comparison Theorem which identifies, through a coding scheme, a class of models isomorphic to the standard model. Of course, identifying a definable class of models isomorphic to the standard one gives an interpretation of true arithmetic in the theory of R.

In this paper we are generally guided by this approach in dealing with the problem at hand. There are, however, some obvious issues and difficulties which have to be resolved. First, the term ‘standard model’ now carries a different meaning. Since one is considering an arbitrary model of a first-order theory (a fragment of Peano arithmetic), which more than likely is itself nonstandard, ‘standard’ has to be understood in the relative sense, using the given model N as reference. In such a situation, it is necessary to exercise control on the order type of the models to be considered so that, in order to apply the Comparison Theorem, only those which are end-extensions of N matter. Second, working with limited mathematical induction always poses the challenge of controlling the complexity of the constructions involved, to ensure that the coding scheme to be defined stays within manageable level, i.e. the constraint of Σ_{4}-induction.

In the next section, we present the coding mechanism and the technical theorems and lemmas needed to make it work. Assuming the technical recursion theoretic results, we prove (in IΣ_{4}) that the coding procedures provide an interpretation of the theory of arithmetic in the r.e. degrees and draw some conclusions about reverse recursion theory and the relations between the theory of the r.e. degrees in a model N and the amount of induction that holds in N. The technical theorems and lemmas are proven in §3.

§2. Coding Schemes Under IΣ_{4}. Let N be a model of IΣ_{4}. We work towards finding a coding scheme S and a formula Ψ in the language of the partial ordering of r.e. degrees such that for appropriate degrees c, any finite set of parameters p⃗ below c which satisfy Ψ code a model M of arithmetic lying below c which is also a copy of N (known as models ‘good for c’). The formula Ψ plays the role of a correctness condition for the coding scheme to be used for interpreting the theory of N in R_{N} by picking out a class of coded models which are isomorphic to N when c is low. (We will then get our desired interpretation of Th(N) by quantifying out the parameter c in an appropriate way.) The development of S and Ψ proceeds in several steps.

We begin with the initial coding scheme from [9]. As described above, this takes as its parameters degrees b, p, q, r and l such that b, p, q and r define a Slaman-Woodin set G, and l defines an ordering ≤_{P} on G which codes a model of a finite fragment of P A sufficient for the simple facts about arithmetic that we will need (one implying IΣ_{1} is more than sufficient) on a subset M of G, using an interpretation of structures for arithmetic in partial orderings. Much of what we do to adapt the codings of [9] will be done to reduce the complexity of various statements about the coded models so as to reduce the amount of induction needed in our verifications.

We begin by assuming that the partial ordering P used to code arithmetic has specific elements s, s_{0} and s_{1} such that the elements of the model of arithmetic coded in P are precisely those below s and the even and odd ones (in the sense of the model of arithmetic) are those below s_{0} and s_{1} respectively. (In addition, we note that the coding presented in [9] makes the minimal elements of P be the domain of the coded model of arithmetic.) Thus the Slaman-Woodin set G has specific elements s, s_{0} and s_{1} such that the elements of M are precisely those x ∈ G satisfying x ≤_{T} s ∨ l and the even (odd) numbers of M are precisely those x ∈ G satisfying x ≤_{T} s_{0} ∨l (x ≤_{T} s_{1} ∨l). We include these elements s, s_{0} and s_{1} among the parameters of our coding scheme, and the assertions about their picking out the appropriate sets of numbers in M as part of our correctness condition.

The next new aspect of our coding scheme that we want to make explicit is the introduction of another parameter l′ which codes a second partial order on G that coincides with the ordering of M. To be precise, we add the parameter l′ and the correctness condition asserting that for x, y ∈ M, x ≤_{T} y ∨ l′ if and only if x ≤_{M} y.

We start our search then with a coding scheme S_{0} and associated correctness condition ψ_{0} with all these properties. All coding schemes considered from now on are assumed to be extensions of S_{0}. If M is a model coded by some scheme S, i ∈ N and there is (in the sense of N) an ith element in the ordering ≤_{M}, then we denote this element by i^{M}.

Now, given a sufficient amount of induction, the Slaman-Woodin construction as given in [9] may be used to show that there are parameters which, via S_{0}, code a recursive model M in R_{N} that is isomorphic to N. However, definably picking out copies of N is considerably more complicated. We continue with a definition that reflects our goal of determining a subclass of the models coded by a scheme S which are isomorphic to N.

Definition 2.1. Let C be the class of models of arithmetic coded in R_{N} by some coding scheme S. Then N ∈ C is N -standard for C if N is isomorphic to N and the domain of N is isomorphic to an initial segment of the domain of every M ∈ C.

Our goal is to definably (at least in an appropriate parameter) determine a set of models which are N -standard for some (coded) class C. The need to restrict the complexity of various definitions, so as to reduce the amount of induction needed for verifications, drives us to a more complicated mechanism than that used in [9] to define a class of standard models. We use models with ‘effectively generated’ successor functions, first studied by Shore [10] and used in [9] for their more delicate results on definability in R.

Definition 2.2. If M is a model of IΣ_{4} defined by parameters b, p, q, r, l and l′ via a coding scheme S and e_{0} , e_{1}, f_{0}, f_{1} are additional parameters from R_{N}, we say that M is effectively generated by these parameters if the even and odd integers of M are generated by e_{0}, e_{1}, f_{0}, f_{1}. More precisely if, 0^{M} ≤_{T} f_{0} and

x ≤_{T} (s_{0} ∨ l) → (x ∨ e_{1}) ∧ f_{1} = (x+_{M}1)^{M} and
x ≤_{T} (s_{1} ∨ l) → (x ∨ e_{0}) ∧ f_{0} = (x+_{M}1)^{M}.

One concludes from this definition and trivial facts of arithmetic that the relation g^{+} = h saying h is the successor of g is definable in any effectively generated model as follows:

g^{+} = h ⇔ (∃i ∈ {0, 1})[g ≰_{T} f_{i} & h = (g ∨ e_{i}) ∧ f_{i}].

This fact will be used implicitly in the sequel.

We will show that N is isomorphic to an initial segment of every model defined by a coding scheme S_{1} with extra parameters e_{0}, e_{1}, f_{0}, f_{1} and a correctness condition asserting that the models are effectively generated. The following theorem which is similar to Theorem 6.1 of [9] will follow from Theorem 3.8 below. It says that there is a recursively coded effectively generated model.

Theorem 2.3. There exist r.e. degrees b, p, q, r, l, l′, e_{0}, e_{1}, f_{0} and f_{1} which effectively generate a coded model N with domain {g_{i}|i ∈ N } which is isomorphic to N and recursive in the sense that the indices of the g_{i} and the structures defined on them are uniformly recursive.

Given an r.e. degree c > 0, we say that a coded model M lies below c if the parameters which code M are all recursive in c. Recall that a degree is promptly simple if it is not half of a minimal pair. (See Definition 3.1 and Theorem 3.2.) By a prompt permitting argument, one may generalize the above theorem as follows:

Theorem 2.4. If c is promptly simple, then there exists a recursive, effectively generated model N_{c} which is recursively isomorphic to N and lies below c.

This result is also similar to Theorem 6.1 of [9] and will follow from Theorem 3.8. Let C_{c} be the class of effectively generated coded models below c by our scheme S_{1}. We will now prove that any N_{c} as in Theorem 2.4 is N -standard for C_{c}. We begin by showing that (under suitable hypotheses) N_{c} is isomorphic to an initial segment of each effectively generated model coded below c.

Lemma 2.5. Let C be an r.e. set of degree c. Assume that IΣ_{4}^{C} holds in N and M is a coded model effectively generated by parameters lying below c in R_{N}. Then for any n in N, n^{M} exists.

Proof. We prove this by induction using IΣ_{4}^{C}. Claim 1. For any n ∈ N, there is an N -finite sequence ⟨x_{i} : i ≤ n⟩ such that

1. x_{0} = 0^{M};

2. For all i ≤ n, x ≤_{T} r and (x_{i} ∨ p) ≥_{T} q;

3. For 2i + 1 ≤ n, x_{2i+1} ≤_{T} (x_{2i} ∨ e_{1}) and x_{2i+1} ≤_{T} f_{1};

4. For 2i + 2 ≤ n, x_{2i+2} ≤_{T} (x_{2i+1} ∨ e_{0}) and x_{2i+2} ≤_{T} f_{0}.

Denote by ψ(n) the conjunction of the four conditions above. Then the complexity of ψ(n), upon replacing the Turing reducibility relation ≤_{T} by the reduction relation between (indices of) r.e. sets, is Σ_{3}^{C}. Suppose that ψ holds for n = 2k (the argument for n odd is similar). We first show that the x_{i} are in M. To see this, note that by (2) and (4) x_{i} ∉ M is equivalent to

∃y(y <_{T} x_{i} and y ∨ p ≥_{T} q)

which is Σ_{4}^{C}. Suppose that not all members of the sequence are in M. By IΣ_{4}^{C}, which is equivalent to LΠ_{4}^{C}, there is a least counterexample i. Then x_{i} ∉ M but x_{i−1} ∈ M. Without loss of generality, assume that x_{i−1} is an even integer in M. Then its successor h satisfies

h = (x_{i−1} ∨ e_{1}) ∧ f_{1} ≥_{T} x_{i}

where the last inequality follows from the fact that x_{i} is below both x_{i−1} ∨ e_{1} and f_{1}. On the other hand x_{i} ∨ p ≥ q, thus x_{i} = h since h is a minimal solution of the inequality and so x_{i} is in M. Thus by IΣ_{4}^{C}-induction x_{i} ∈ M for all i ≤ n. We can now verify Claim 1 for n+1 by taking x_{n+1} to be the successor of x_{n} in M. This proves Claim 1. Claim 2. For any n ∈ N, the sequence ⟨x_{i} : i ≤ n⟩ defined above is an initial segment of M. Indeed x_{i} = i^{M}. We first use induction on k ≤ n to establish the following Π_{4}^{C} statement:

∀x[(x ≤_{T} r,(x_{k} ∨ l) and (x ∨ p) ≥_{T} q) → (∃i ≤ k)(x_{i} ≤_{T} x)]. (∗)

Suppose (∗) is true for k. By Claim 1, x_{k} is in M and as shown in the proof of that Claim, x_{k+1} is the successor of x_{k} in M. Let x ≤_{T} r be such that x ∨ p ≥_{T} q and x ≤_{T} x_{k+1} ∨ l. Then x is above some h ∈ M and h ≤_{M} x_{k+1}. Thus h ≤_{M} x_{k} or h = x_{k+1}, which is the successor of x_{k}. Hence (∗) holds.

Furthermore (∗) implies that ⟨x_{i} : i ≤ n⟩ is an initial segment of elements in M. To see this, suppose that h ∈ M and h ≤_{M} x_{k}. Then if we substitute h for x in (∗), we get an x_{i} such that x_{i} ≤_{T} h. Since the members of M form an antichain (with respect to Turing reducibility), we have h = x_{i}. Thus if h ∈ M satisfies h ≤_{M} x_{k}, then h = x_{i} for some i ≤ k. □

Lemma 2.5 allows one to effectively embed N_{c} into every other effectively generated model M below c. The next step is to provide a coding scheme which allows us to compare (via a coding scheme for maps between coded models) initial segments of effectively generated models coded below c. An N -standard model for c will then be one whose initial segments can be embedded into every other effectively generated model coded below c via the maps defined by the coding scheme for comparisons. The intuitive argument goes roughly as follows: Suppose M is effectively generated and embeddable into every other coded model in C_{c} as an initial segment. Let f : M → N_{c} be an embedding that preserves the successor function. Let g : N_{c} → M be the natural embedding described in Lemma 2.5. If g(N_{c}) is a proper initial segment of M (bounded, say, by m), then fg : N_{c} → N_{c} maps an initial segment [0^{N_{c}}, n^{N_{c}}] of N_{c} properly into itself (where n^{N_{c}} = f(m)). Now if fg ↾ [0^{N_{c}}, n^{N_{c}}] is N -finite, then the pigeon hole principle is violated, and we have a contradiction. All this works if the instance of the pigeon hole principle that we need is sufficiently simple to follow from the amount of induction that we have in N. Thus we need to produce a map f as above that is as simple as possible. (Note that g ↾ n^{N_{c}} is N - finite by Lemma 2.5 as long as we have IΣ_{4}^{C}.) We begin by describing a variant of the scheme for comparison maps used in [9] and the technical lemma needed to prove the existence of parameters as required to make the scheme work. We will then consider some extensions of the scheme that allow us to define the map fg as an IΣ_{4}^{C} relation. Finally, we argue that we can restrict our attention to low degrees c by an appropriate quantification. This will allow us to get by with IΣ_{4}. First the technical lemma which is similar to Theorem 5.1 of [9] and will follow from Theorem 3.10.

Lemma 2.6. For any nonzero low degrees q_{0}, …, q_{m−1}, r_{0} and r_{1}, there is a recursive model M coded below a low degree such that

(i) M is recursively isomorphic to N; (ii) For each i < m, (i)^{M} ≤_{T} q_{i}; (iii) For i, j < m, if q_{i} ≰_{T} q_{j} then (i)^{M} ≰_{T} q_{j}; and (iv) For all x ≥_{M} m^{M}, x ≰_{T} r_{0}, r_{1}.

Notice that we do not require M to be an effectively generated model. (Indeed, there seems to be an incompatibility with M being effectively generated and the permitting required in this lemma.)

By the N -part of a coded model M we refer to the union of its initial segments of the type [0^{M}, n^{M}] where n ∈ N. Given two coded low models M_{0} and M_{1}, we want a scheme that (as we vary its parameters) defines comparison maps giving isomorphisms between their N -parts piece by piece. This is done for each n via a third model M which is obtained by applying Lemma 2.6 with m = 2n and q_{2i} = i^{M_{0}} and q_{2i+1} = i^{M_{1}} for i < n.

More precisely, for N -finite segments [0^{M_{k}}, n^{M_{k}}] in M_{k} (k = 0, 1) and a coded model M with element n =n^{M}, we define a comparison map f_{M,n^{M}} from M_{0} to M_{1} as follows: f_{M,n^{M}} : x ↦ y if and only if x ≤_{M_{0}} n_{0} = n^{M_{0}}, y ≤_{M_{1}} n_{1} = n^{M_{1}} and there exists an a ∈ M such that

(a) a <_{M} n and a ≤_{T} x;

(b) a is even in M;

(c) a^{+} ≤_{T} y, where a^{+} is the successor of a in M.

Given that q_{2i} = i^{M_{0}} and q_{2i+1} = i^{M_{1}}, we apply Lemma 2.6 and see that there is an M such that j^{M} <_{T} q_{j}. Then if x = q_{2i} and a = (2i)^{M}, we have a^{+} = (2i + 1)^{M} <_{T} q_{2i+1} which we can denote by y. Now by Lemma 2.6 (iii) and (iv) this y is uniquely defined, showing that f_{M,n^{M}} provides a one-one correspondence between the integers less than n in M_{0} and M_{1}. We have thus described a formula θ̂(x, y, p⃗_{0}, n_{0}, p⃗_{1}, n_{1}, p⃗, n) of degree theory which provides a scheme for isomorphisms between the N -parts of any two low coded models. In order to guarantee that the map defined is an isomorphism between the specified initial segments of M_{0} and M_{1} we include a correctness condition in this scheme which simply says that the relation defined between the initial segments of M_{i} below n_{i} is an order preserving isomorphism. The maps defined by our scheme θ̂ (with this correctness condition) are now candidates for the function f used in our informal argument above for defining N -standard models for C_{c}.

In particular, if we consider N_{c} for c low and promptly simple then for any effectively generated M_{0} coded below c, the scheme given by θ̂ provides isomorphisms from every initial segment of N_{c} onto ones of M_{0}. We would like to claim that any effectively generated M_{0} coded below a low promptly simple c, with the property that θ̂ provides isomorphisms between each of its initial segments and ones of every effectively generated M_{1} coded below c, is isomorphic to N (and so N -standard for C_{c} ). As we explained before, the problem is that the maps as defined by θ̂ provide too complicated an instance of the pigeon hole principle to contradict IΣ_{4}. The problematic part of the definition of θ̂ is membership in M (which is Π_{4}^{C}) and the definition of the successor function in M. We solve this problem by adding more parameters to the scheme S_{0} defining M as well as new correctness conditions that allow us to argue that there are IΣ_{4}^{C} definitions of the functions f_{M,n^{M}} given by θ̂. We add parameters t, u and v and the conditions (v)-(vii) of the following lemma to the scheme S_{0} to get a new scheme S_{2,c} defining models of arithmetic which has c as a parameter as well.

Lemma 2.7. Let c be low and promptly simple, and let M_{i} (i = 0, 1) be effectively generated models coded below c and n ∈ N. There is a model M coded below c and degrees t, u and v (also below c) which are uniformly defined in terms of the parameters p⃗_{i} defining M_{i} and the sequences ⟨j^{M_{0}}|j < n⟩ and ⟨j^{M_{1}}|j < n⟩ such that M satisfies the conditions (i)-(iv) of Lemma 2.6 substituting n for m, j^{M_{0}} for q_{2j} and j^{M_{1}} for q_{2j+1}, as well as the following conditions:

(v) For any even number h in M, h∨t is above h^{+}, but not above any other integer in M (except, of course, h). (In particular, there is a unique odd (resp. even) number k ∈ M below h ∨ t.)

(vi) The join of any nontrivial distinct triple of numbers in M with v

computes u, but no join of any pair with v computes u. (vii) For any even number h ∈ M, h ∨ t ∨ v ≱_{T} u.

This Lemma will follow from Theorem 3.10. We now show that these conditions suffice to make the maps defined by θ̂ be IΣ_{4}^{C}.

Lemma 2.8. With the notation of Lemma 2.7 and C an r.e. set of degree c, the following Σ_{4}^{C} formula θ defines the same map as f_{M,n^{M_{0}}} (assuming, of course, the correctness conditions of θ̂ hold):

θ(x, y, p⃗_{0}, n_{0}, p⃗_{1}, n_{1}, p⃗, n) if and only if x ≤_{M_{0}} n_{0}, y ≤_{M_{1}} n_{1}and there exist w, z such that

(d) w ≤_{T} s_{0} and z ≤_{T} s_{1}; (e) w ≤_{T} x and z ≤_{T} y;

(f) w ∨ p ≥_{T} q and z ∨ p ≥_{T} q;

(g) z ≤_{T} w ∨ t and w ∨ t ∨ v ≱_{T} u.

Proof. First we verify that θ(x, y, p⃗_{0}, n_{0}, p⃗_{1}, n_{1}, p⃗, n) holds whenever y = f_{M,n^{M_{0}}} (x). Let a be the witness required to show that f_{M,n^{M_{0}}} (x) = y. We take w to be a and z to be a^{+} in the definition of θ. It is easy to see that (d)—(f) hold and (g) follows from the connection between t, u and v specified in (v) and (vii). For the converse, suppose θ(x, y, p⃗_{0}, n_{0}, p⃗_{1}, n_{1}, p⃗, n) holds via witnesses w and z. By (f), w is above some a in M and by (d) a is an even number in M. By (e) and (iii) and (iv) of Lemma 2.6, a is the unique even element in M below x as the j^{M_{0}}’s form an antichain. We show that a is a witness that f_{M,n^{M_{0}}} (x) = y. Clearly (a) and (b) hold. We now prove (c) by showing that a^{+} ≤_{T} z, which is sufficient in view of (e). By (g), which says w ∨ t ∨ v ≱_{T} u, there are at most two integers in M below w ∨ t. Now a ≤_{T} w is one and a^{+} ≤_{T} w ∨ t ≤_{T} a ∨ t is another by (v). Hence only a and a^{+} are below w ∨ t. By (f) and (d), z is above some odd integer in M. Since z ≤_{T} w ∨ t, that odd integer must be a^{+}. □

Recall that if c is promptly simple, then C_{c} denotes the class of effectively generated coded models below c via S_{1}. Heading toward our definition of a class of N -standard models for C_{c}, we define the relation Θ(p⃗_{0}, p⃗_{1}) to hold if and only if

1. p⃗_{0} and p⃗_{1} code models M_{0} and M_{1}, respectively, via S_{1} and

2. (∀x ∈ M_{0})(∃y ∈ M_{1})(∃p⃗, n)(p⃗ codes a model M via S_{2,c}, n ∈ M

and

θ(x, y, p⃗_{0}, n_{0}, p⃗_{1}, n_{1}, p⃗, n)).

That is, every initial segment [0^{M_{0}}, x] of M_{0} is isomorphic to one [0^{M_{0}}, y] of M_{1} by a map defined by θ through a third model M coded by p⃗ via S_{2,c} and an n ∈ M.

We will now show that Ψ(p⃗_{0}, c) ≡ (∀p⃗_{1})(p⃗_{1} codes a model below c via S_{1} → Θ(p⃗_{0}, p⃗_{1})) is the required correctness condition for a coding scheme that guarantees that M_{0} is N -standard for C_{c}.

Lemma 2.9. Assume that C is promptly simple and that IΣ_{4}^{C} holds. Let M_{0} be an effectively generated model coded by p⃗_{0} below c. Suppose that Ψ(p⃗_{0}, c) holds. Then M_{0} is isomorphic to N.

Proof. By Theorem 2.4 there is a coded model N_{c} = M_{1} below c which is a recursive copy of N. By Lemma 2.5 there is an order-preserving one-to-one map g from M_{1} to M_{0} which is closed downwards so that M_{0} is an end-extension of M_{1}. Moreover, g restricted to any initial segment of M_{1} is N -finite. We show that this map is onto. Suppose for the sake of a contradiction that there is an x ∈ M_{0} which is not in the range of g. Then, as guaranteed by Θ, there is an M and an n ∈ M which provide an order-preserving isomorphism from [0^{M_{0}}, x] to some initial segment [0^{M_{1}}, y] of M_{1}. By Lemma 2.8 this map f is Σ_{4}^{C}. The N - finite function g ↾ [0^{M_{1}}, y] maps this interval one-to-one and onto some [0^{M_{0}}, x′] in M_{0} and x′ <_{M_{0}} x by our choice of x. Thus fg ↾ [0^{M_{1}}, y] is one-one, Σ_{4}^{C} and maps some [0^{M_{1}}, y] which is recursively isomorphic to some interval [0, n] in N into a proper subset of itself. As this map is Σ_{4}^{C} it is actually N -finite by IΣ_{4}^{C} induction, and so contradicts the pigeon hole principle. □

Our analysis so far shows that the next definition may be formalized in the language of R_{N}.

Definition 2.10. M_{0} is good for c if M_{0} is an effectively generated model coded below c by the parameters p⃗_{0} and Ψ(p⃗_{0}, c) holds.

Summarizing the results obtained thus far, and noticing that for C low IΣ_{4}^{C} is equivalent to IΣ_{4}, we have the following.

Theorem 2.11. If N ⊧ IΣ_{4} and c is promptly simple and low, then 1. there is an M_{0} which is good for c, and

2. any M_{0} good for c is isomorphic to N.

We are now ready to provide an interpretation of the theory of N in R_{N}. Theorem 2.11 says that the theory of N may be interpreted below any low, promptly simple degree c whenever N satisfies IΣ_{4}. We can define the class PS of promptly simple degrees in R_{N} as the ones which are not half of a minimal pair by [1]. (See Theorems 3.2.) The problem is that we do not have a first-order degree-theoretic definition for the low degrees. However, we can get the same effect in terms of interpreting the theory of N (although not of N itself) by quantifying over promptly simple degrees in the way used by Slaman and Woodin in their (unpublished) proof that there is an interpretation of the theory of N in R.

Definition 2.12. We define a translation ^{∗} taking a sentence φ in the language of Peano arithmetic to a φ^{∗} in the language of R. First let φ′(p⃗) be the corresponding sentence of R_{N} asserting that φ holds in the model coded by the parameters p⃗ (using the translation provided by the scheme S_{0}). Then let φ^{∗} be

(∀d ∈ PS)(∃c ∈ PS)(∃M_{0})(c ≤_{T} d, M_{0} is good for c and M_{0} ⊧ φ′).

Theorem 2.13. For every formula φ of arithmetic, if N ⊧ IΣ_{4}, then

N ⊧ φ ⇔ R_{N} ⊧ φ^{∗}.

Proof. Suppose that N ⊧ φ and d is promptly simple. By Theorem 3.6 (taken from [6]) we can choose a degree c ≤ d which is promptly simple and low. Let M_{0} be a the recursive copy of N as given by Lemma 2.4. Clearly M ⊧ φ′ as it is isomorphic to N. It remains to check that M_{0} is good for c, which can be done as carried out before under IΣ_{4}^{C}, and this is equivalent to IΣ_{4} since c is low. For the converse, suppose that R_{N} ⊧ φ^{∗}. Choose d low and promptly simple. Fix c and M_{0} as in the hypothesis. Then by the lowness of c and Theorem 2.11, IΣ_{4} shows that M_{0} is isomorphic to N. Since M_{0} ⊧ φ′, we get N ⊧ φ. □

We now draw some consequences of our work which illustrate the extent to which the theory of R_{N} depends on, and reflects, the amount of induction that holds in N. First, in terms of reverse mathematics we see that we have equivalents for IΣ_{n} for each n > 4 over the base theory IΣ_{4}.

Corollary 2.14. For each n > 4 there is a theorem ψ_{n} about the r.e. degrees such that ψ_{n} is equivalent to IΣ_{n} over the base theory IΣ_{4}. Proof. For each n > 1 there is a sentence φ_{n} of arithmetic that is equivalent to IΣ_{n} over IΣ_{1}. Let ψ_{n} be φ_{n}^{∗}. For n > 4, our results show that N ⊧ φ_{n} ⇔ R_{N} ⊧ φ_{n}^{∗} for every model N of IΣ_{4}. Thus φ_{n}^{∗} is the desired formula ψ_{n}. □

Another way of looking at our results and other older ones is in terms of the r.e. degree theory of various fragments of arithmetic. If T is a theory of arithmetic, the r.e. degree theory of T is the set of all firstorder sentences (without parameters) in the language of the r.e. degrees which are true in every model of T. For example, consider the theory IΣ_{n}^{+} which is P A^{−} + IΣ_{n} together with a sentence which asserts the failure of Σ_{n+1}-induction. We call this theory strict IΣ_{n}. Our results here show that the r.e. degree theories of IΣ_{n}^{+} are not complete for n ≥ 4 as the theories IΣ_{n} are themselves not complete. On the other hand, results such as those on the existence of minimal pairs [2] and on the density of branching r.e. degrees [14] show that the r.e. degree theories of IΣ_{1}^{+} and IΣ_{2}^{+} are incomplete as well.

We now give some other corollaries.

Corollary 2.15. For n > m ≥ 4, the r.e. degree theories of IΣ_{n}^{+} and IΣ_{m}^{+} are different. Proof. If N_{m} is a model of IΣ_{m}^{+}, it satisfies the sentence φ which states that IΣ_{m+1} fails. Hence φ^{∗} holds in R_{N_{m}}. Now φ^{∗} is parameter free and true in the r.e. degree theory of IΣ_{m}^{+}. On the other hand, φ is false in every model N_{n} of IΣ_{n}^{+}, so that φ^{∗} is false in the r.e. theory of degrees for IΣ_{n}^{+}. □

Corollary 2.16. The r.e. degree theory of IΣ_{1}^{+} is different from the r.e. degree theory of IΣ_{n}^{+} for n ≥ 2.

Proof. It is shown in [2] that the existence of a minimal pair of r.e. degrees is equivalent to IΣ_{2} over the base theory BΣ_{2}. Since there exist models satisfying BΣ_{2} (hence IΣ_{1}) but not IΣ_{2}, we have a sentence that differentiates between the r.e. degree theories of IΣ_{1}^{+} and IΣ_{n}^{+} for n ≥ 2. □

Yang [14] has recently shown that over P A^{−}+BΣ_{3}, Slaman’s theorem that branching r.e. degrees are dense is equivalent to Σ_{3}-induction. This gives an example of the equivalence of IΣ_{3} with a 0′′′ priority argument. It also gives a difference between the r.e. degree theories of IΣ_{2}^{+} and IΣ_{3}^{+}. We believe that Corollary 2.15 holds for all n > m ≥ 1. The only case left open is when n > m = 3. A recursion-theoretic statement whose proof requires a 0′′′′ priority argument would be a good candidate to establish this.

In terms of reverse mathematics, the natural question along these lines is whether Corollary 2.14 can be improved by weakening the base theory to IΣ_{1} (or any IΣ_{k} for k < 4) and establishing equivalences for all n > 1 (or n > k). Another question to ask is the extent to which Theorem 2.13, whose proof uses IΣ_{4} in an essential way, can be strengthened. More specifically, for 1 ≤ k ≤ 3, is there an interpretation ∗ (a recursive map from sentences in the language of Peano arithmetic to sentences in the language of partial ordering for r.e. degrees) such that for all models M of IΣ_{k} and all sentences φ, M ⊧ φ if and only if R_{M} ⊧ φ^{∗}?

§3. Recursion-theoretic Constructions. Throughout this section, we fix N to be a model of IΣ_{4}. All r.e. degrees are members of R_{N}. We need to argue that all the facts about the R_{N} used in the previous section can be proven in IΣ_{4}. An examination of our arguments shows that four Theorems 3.2, 3.6, 3.7 and 3.9 suffice. Some of the arguments merely require reading proofs in the literature and noticing that IΣ_{4} suffices to carry them out. Others are new results about the r.e. degrees which are extensions and elaborations of results in [9]. We assume familiarity with that paper as well as [6] and [1] or the presentation of that material in Ch. XIII of [13] and with tree arguments as in, for example, Ch. XIV of [13]. For our purposes we may take the promptly simple degree theorem of [6] as a definition of PS, the class of promptly simple degrees.

Definition 3.1. An r.e. degree a is promptly simple if there is an A ∈ a with an enumeration A_{s} and a recursive function p such that for all s, p(s) ≥ s and for all e

W_{e} infinite ⇒ (∃x)(∃s)[x ∈ W_{e,at s} & A_{s} ↾ x ≠ A_{p(s)} ↾ x].

Theorem 3.2. (Ambos-Spies et al. [1]) The promptly simple degrees c are precisely those which are not halves of minimal pairs, i.e. (∀x > 0) (∃y > 0) (y ≤_{T} x, c).

The proof that no promptly simple c is half of a minimal pair is Theorem 1.11 of [6]. In terms of Definition 3.1, it appears as Theorem XIII.2.1 in [13]. Its proof is easily seen to work in far less than IΣ_{4}. The other direction is Theorem 1.13 of [1] (and XIII.2.2 of [13]). Unfortunately there is a gap in these write ups of this result. It will be corrected in the new edition of [13] but we take this opportunity to present a different presentation based on a gap-cogap tree argument taken from [11].

We are given a nonrecursive r.e. set B and wish to build an r.e. A and various candidates p_{α} such that either some p_{α} is a witness to B’s being of promptly simple degree or A > 0 and A ∧ B = 0. The requirements are as follows:

N_{e}: Φ_{e}(A) = Φ_{e}(B) = h_{e} ⇒ h_{e} ≤_{T} 0 (in fact we will define partial recursive functions ψ_{e,i} such that h_{e} = ψ_{e,i} for some i).

P_{e}: Φ_{e} ≠ A

R_{e}: There is a recursive p_{e} such that ∀i[W_{i} infinite ⇒ ∃x, s(x ∈ W_{i,at s} &B_{s} ↾ x ≠ B_{p(s)} ↾ x)].

The requirements N_{e}, P_{e} and R_{e} are assigned to nodes α with length 3e, 3e + 2 and 3e + 1, respectively. Thus our tree construction will, for some α with |α| = 3e + 1, build a recursive p_{α} as in R_{e} or guarantee that N_{e} and P_{e} are satisfied for all e.

To understand the module for one requirement R_{e} or N_{e} consider first the problem of just trying to build A for any given B following the usual minimal pair construction on a tree. The problem is that once we get a new length of agreement, if we allow A to change later on the use, we cannot preserve the B-computations. (And so, in fact, not every b is half of a minimal pair.) Our plan then is to allow A to change only at those stages (inside a gap) at which a B change would get us closer to satisfying R_{e,i} for some new i: If we have an x ∈ W_{e,at s} and if B ↾ x changes “promptly”, i.e. before p_{e}(s), we would satisfy R_{e,i}. At those stages (inside the cogap) at which we would get no advantage from a B change (after p_{e}(s)) we must preserve the A-computations to keep the minimal pair argument working.

To be more precise if Φ_{e}(A) = Φ_{e}(B) = h_{e} we will define p_{e} and ψ_{e,i} such that if i is least such that p_{e} does not satisfy R_{e,i} then ψ_{e,i} = h_{e} so as to meet N_{e}. At a stage s + 1 at which the usual length of agreement function ℓ(e, s) has reached a new maximum we may open an R_{e,i} gap for the least i such that R_{e,i} is not yet satisfied and for which we have an x ∈ W_{i,at s} and a y ∉ dom ψ_{e,i,s} with y < ℓ(e, s) such that ∀z ≤ y[ϕ_{e}(B; z)[s] < x]. We now set ψ_{e,i}(z) = Φ_{e}(B; z)[s] for z ≤ y, z ∉ dom ψ_{e,i,s}. The idea is that we need not restrain A as long as the gap is open since any change in B below the use (at some y′ ≤ y) would give us a win on R_{e,i}. For this threat to be credible we must, however, eventually define p_{e}(s). We wait for the first stage t at which ℓ(e, t) > ℓ(e, s). We then set p_{e}(s) = t and close the gap. The point now is that we no longer get any advantage from a B change on the use (for y′ ≤ y) and must now impose restraint on the use from A during the cogap , i.e. until the next gap is opened.

Note that we really need to deal with R_{e} only if ℓ(e, s) → ∞. The positive requirements have, as usual, disjoint, infinite, recursive sets Q_{α} assigned to them with x ∈ Q_{α} → x > α. The interactions among the various strategies (in particular different R_{e}) is now handled by a tree construction. The priority tree: We specify the assignment of requirements and their outcomes:

a) |α| = 3e is assigned to N_{e} and the possible outcomes are i (if ℓ(α, s) → ∞) and n ∈ ω (the last stage at which ℓ(α, s) reached a maximum).

b) |α| = 3e + 1 is assigned to R_{e}. If the outcome of N_{e} is not i at the immediate predecessor of α, then that of R_{e} at α is 0 (no action is needed for R_{e}). Otherwise, the outcome can be g_{n} or d_{n}(n > 0, n ∈ ω). The idea here is first that g_{n} (gap) represents the possibility that Φ_{e}(B) is total and n is least such that R_{e,n} fails, i.e. we open an R_{e,n} gap infinitely often at α. In this case we will claim that, if h_{e} is defined then it equals ψ_{α,n}. The outcomes d_{n} (divergent) represent the possibility that Φ_{e}(B; y_{n}) ↑ where we define y_{n} at the last stage we go through g_{n} (i.e. the last time we open or close an R_{e,n} gap). The outcomes are ordered by 0 <_{L} g_{1} <_{L} d_{1} <_{L} g_{2} <_{L} d_{2} <_{L} · · ·.

c) |α| = 3e + 2 is assigned to P_{e}. The outcomes here are s if ∃x ∈ Q_{α}[Φ_{e}(x) = 0 & x ∈ A] and w otherwise. Of course w <_{L} s.

The Construction:

The accessible nodes at stage t: The sequence δ_{t} of length ≤ t of nodes accessible at stage t is defined by induction beginning with ∅ which is always accessible. Say α ⊆ δ_{t}, |α| < t. We let u_{e}(y, t) = max{ϕ_{e}(B; z)[t]|z ≤ y}. |α| = 3e: αˆ i ⊆ δ_{t} if ℓ(α, t) > ℓ(α, r) for every r < t such that α ⊂ δ_{r}. Otherwise αˆ r ⊆ δ_{t} where r is the last stage at which αˆ i ⊆ δ or 0 if there is no such stage. |α| = 3e + 1: If δ_{t}(3e) ≠ i, δ_{t}(3e + 1) = 0. Otherwise we go through the following steps to define δ_{t}(3e + 1):

1. Let r < t be the last stage at which α ⊆ δ_{r}. (If there is no such r, δ_{t}(3e+1) = 0.) If we opened an R_{e,n} gap for α at r we now close it, set δ_{t}(3e + 1) = g_{n} and terminate the definition of δ_{t}. Otherwise,

2. We find the least n for which

(a) we can open an R_{e,n} gap (for α) at t, i.e.

(i) R_{e,n} is not satisfied for p = p_{α} which is given by p_{α}(r) = (μs > r)(α ⊆ δ_{s} and we closed an R_{e,n} gap at s) and

(ii) ∃x ∈ W_{n,t} − W_{n,r} such that u_{e}(y_{n}, t) < x; or

(b) dom ψ_{α,n,r} = dom ψ_{α,n,t} = y_{n} and u_{e}(y_{n}, t) > u_{e}(y_{n}, v) for all

v < t with α ⊆ δ_{v}. Now, if we can open a gap for R_{e,n} (2a), then we set δ_{t}(3e + 1) = g_{n}, and ψ_{α,n}(y_{n}) = Φ_{e,s}(B_{s}; y_{n}). (Note that we will automatically have y_{n} < ℓ(α, t) as we only extend dom ψ_{α,n} at stages at which ℓ(α, s) is above the value it had when we last extended dom ψ_{α,n}). If we cannot open a gap but satisfy (2b) then we set δ_{t}(3e+1) = d_{n} and continue.

3. If there is no n as required in (2) we terminate the definition of δ_{t}.

|α| = 3e + 2: αˆ s ⊆ δ_{t} if ∃x ∈ Q_{α}[ Φ_{e,t}(x) = 0 & x ∈ A_{t}]. Otherwise αˆ w ⊆ δ_{t}.

The action at stage t: Find the shortest α ⊆ δ_{t} such that δ_{t}(|α|) = w and ∃x ∈ Q_{α}[Φ_{e,t}(x) = 0 & x > r for every r < t at which δ_{r} <_{L} α] and put the least such x into A. If there is no such α go on to the next stage. This finishes the construction.

The Verifications:

The basic situation here is a bit more complicated than in many usual tree arguments. As we might go through g_{n} (and d_{n}) successively there needn’t be a leftmost infinite path through the tree that is accessible infinitely often. In this case, however, we show that B ∈ PS.

Lemma 3.3. If B ∉ PS then there is an infinite leftmost path f. (We take this assertion as shorthand for the existence, for each n, of an α of length n which is accessible infinitely often such that no β to the left of α is accessible infinitely often. We denote this property by α ⊆ f.)

Proof. We proceed by induction on n = |α|. If |α| = 3e or 3e+2 then if α ⊂ δ_{t} for infinitely many t then αˆ x ⊂ δ_{t} for some outcome x and so for a leftmost one as there are only finitely many outcomes. If |α| = 3e + 1 and some immediate successor x is accessible infinitely often then there is again a leftmost one as there are only finitely many outcomes to the left of x. If no successor node is accessible infinitely often, we claim that p_{α} is a witness to B being of promptly simple degree. If not let W_{n} be the least counterexample. Note first that α(3e) = i for otherwise we would eventually have αˆ 0 ⊆ δ_{t} for all t with α ⊂ δ_{t}. Thus ℓ(α, t) → ∞. As no successor g_{m} or d_{m} is traversed infinitely often we may choose t_{0} such that ∀t ≥ t_{0}(αˆ g_{m} ⫅̸ δ_{t} & αˆ d_{m} ⫅̸ δ_{t}) for m ≤ n. As we never again go through αˆ g_{n}, ψ_{a,n,t} is fixed, say as ψ_{α,n}, for t ≥ t_{0} and we can set y_{n} = dom ψ_{α,n}. As we never again go through αˆ d_{n}, u_{e}(y_{n}, t) is bounded for t with α ⊆ δ_{t} say by u. As W_{n} is infinite we eventually get a t > t_{0} with an x ∈ W_{n,at t} and x > u. Now at the next stage s > t at which α ⊂ δ_{s} we would, by the definition of being able to open an R_{e,n} gap, have αˆ g_{n} ⊆ δ_{t} unless R_{e,n} were already satisfied for our desired contradiction. □

We now assume that f is the leftmost infinite path.

Lemma 3.4. Each P_{e} is satisfied.

Proof. Say |α| = 3e + 2 and α ⊂ f. If αˆ s ⊂ f we are done so suppose αˆ w ⊂ f but Φ_{e} = A. Thus Q_{α} ∩ A = ∅ and there is an x ∈ Q_{α} with x > t for every t with δ_{t} <_{L} α and an s with Φ_{e,}_{s}(x) = 0 for which α ⊂ δ_{s}. We would now, by our action at s, put such an x into A unless P_{e} were already satisfied and so αˆ s ⊂ f after all. □

Note now that if α ⊂ f and αˆ d_{n} ⊂ f then Φ_{e}(B) is not total and so to finish the proof of the theorem it suffices to prove the following:

Lemma 3.5. If Φ_{e}(A) = Φ_{e}(B) = h_{e}, |α| = 3e + 2 and αˆ g_{n} ⊂ f then ψ_{α,n} = h_{e}.

Proof. Let t_{0} be such that ∀t > t_{0}(δ_{t} ≮_{L} αˆ g_{n}). We argue by induction from one stage t > t_{0} at which αˆ g_{n} ⊆ δ_{t} and at which we open an R_{e,n} gap to the next such t′ that if ψ_{α,n,t}(y) ↓ then for every r, t ≤ r ≤ t′

ψ_{α,n,r}(y) = Φ_{e,r}(A_{r}; y) or Φ_{e,r}(B_{r}; y).

Now at the first stage t at which ψ_{α,n,t}(y) ↓ its value is Φ_{e,t}(B_{t}; y) by definition. As we never satisfy R_{e,n}, B cannot change on u_{e}(y, t) until the next stage r at which αˆ g_{n} ⊆ δ_{r} at which we close the R_{e,n} gap. At this stage Φ_{e,r}(A_{r}; y) = Φ_{e,r}(B_{r}; y) = Φ_{e,t}(B_{t}; y) and no element enters A. (The part to notice here is that δ_{r} = αˆ g_{n} as its definition is terminated at this level. Thus no P_{e′} for e′ ≥ e can put an element into A. On the other hand no P_{e′} for e′ < e can put one in since that would cause a shift in outcome for P′_{e} from w to s contradicting α ⊂ f. From now until t′, however, we are never to the left of αˆ g_{n} as t > t_{0} and so no elements can be put into A below r > u_{e}(y, t) until t′. Thus Φ_{e,t′}(A_{t′}; y) = Φ_{e,r}(A_{r}; y) = Φ_{e,t}(A_{t}; y). We now simply note that if we define ψ_{α,n}(y′) at t′ then y′ > y, u_{e}(y′) > u_{e}(y) and so we can continue the induction by seeing that again B cannot change on u_{e}(y′, t′) > u_{e}(y, t) until we next close the R_{e,n} gap. □

This completes the proof of Theorem 3.2 (in ordinary mathematics). As an aside we point out that this proof shows that the definition of promptly simple degree is independent of both the r.e. member of the degree considered and its enumeration. All we have to do now is check that we did not need anything more than IΣ_{4}. The most complicated use of induction is the proof of Lemma 3.3. The statement being proved by induction on n is that there is an α of length n which is accessible infinitely often and such that there is a bound on the stages at which any (α ↾ i)ˆ x is accessible for i < n and x <_{L} α(i). This sentence is Σ_{3} and so our induction can be carried out in the model N of IΣ_{4}. Everything else used in the proof is easily seen to be simpler yet.

Theorem 3.6. (Maass, Shore and Stob [6]) For every promptly simple d there is a low promptly simple c ≤_{T} d.

Proof. This is simply the special case of Theorem 1.5 of [6] with A = B. The proof is routine (once one knows about prompt permitting) and clearly needs far less induction than Σ_{4}. □

Our next theorem was originally stated as Theorem 2.4.

Theorem 3.7. For every promptly simple c there is an effectively generated recursive model M isomorphic to N with all its parameters below c.

For this Theorem and Theorem 3.9, we use the notation of [9], assume the reader is familiar with its constructions and verifications, and describe only the changes needed to get the construction satisfying Theorems 3.7 and 3.9. Our starting point for Theorem 3.7 is Theorem 6.1 of [9] to which we must add requirements (8 and 9 below) to take care of the only new aspect of our theorem, namely the addition of the second partial order coded by l′ that coincides with ≤_{M} on M. The following Theorem is then the technical result needed to verify Theorem 3.7.

Theorem 3.8. Given any 0 <_{T} A ≤_{T} U with U promptly simple, and given recursive partial ordering P = ⟨ω, ⪯⟩ with a specified infinite recursive set H = {h_{i}|i ∈ ω} of minimal elements, there are r.e. sets E_{0}, E_{1}, F_{0}, F_{1}, B, P, Q, R and G_{i} (for i ∈ ω) with R = ⊕G_{i}, F_{0} = ⊕G_{h_{2i}}, F_{1} = ⊕G_{h_{2i+1}} and B = G_{i}^{[0]} (for each i ∈ ω) such that P, Q ≤_{T} U, all the other sets constructed are recursive in A and

1. (T) : G_{i} ⊕ P ≥_{T} Q.

2. (D) : G_{i} ≱_{T} G_{j} for i ≠ j.

3. (M) : If B is recursive in an r.e. W which is recursive in R and W ⊕ P ≥_{T} Q, then there is a j ∈ ω such that G_{j} ≤_{T} W.

4. (K) : R ⊕ P is low.

5. (O) : i ⪰ j ⇒ G_{i} ⊕ L ≥_{T} G_{j}.

6. (N) : i ⪰̸ j ⇒ G_{i} ⊕ L ≱_{T} G_{j}.

7. (Y) : For each i ∈ ω, deg (G_{h_{2i}} ⊕ E_{1}) ∧ deg(F_{1}) = deg(G_{h_{2i+1}}) and deg (G_{h_{2i+1}} ⊕ E_{0}) ∧ deg(F_{0}) = deg(G_{h_{2i+2}}).

8. (O′) : i ≥ j ⇒ G_{h_{i}} ⊕ L′ ≥_{T} G_{h_{j}}.

9. (N′) : i ≱ j ⇒ G_{h_{i}} ⊕ L′ ≱_{T} G_{h_{j}}.

For the purposes of Theorem 3.7, we can take A = U ∈ c. Also note that our coding of a model M of arithmetic in the partial order P makes the domain of M the minimal elements of P which we take to be H listed in the order of M.

As a first approximation, requirements O′ and N′ should be treated exactly as were O and N. The plan for O′ then would be that whenever a number x enters some G_{h_{j}} it must also be put either into L′ or into every G_{h_{k}} with k > j. Similarly, requirements N′ would be treated exactly as are the ones for N. If we were constructing a coded model via S_{0} (and so without the lattice structure required by S_{1} and effective generation), we could do this without any difficulty. One only needs to check that no new conflicts are introduced. For O and O′, we consider any x targeted for some G. It is a follower of some requirement D_{i,j}, N_{i,j,e} or N′_{i,j,e} and so we must preserve the corresponding computation from G_{i}, G_{i} ⊕ L or G_{h_{i}} ⊕ L′, respectively. In the first case, when we put x into G_{j} we can put x into L and L′ as well without injuring the computation from G_{i}. In the second case, when we put x into G_{j} we can put x into L′ and every G_{k} with k ⪰ j without injuring the computation from G_{i} ⊕ L since i ⪰̸ j. In the third case, when we put x into G_{h_{j}} we can put it into L and every G_{h_{k}} for k > j without injuring the computation from G_{h_{i}} ⊕ L′ as i ≱ j. Thus no essential changes to the basic constructions in [9] through §4.4 would be necessary to construct, for example, a recursive coded model isomorphic to N via our scheme S_{0} by omitting requirements Y in Theorem 3.8 but including O′ and N′.

The new problem in proving Theorem 3.8 comes from the need to satisfy the infima requirements Y in the associated pinball construction. This construction does not allow us to put numbers simultaneously into distinct G_{h_{j}} and G_{h_{k}} (as they appear as components of both sides of the computations at single gates). (There is no problem putting numbers simultaneously into any G_{j} and all G_{i} with i ≻ j as the only G_{k} involved in the infima requirements are ones minimal with respect to ⪰.) To solve this problem, we first change the nature of the coding procedure for O′_{k,j} to compute G_{h_{j}} from G_{h_{k}} ⊕ L′. To decide if x ∈ G_{h_{j}} we ask if x ∈ G_{h_{k}} or x ∈ L′. If not, x ∉ G_{h_{j}}. If so, we find the stage s at which it entered. If x entered at s we will set up a sequence of coding markers targeted for L′ in the standard fashion. We appoint a new large one t > s at s and may change it to a larger number when it or some smaller number enters L′. Eventually, either x enters G_{h_{j}} (perhaps already at s) or we appoint a marker targeted for L′ which never enters L′. The full solution to our problem also involves weakening even this coding procedure for requirements O′ so that they work for all but finitely many x’s. We also have to add an appropriate sequence of balls to the entourage for any x which is a follower of some N′_{i,j,e}.

As in the basic construction without the infima requirements, D and N requirements only need to preserve computations from G_{i} and L. When one of their followers x enters G_{h_{j}} we can simply put x into L′ to maintain the codings for all O′ requirements. (We can also put it into G_{k} for all k ≻ h_{j} as well to maintain the O codings.) Similarly, any ball x appointed as a trace in the pinball construction is too large to injure the computation realizing the follower to whose entourage it belongs and so when it enters its target G_{h_{k}} we can put it into both L and L′ to satisfy all the codings requirements for O and O′. Thus our only worries are for followers x of some N′_{i,j,e} requirement that we wish to target for G_{h_{j}}. We place x in the hole for this requirement which we assume is the nth requirement on our master list of all the requirements. Our plan is to also put in the hole balls labelled ⟨x, i, j, e, k⟩, say, targeted for G_{h_{k}} for j < k ≤ n. When the ball ⟨x, i, j, e, k⟩ leaves the permitting bin of the pinball machine (i.e. it first reaches the bin and then x is permitted by A) we put x into G_{h_{k}}. Of course, each such ball is provided with an appropriate sequence of traces at all stages before it leaves the machine. The balls ⟨x, i, j, e, k⟩ (with their traces) are arranged in the hole in order (of k) so that the first one to roll out and stop at a gate is ⟨x, i, j, e, n⟩ (preceded, as usual, by its sequence of traces).

The appointment of traces and movement of balls down the pinball machine is now as in [9]. When the first of these new balls in x’s entourage, ⟨x, i, j, e, n⟩, leaves the permitting bin, say at stage s_{n}, we put x into G_{h_{n}} but not into any other G_{h_{k}}. We also appoint t_{n} > s_{n} as the coding marker for the reduction associated with O′_{n,k} at x for k < n. This marker is targeted for L′. This action does not injure the computation that realized x for N′_{i,j,e} as i < j ≤ n. It does, however, violate our coding requirements O′_{k,n} for k > n but such violations will happen only finitely often. When the next ball ⟨x, i, j, e, n − 1⟩ leaves the permitting bin, say at stage s_{n−1}, we put x into G_{h_{n−1}} and so violate the coding requirements O′_{k,n−1} for k > n but for k = n we can put t_{n} into L′ (and so make the reduction described above for computing G_{h_{n−1}} from G_{h_{n}} correct at x) without injuring the computation that realized x for N′_{i,j,e}. Of course, we now redefine the coding markers for x targeted for L′ for O′_{n,k} and O′_{n−1,k} for k < n−1 to be t_{n−1} > s_{n−1}. We continue on with this procedure putting x into each G_{h_{k}} in turn until we get to put x into G_{h_{j}} as desired. At this point we injure O′_{k,j} for k > n but can put the large marker t_{j+1} for each O′_{k,j} for j < k ≤ n into L′ and so make these reductions correct. Thus we see that the reduction described above for computing an arbitrary G_{h_{j}} from G_{h_{m}} ⊕ L′ with m > j is violated only when we act for a requirement N′ which appears on our list of requirements before position m. As these requirements will act only finitely often, we will satisfy the requirement O′_{m,j}.

The other changes needed in the construction are minor and straightforward given our plans for satisfying the O′ requirements. For example, we place N′_{i,j,e} immediately after N_{i,j,e} in our master list of requirements. Suppose it is in position n. The function giving the number of permissions need to get a particular follower x into G_{h_{j}} is then (n − j + 1) times that for N_{i,j,e} (g(i, j, e)) as we must get all the balls ⟨x, i, j, e, k⟩ for j < k ≤ n as well as x through the permitting bin. The restraint imposed to preserve the suitability of the follower x of N′_{i,j,e} in the Slaman-Woodin part of the construction is now calculated so as to also preserve the suitability of x entering G_{h_{k}} for j ≤ k ≤ n. This then concludes our description of the (changes in the) construction (from that for Theorem 6.1 of [9]).

We must now say a word or two about the amount of induction needed for the verifications. The global structure of the Slaman-Woodin construction (requirements T, D, M and K) has finitary action by all the requirements except M and so the induction statement of the outcomes for these requirements is Σ_{2}. The M requirements are like the minimal pair requirements in Ch. IX of [13]. The essential point here is that for each M_{i} there are either finitely many expansionary stages or infinitely many. In the first case, the action by M is finitary. In the second, we argue that the restraint is eventually constant on the expansionary stages. In either case, the positive action is finitary. Thus the statements needed here are clearly no worse than Σ_{3}. We also need to know that the subsets of any initial segment of M requirements that fall into each case is N -finite and then that the total restraint is bounded. Again IΣ_{3} is sufficient. Except for the interactions with the pinball machine requirements N and N′ are like D. The coding requirements can be ignored at this stage as they impose no restraint and act whenever they want to. So all that remains at the global level is the pinball construction. Here the situation is again like the minimal pair argument. We must know the subset of gates within any initial segment that open infinitely often. Then we must argue that there is a bound on the stages at which those (in any initial segment) that are permanently occupied have been occupied by their permanent residents and that after that stage every ball that reaches the beginning of this sequence of gates gets through to the end. Again IΣ_{3} clearly suffices. The inductive assumptions for the diagonalization and preservation requirements are again just that the outcomes are finitary. This brings us to the consideration of the inductive steps of the argument. For the basic construction, all except the M requirements are essentially immediate. The arguments for M involve a few Lemmas (4.2–4.6 of [9]) which at worst are of the form that if something happens infinitely often (e.g. some functional Δ_{i,j} being constructed gives the wrong answer at infinitely many x) then there are infinitely many x with some additional property. These are proved by induction on n by showing that under the assumed hypotheses there are at least n many x’s as required. As the required properties are Π_{1}^{0}, these inductions are Σ_{2}. The other type of inductions used are on j as it is shown that each Δ_{i,j} (j ≤ n_{i}) are total. This looks like a Π_{3} induction as the functionals Δ_{i,j} are computed relative to arbitrary r.e. sets W_{e}. Although this would not be a problem in IΣ_{4}, we note that as all the sets W_{e} considered are below the set R that we are constructing to be low, we can actually convert this into a Π_{2} induction.

With the pinball construction added in, the difficult part of the proof is actually showing that the action for the D, N and N′ requirements is finitary. The inductive assumptions about the actions of the gates described above, however, are sufficient along with IΣ_{3}. The argument for the success of infima requirements is now the standard pinball construction argument that, recursively in the infimum, finds a certain type of stage at which we have a computation at a given x and then argues by induction that the computation remains correct (on one side or the other of the pair being considered) at every later stage. Once again the amount of induction needed is small. The arguments for the success of the finitary requirements are straightforward given the inductive assumptions about the actions of the requirements and involve just standard (and prompt) permitting arguments that show that if we get infinitely many candidates we eventually put one in (at an expansionary stage). The arguments for the success of the reductions constructed is a simple induction showing that they are correct at every stage (with at most finitely many exceptions for each one which are bounded by the actions of higher priority requirements). Thus the verifications for Theorem 3.8 can be carried out in IΣ_{3}.

The following theorem combines Lemmas 2.6 and 2.7.

Theorem 3.9. For every low promptly simple degree c and degrees q_{0}, …, q_{m−1}, r_{0}, r_{1} ≤_{T} c there is a recursive model M coded below c and degrees t, u and v also below c such that

(i) M is recursively isomorphic to N; (ii) For each i < m, (i)^{M} ≤_{T} q_{i}; (iii) For i, j < m, if q_{i} ≰_{T} q_{j} then (i)^{M} ≰_{T} q_{j}; and (iv) For all x ≥_{M} m^{M}, x ≰ r_{0}, r_{1}.

(v) For any even number h in M, h∨t is above h^{+}, but not above any other integer in M (except, of course, h). (In particular, there is a unique odd (respectively, even) number from M below h ∨ t.)

(vi) The join of any nontrivial distinct triple of numbers in M with v

computes u, but no join of any pair with v computes u. (vii) For any even number h ∈ M, h ∨ t ∨ v ≱ u.

Our starting point here is Theorem 5.1 of [9] to which we add requirements to take care of the new aspects of our theorem: (9) and (10) for l′ to code the second partial order that coincides with ≤_{M} on M, and (11)–(15) for t, u and v as described above. The following Theorem is then the technical result needed to verify Theorem 3.9. Note that we still have a coding of a model M of arithmetic in the partial order P that makes the domain of M the minimal elements of P which we take below to be H listed in the order of M. We may assume that all the sets U_{i} and V_{i,j} of Theorem 5.1 of [9] are uniformly below C ∈ c (and so uniformly low as in [9]) but we must also add in ordinary and prompt permitting by C to get all the sets constructed recursive in C.

Theorem 3.10. Suppose C ∈ c is low and promptly simple; P = ⟨ω,⪯⟩ is a recursive partial order; H is a recursive set of minimal elements of P; ⟨U_{i}, V_{i,j}⟩_{i∈H} is a uniformly r.e. array of pairs of sets such that the U_{i} and V_{i,j} are uniformly recursive in C (and so we can recursively in i, j calculate an index for computing V′_{i,j} from ∅′); and, for every i ∈ H, U_{i} ≰_{T} V_{i,j} (and so in particular U_{i} > 0 for i ∈ H). Then there are r.e. sets L, L′, P, Q, R, T, U, V and G_{i} (for i ∈ ω) with R = ⊕G_{i} all uniformly recursive in C such that

1. (T) : G_{i} ⊕ P ≥_{T} Q.

2. (D) : G_{i} ≱_{T} G_{j} for i ≠ j.

3. (M) : If W is r.e., recursive in R and W ⊕ P ≥_{T} Q, then there is a j ∈ ω such that G_{j} ≤_{T} W.

4. (K) : R ⊕ P is low.

5. (O) : i ⪰ j ⇒ G_{i} ⊕ L ≥_{T} G_{j}.

6. (N) : i ⪰̸ j ⇒ G_{i} ⊕ L ≱_{T} G_{j}.

7. (Z) : G_{i} ≰_{T} V_{i,j} for i ∈ H.

8. (Q) : G_{i} ≤_{T} U_{i} for i ∈ H.

9. (O^{1}) : i ≥ j ⇒ G_{h_{i}} ⊕ L′ ≥_{T} G_{h_{j}}.

10. (N^{1}) : i ≱ j ⇒ G_{h_{i}} ⊕ L′_{T} ≱_{T} G_{h_{j}}.

11. (O^{2}) : G_{h_{2j}} ⊕ T ≥_{T} G_{h_{2j+1}}.

12. (N^{2}) : G_{h_{2i}} ⊕ T ≱_{T} G_{h_{j}} for j ≠ 2i + 1.

13. (O^{3}) : G_{h_{i}} ⊕ G_{h_{j}} ⊕ G_{h_{k}} ⊕ V ≥_{T} U for i, j, k all distinct.

14. (N^{3}) : G_{h_{i}} ⊕ G_{h_{j}} ⊕ V ≱_{T} U.

15. (N^{4}) : G_{h_{2i}} ⊕ T ⊕ V ≱_{T} U.

Once again we have the problem of not being able to put numbers simultaneously into G_{h_{i}} and G_{h_{j}} as they have to be permitted by U_{h_{i}} and U_{h_{j}}, respectively. Thus we need generalized reduction procedures for the O^{1}, O^{2} and O^{3} type requirements like those used for O′ in Theorem 3.8. We include the rules for the O requirements in our list as well because of their interactions with other requirements. Again these rules will be satisfied except for finitely many numbers x. Note that the only numbers put into any of the sets G_{i} or U are followers of various requirements. Thus we restrict our attention in computing reductions to such numbers (which form an infinite coinfinite recursive set by convention).

• (O) : As in [9], for i ≻ j, to decide if x ∈ G_{j}, see if x ∈ L or x ∈ G_{i}. If not, x ∉ G_{j}. If so, let s be the stage at which x L or G_{i}. At s we appointed a new large number t_{s} targeted for L and we proceed until either x enters G_{j} or the sequence of markers that we appointed beginning with t_{s} comes to a marker that is not in L. (A new marker t′ can be appointed in this sequence only when the previous one t enters L).

• (O^{1}) : As in Theorem 3.8, for i > j, to decide if x ∈ G_{h_{j}}, see if x ∈ L′ or x ∈ G_{h_{i}}. If not, x ∉ G_{h_{j}}. If so, let s be the stage at which x entered. At s we appointed a new large number t_{s} targeted for L′ and we proceed until either x enters G_{h_{j}} or the sequence of markers that we appointed beginning with t_{s} comes to a marker that is not in L′.

• (O^{2}) : For any j ∈ ω, to decide if x ∈ G_{h_{2j+1}}, see if x ∈ T or x ∈ G_{h_{2j}}. If not, x ∉ G_{h_{2j+1}}. If so, let s be the stage at which x entered. At s we appointed a new large number t_{s} targeted for T and we proceed until either x enters G_{h_{2j+1}} or the sequence of markers that we appointed beginning with t_{s} comes to a marker that is not in T.

• (O^{3}) : For any distinct i, j and k, to decide if x ∈ U, see if x ∈ V or x ∈ G_{h_{m}} for m ∈ {i, j, k}. If not x ∉ U. If so, let s be the stage at which x entered. At s we appointed a new large number t_{s} targeted for V and we proceed until either x enters U or the sequence of markers that we appointed beginning with t_{s} comes to a marker that is not in T.

Now we list the diagonalization requirements and explain how they can be satisfied by putting numbers into the target sets (but at most one G_{h_{i}} at a time) while preserving the sets needed in the computations producing the desired diagonalizations and still obeying all the rules for the above reductions.

• (D) : We can put x into G_{j} (when permitted by the associated U_{j} if j ∈ H and by C otherwise) and preserve G_{i} (for i ≠ j) and satisfy all the O type requirements by putting x into L, L′ and T.

• (Z) : We can put x into G_{i} (when permitted by the associated U_{i} if i ∈ H and by C otherwise) and also put it into L, L′ and T.

• (N) : When we want to put x into G_{j} (when permitted by the associated U_{j} if j ∈ H and by C otherwise) and preserve G_{i} ⊕ L with i ⪰̸ j, we put x into G_{k} for k ≻ j, L′ and T. (No permissions are needed for G_{k} with k ∉ H and if k ≻ j then k ∉ H as the elements of H are all minimal elements with respect to ⪯.)

• (N^{1}) : When we want to put x into G_{h_{j}} and preserve G_{h_{i}} ⊕L′ with i ≱ j, we first try to put x into each G_{h_{k}} for each k with j < k ≤ n in reverse order where n is the index of the requirements we are considering on our master list. So our first step is to put x into G_{h_{n}}, L and T when permitted by U_{h_{n}} at s_{n} and choose a new large marker t_{n} targeted for L′, L and T. We then proceed in turn to try to put x into each G_{h_{k}} for j < k < n when permitted by U_{h_{k}}. When we get to do so at stage s_{k} we put t_{k+1} into L′, L and T and choose a new large marker t_{k}. Finally, when we have put x into G_{h_{j+1}} we wait for permission from U_{j} to put x into G_{h_{j}}.When we get this permission we put x into G_{h_{j}} and t_{j+1} into L′, L and T.

• (N^{2}) : When we want to put x into G_{h_{j}} and preserve G_{h_{i}} ⊕ T with j ≠ 2i + 1, we first try to put x into G_{h_{2k}} for j − 1 ≤ 2k ≤ n (again n is the number of the requirement we are considering) in reverse order and appoint markers targeted for T, L′ and L. We begin with the largest such k. When permitted by U_{h_{2k}} we put x into G_{h_{2k}}, L and L′ and appoint a marker t_{2k} targeted for T, L and L′. When we are permitted to put x into G_{h_{2k+1}} by U_{h_{2k+1}} we put it in and t_{2k} into L, L′ and T and appoint t_{2k−1}. We then turn to 2(k − 1) and repeat the process getting (if permitted) x first into G_{h_{2(k−1)}} and t_{2k−1} into L, L′ and T while appointing t_{2(k−1)} and then getting x into G_{h_{2k−1}}, t_{2(k−1)} into L, L′ and T while appointing t_{2(k−2)}. Finally, if we get all the required permissions, we will put x into G_{h_{j}} and the last marker appointed in this sequence into T, L and L′.

• (N^{3}) : When we want to put x into U and preserve G_{h_{i}}, G_{h_{j}} and V, we first try to put x into each G_{h_{k}} for each k ≠ i, j with k ≤ n in reverse order (n as before). We proceed as for N^{1} but first putting x into G_{h_{n}} and L, L′ and T and appointing a marker t_{n} targeted for V as well as L, L′ and T. At each successive step we put x into G_{h_{k}} for k ≠ i, j in turn in reverse order when permitted by U_{h_{k}}and the last marker appointed into L, L′, T and V and appoint a new marker until we get x into the least k ≤ n not equal to i or j at which point we also put it into U (and the final marker into L, L′, T and V).

• (N^{4}) : When we want to put x into U and preserve G_{h_{2i}}, T and V note that we also need to preserve G_{h_{2i+1}} (for O^{2}). Our plan is to put x into all G_{h_{k}} for k ≤ n and k ≠ 2i, 2i + 1 and appropriate markers into various sets. Our order is like that for N^{2}. We begin with the largest k such that 2k ≤ n and k ≠ i (without loss of generality n ≥ 2). When permitted by U_{2k} we put x into G_{h_{2k}}, L and L′ and appoint a marker t_{2k}. When x is permitted by U_{2k+1} we put x into G_{h_{2k+1}}, t_{2k} into L, L′, T and V and appoint a new marker t_{2k+1}. We then move on to 2(k − 1). Note that we skip 2i and 2i + 1 moving instead to 2i − 2 and 2i − 1 when we reach that point. At the end we put x into U and the last marker into L, L′, T and V.

It is clear that these procedures preserve the required sets for each diagonalization requirement. It is slightly complicated but reasonably straightforward to check that they also make all the desired reductions correct. For example, consider numbers put into U by action for some requirement of type N^{3} and the reduction procedure for O_{i,j,k}^{3}. Once all action by requirements of priority higher than (i.e. occurring on the master list before) max{i, j, k} have finished their positive actions, any number x put into U by an N^{3} requirement for which it is a follower must first enter one of G_{h_{i}}, G_{h_{j}} or G_{h_{k}} since it enters every G_{h_{m}} for m ≤ max{i, j, k} other than the two being preserved for the computation realizing the N^{3} requirement. Once it enters one G_{h_{n}} for n ∈ {i, j, k}, we have a sequence of markers appointed targeted for V by construction. As required by the reduction procedure, x enters U only if all of these markers enter V. Similarly, if x is a follower of some N^{4} requirement of priority less than max{i, j, k}, it must enter every G_{h_{m}} for m ≤ max{i, j, k} except for the two being preserved for the computation needed by N^{4} (i.e. 2n and 2n + 1 if the requirement we are considering is N_{n}^{4}). As another example consider O_{j}^{2} and an x which is a follower of some diagonalization requirement of priority less than 2j + 1. We argue by cases according to the type of requirement for which x is a follower. If x follows a requirement of type D, Z or N the argument is trivial since if x enters any set it enters its target for the requirement and at the same stage enters T. For the other requirements x may enter sets not mentioned in the requirement it follows but for requirements of type N^{1} and N^{3} once it enters any set, it enters T and a sequence of followers is set up as required. For N^{2} and N^{4} type requirements each time x enters a G_{h_{n}} we appoint a marker targeted for T and following the markers until either x enters the set associated with the N^{2} or N^{4} requirement completely determines which sets x enters. The other cases are similar.

Thus no further essential changes to the basic constructions in [9] for Theorem 5.1 are necessary. (As before the P restraint associated with any diagonalization requirement witness (targeted for G_{j}) is the restraint needed to maintain suitability for the witness to enter all of the sets G_{i} it might yet have to enter as the above procedure is carried out. The prompt permitting works for the M requirements as in Theorem 3.8 to get P, Q ≤_{T} C. Otherwise, we see that every number going into any other set is associated with some particular diagonalization requirements as a follower or marker. We can recursively tell which requirement any given number is associated with by the usual conventions of assigning witnesses and markers for the action of each requirement form some fixed infinite recursive set. Once the requirement is identified all the action for it putting numbers into any set is controlled by permitting the follower by members of some fixed finite set of U_{i}’s and C and so can be entirely determined recursively in C. Other aspects of the construction and verification are either like those for Theorem 3.8 or standard such as multiple permitting of a single number x by a finite sequence of nonrecursive sets U_{i}.

Finally, we conclude with a word about the verifications from the viewpoint of the amount of induction needed. The global structure of the verification is like that of Theorem 3.8. The diagonalization requirements are finitary and the others are like those for the minimal pair argument. Thus the global inductions are at worst IΣ_{3}. The arguments for the inductive steps for each requirement are simpler. One new item is the use of guessing to approximate some computation from a low oracle using the recursion theorem as well. Another, mentioned above, is the requirements needing successive permissions form a sequence of finite nonrecursive sets to succeed. Neither of these present any difficulties. Thus, once again IΣ_{3} would be sufficient to verify that the constructions succeed.

REFERENCES

[1] K. Ambos-Spies, Carl G. Jockusch, Jr., Richard A. Shore, and Robert I. Soare, An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Transactions of the American Mathematical Society, vol. 281 (1984), pp. 109– 128.

[2] C. T. Chong, Lei Qian, Theodore A. Slaman, and Yue Yang, Σ_{2} induction and infinite injury priority arguments, part III: Prompt sets, minimal pairs and Shoenfield’s conjecture, To appear in Israel Journal of Mathematics.

[3] C. T. Chong and Yue Yang, Recursion theory in weak fragments of Peano arithmetic: A study of cuts, Proceedings of the Sixth Asian Logic Conference: Beijing 1996, World Scientific, Singapore, 1998, pp. 47–65.

[4] , Computability theory in arithmetic: Provability, structure and techniques, Computability Theory and Its Applications: Current Trends and Open Problems, (P. Cholak, S. Lempp, M. Lerman and R. A. Shore, editors), Comtemporary Mathematics, vol. 257, AMS, Providence, RI, 2000, pp. 73–82.

[5] Wilfrid Hodges, Model theory, Cambridge University Press, Cambridge, 1993.

[6] W. Maass, Richard A. Shore, and M. Stob, Splitting properties and jump classes, Israel Journal of Mathematics, vol. 39 (1981), pp. 210–224.

[7] Karim Joseph Mourad, Recursion theoretic statements equivalent to induction axioms for arithmetic, Ph.D. thesis, University of Chicago, 1988.

[8] André Nies, Richard A. Shore, and Theodore A. Slaman, Definability in the recursively enumerable degrees, Bulletin of Symbolic Logic, vol. 2 (1996), no. 4, pp. 392–404.

[9] , Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society (3), vol. 77 (1998), no. 2, pp. 241–291.

[10] Richard A. Shore, The theory of the degrees below 0′, Journal of the London Mathematical Society, vol. 24 (1981), pp. 1–14.

[11] Richard A. Shore, Constructing recursively enumerable sets, Lecture notes (unpublished), Nanjing , May, 1985.

[12] Stephen G. Simpson, Subsystems of second order arithmetic, Springer-Verlag, Berlin, 1999.

[13] Robert I. Soare, Recursively enumerable sets and degrees, Springer– Verlag, Heidelberg, 1987.

[14] Yue Yang, Σ_{3} induction and 0′′′ priority arguments, in preparation.

DEPARTMENT OF MATHEMATICS, FACULTY OF SCIENCE, NATIONAL UNI-VERSITY OF SINGAPORE, LOWER KENT RIDGE ROAD, SINGAPORE 119260

E-mail: scicct@leonis.nus.edu.sg

DEPARTMENT OF MATHEMATICS, CORNELL UNIVERSITY, ITHACA NY 14853, U.S.A.

E-mail: shore@math.cornell.edu

URL: http://www.math.cornell.edu/˜ shore/

DEPARTMENT OF MATHEMATICS, FACULTY OF SCIENCE, NATIONAL UNI-VERSITY OF SINGAPORE, LOWER KENT RIDGE ROAD, SINGAPORE 119260

E-mail: matyangy@leonis.nus.edu.sg