Interpretability and definability in the recursively enumerable degrees

André Nies^{∗} University of Chicago, Chicago IL 60637

Richard A. Shore^{§} Cornell University, Ithaca NY 14853 USA

Theodore A. Slaman^{‡} University of Chicago, Chicago IL 60637

Abstract

We investigate definability in R, the recursively enumerable Turing degrees, using codings of standard models of arithmetic (SMA’s) as a tool. First we show that an SMA can be interpreted in R without parameters. Building on this, we prove that the recursively enumerable T –degrees satisfy a weak form of the biinterpretability conjecture which implies that all jump classes Low_{n} and High_{n−1} (n ≥ 2) are definable in R without parameters and, more generally, that all relations on R that are definable in arithmetic and invariant under the double jump are actually definable in R. This partially answers Soare’s Question 3.7 [35, XVI].

1. Introduction

Coding by first–order formulas in structures arising from computability theory has been a focus of attention for some time. Traditionally, such coding methods are initially used to study the complexity of the theory of the structure. Typically, one first proves that theory is undecidable by uniformly coding a sufficiently complex class of structures (with parameters). Then, usually using more sophisticated codings, undecidability of low–level fragments of the theory is established. For instance, Harrington and Shelah [10] sketched a coding of the class of Δ_{2}^{0}–partial orders in the structure R of recursively enumerable Turing degrees to prove the undecidability of T h(R). Later, Lempp, Nies and Slaman [15] showed that the Π_{3}–theory of R (as a partial order) is undecidable by a coding of the class of finite bipartite graphs with Σ_{1}–formulas. Another elaboration of the undecidability of a theory is the determination of its computational complexity. For recursion– theoretic structures which can be coded in N (like R), the expected result is that the complexity is as high as possible, namely that one can give an interpretation of true arithmetic T h(N) in the theory of the structure. To prove this, one finds coding schemes to code models of arithmetic with parameters and tries to give a first–order condition on parameters which implies that the coded model is standard. We supply such an interpretation and conditions below for R. The bare interpretability of T h(N) in T h(R) has previously been established by Harrington and Slaman and, in a different way, by Slaman and Woodin but without explicitly defining a class of standard models.

∗Partially supported by NSF Grant DMS-9500983.

§Partially supported by NSF Grants DMS-9204308, DMS-9503503 and ARO through MSI, Cornell University, DAAL-03-C-0027.

‡Partially supported by NSF Grant DMS-9500878 and a CNR Visiting Professorship at the University of Siena.

Due to the use of parameters, the types of codings mentioned so far have a very local character, so they do not seem to reveal much information about global aspects of the structure beyond the complexity of the theory. Another, seemingly unrelated, line of research is the study of definability in recursion theoretic structures A. While coding results give information about what structures can be recovered from A (possibly extended by some constants) up to isomorphism, definability results in recursion theory tell us which relations that are apparently external to A are in fact already inherent in A, namely can be defined in a first–order way. As examples, consider the definability of “arithmetic in” and “hyperarithmetic in” within the structure of D with the jump operator [14]; the jump operator itself in D [5]; or the class of promptly simple degrees in R as the class of degrees which are not half of a minimal pair [3]. Considerable previous work on the structure D of all the Turing degrees, however, has shown that coding methods can be used to prove global results restricting the possible automorphisms of the structure and that such restrictions on automorphisms can often be converted into very general definability results. Typically, this work showed that all automorphisms of D are the identity on a cone (the degrees above some fixed degree c) and that all relations on this cone that are definable in second order arithmetic are actually definable in D. (See, for example, [32], [19] and [28].) Similarly, Shore [1981] used coding methods to determine the complexity of D(≤ 0′), the (Turing) degrees below 0′. He used these methods in [29] to restrict the possible automorphisms of the structure by showing that the triple jump classes are invariant and then derived corresponding definability results.

Our first goal in this paper is to develop such global coding methods for R. For instance, we will give an interpretation of an SMA without parameters, which of course implies that true arithmetic can be interpreted in T h(R). Our second goal is to apply our global coding results to obtain invariance results for automorphisms of R and then the corresponding definability results. Once again the jump classes play a crucial role. Recall that an r.e. degree a is Low_{n} (High_{n}) if a^{(n)} = 0^{(n)} (a^{(n)} = 0^{(n+1)}).

Various methods have been developed to exploit properties of degrees in the classes Low_{1}, High_{1}, Low_{2} and its complement, \overline{Low_{2}}, in recursion theoretic constructions and there are many structural results that rely on degrees being in each of these classes. The question “which of the jump classes are definable” has motivated a fair amount of research. In particular, the methods developed suggested that there should be “natural” order theoretic definitions of Low_{2} and High_{1} in R. As an approximation, Shore and Slaman ([30], [31]) give an example of a definable class which includes Low_{2}, but is disjoint from High_{1}. In another setting, Downey and Shore [7] show that Low_{2} is definable in the r.e. tt degrees.

Here, in a uniform approach similar in outline to that previously used for D and D(≤ 0′), we establish the definability of all the classes Low_{n} and High_{n} for n ≥ 2. In fact we show that each relation P (x⃗) which only depends on each coordinate of x⃗ up to second jump and is arithmetical (i.e. its index set can be defined in N) is definable in R. A further argument then yields the definability of High_{1}. In accordance with the formulation of our second goal, the definability of these relations is obtained by considering codings of SMA’s, particularly of “effectively” coded SMA’s and the interaction of such coded models with a degree x. The interactions between a degree x and the effective SMA’s (via the sets coded in them by degrees below x) show that the isomorphism type of x within R determines its double jump. This immediately makes the relations invariant under automorphisms. The interactions between the sets so coded and the arithmetic inherent in the SMA’s translate these results into the desired ones on definability. Our improvements on Shore’s coding in [29] also enable us to improve the definability results established there for the degrees below 0′ by one jump (from triple to double).

We now discuss the coding and definability results in more detail. As mentioned above, the first step is to obtain a coding or, in the terminology of [11], an interpretation of an SMA in R without parameters. (As an example of interpretations of structures, consider the interpretation of Q on Z given by the quotient field construction.) The existence of an interpretation of N in R means that N can be considered as a “projection” of R. Similar results have been proved for many global degree structures by Slaman and Woodin (see [33]) and, in the setting of the r.e. sets, for the r.e. many–one and wtt–degrees (see [21] and [24]). On the other hand, the lattice E of recursively enumerable sets under inclusion is an example of a structure where an interpretation of true arithmetic in its theory can be given, but no interpretation of the structure N in the structure E exists (see [9] and [12]). In all three cases of r.e. degree structures, the most general concept of interpretations is used: a number is represented by an n–tuple of degrees (for some fixed n ≥ 1), modulo a definable equivalence relation. (This is also the case for the interpretation of Q in Z, where n = 2.) The example of the r.e. many-one degrees, R_{m−1}, shows that the existence of such an interpretation does not necessarily imply that the degree structure is similar to N. For example, R_{m−1} has continuum many automorphisms.

One way to show that some structure is very much like N is to prove that the two structures are biinterpretable. Of course, there is an obvious interpretation of R in arithmetic, so what is needed is an interpretation of N in R and a definable relation associating each degree x in R to codes (relative to this model) of sets of degree x. The existence of such a model and definable relation is called the biinterpretability conjecture for R (Harrington; Slaman and Woodin). In the setting of just the r.e. degrees, the conjecture is equivalent to the existence of any definable injective map f : R → N. Here N is the copy of N coded inside R, and the definability of f means that the corresponding relation on R between an argument a and a tuple b representing f(a) is definable. Such a map can be viewed as an internal coding map, sending a degree a to an “index” f(a) ∈ N all taking place inside R. An easy modification of any such f gives a standard index, i.e., for each a an e = f(a) such that deg(W_{e}) = a.

The biinterpretability conjecture has many consequences for the analysis of the structure of R. For instance, it implies that a relation on R is definable iff it is definable in arithmetic and that R is rigid (i.e. has no nontrivial automorphisms). Hence it contradicts Cooper’s recent announcement [6] that there are automorphisms of R and indeed ones that take a low degree to a nonlow one. A weaker form of the conjecture which only requires that f and N be definable from parameters has been established by Slaman and Woodin (see [33]) for D_{T} (≤ 0′) (for which Cooper has also announced the existence of a nontrivial automorphism). Even in this weaker form, the conjecture implies that the structure is a prime model of its theory, its automorphism group is countable, and a relation is definable iff it is arithmetically definable and invariant under automorphisms.

In this paper we provide another type of approximation to the biinterpretability conjecture. We show that there is a definable f : R →N such that, for each a and b,

a^{(2)} ≠ b^{(2)} → f(a) ≠ f(b).  (1.1)

(In fact, f(a) will be an index for a^{(2)} in the sense that W_{f(a)}^{(2)} = a^{(2)}.) Thus the coded model N still interacts with the structure R as a whole in a very strong way and we have obtained what we called a “global” coding result.

Let a ∼_{2} b ⇔ a^{(2)} = b^{(2)}. As an immediate consequence of (1) we obtain that

any relation C ⊆ R_{T} which is arithmetical

and invariant under ∼_{2} is definable in R.  (1.2)

We call C arithmetical if the corresponding relation on indices is. To see that this definability result follows from (1.1), note that f(C) is definable and C = f^{−1}(f(C)).

As a corollary, we obtain the definability results for Low_{n}, High_{n} (n ≥ 2) mentioned earlier, along with the definability of the relation ∼_{2} itself. As we show that, in R_{T}, x ∈ High_{1} ⇔ ∀z∃y ≤ x( y ∼_{2} z), High_{1} is also definable.

The required coding machinery is introduced in §2 along with statements of the technical results needed to carry it out. §3 considers the issue of relativizing our results to structures R^{z}, the degrees r.e. in and above z, for arbitrary degrees z. (Most relativize; some do not and so provide elementary differences between various pairs of such structures.) It also shows how to use our coding ideas to improve the known results on invariance and definability in D(≤ 0′) to be comparable to the ones derived here for R and applies these results to give a proof of Slaman and Woodin’s result that all automorphisms of D are fixed on all degrees above 0′′. The remaining sections are devoted to the constructions needed to implement the coding machinery. We begin in §4 with a presentation of the Slaman-Woodin coding scheme for interpreting partial orders (and so models of arithmetic) in R and various technical extensions and improvements. The next section (§5) provides the results needed to compare models coded in this way and so define an SMA in R. §6 combines lattice embeddings with the codings of the previous sections to produce more effective codings of models of arithmetic that are needed to show that x′′ is determined by the sets coded in such models by degrees below x. The final section, §7, which is independent of the previous ones, contains the construction of degrees below any x coding any given Σ_{3}^{X} set in the models constructed in §5. (Of course, these sets determine x′′.)

Notations and Conventions: We generally follow [35]. In particular, if x is an r.e. degree, then X denotes some r.e. set in x. Unless otherwise specified, all sets and degrees will be r.e.

2. The Coding Methods

2.1. Schemes

We intend to uniformly code objects of a certain type (e.g., 1–1 maps or models of some finitely axiomatized theory) into R. Formally, a scheme for coding objects of a certain type in R is given by a sequence of formulas φ_{0}, …, φ_{k} (in the language of partial orderings) with a common list \overline{p} of names for parameters and further free variables, as well as a formula ψ(\overline{p}) called the correctness condition. The first formula φ_{0} defines the domain of the interpreted structure (possibly a set of n-tuples) and the remaining formulas define its functions and relations (including equality if the intention is to identify elements (or n-tuples) according to some equivalence relation). The formula ψ typically says that the φ_{i} that are intended to define functions actually do so and that the relations and functions defined by the φ_{i} satisfy various axioms. Precise formulations of these notions can be found in [11, 5.3]. We content ourselves with a couple of examples.

Example 2.1. A scheme S_{g} for defining a function g on a particular domain is given by a formula φ_{0}(x; \overline{p}) defining the domain of the function; one φ_{1}(x, y; \overline{p}) defining the relation between inputs and outputs; and a correctness condition ψ(x, y; \overline{p}) which says that a function is actually defined on the intended domain: ∀x(φ_{0}(x; \overline{p}) → ∃!y ϕ_{1}(x, y; \overline{p})).

Example 2.2. A scheme S_{M} for coding models of some finitely axiomatized fragment P A^{−} of Peano arithmetic (in the language L (+, ×)) is given by the formulas

φ_{0}(x, \overline{p}), φ_{1}(x, y, z; \overline{p}), φ_{2}(x, y, z; \overline{p})

and a correctness condition ψ(\overline{p}) which says that φ_{1} and φ_{2} define binary operations on the set \{x : φ_{0}(x; \overline{p})\} which satisfy the finitely many axioms of P A^{−}. In our applications, the axioms ensure that M has a standard part.

In general, a coding scheme S_{X} introduces a new type of object. The parameters \overline{p} satisfying ψ(\overline{p}) code an object, and S_{X} acts as a decoding key. Using this coding, it becomes possible to quantify over objects of the new type (a form of second order quantification) in the first–order language of R. We can also perform basic mathematical operations on objects of two possibly different types and obtain a uniform way of coding objects of a yet different type (for example, we can define the composition of maps). Furthermore, we can express basic relationships between coded objects by first order conditions on codes; for instance we can express the relationship “g is a partial map from M_{0} to M_{1}”, where M_{0}, M_{1} are coded via S_{M} and g is coded via S_{g}, by formulas of R. We use the following convention throughout: If a scheme S_{X} is given, variables X, X_{0}, etc. denote objects coded by this scheme for a particular parameter list \overline{p} satisfying the correctness condition. If it is necessary to mention the parameters explicitly, we write X(\overline{p}), X_{0}(\overline{p}), etc. We say that \overline{p} codes X(p̄) via S_{X}.

Definition 2.3. A class C of structures with a common signature is uniformly definable in R if, for some scheme S, C is the class of structures coded via S as the parameters range over R. An object X is definable via S if X is coded via S with a particular choice of parameters.

2.2. A Scheme for Coding SMA’s in R

We now describe a particular coding of the type described in Example 2.2. We begin with special class of definable antichains in R.

Definition 2.4. A set G ⊆ R is called an SW–set (short for Slaman–Woodin set) above b if, for some parameters p, q, r ∈ R, G is the set of minimal degrees x, b ≤ x ≤ r, such that q ≤ x ∨ p. If b = 0, we call G simply an SW-set and may omit b from the list of parameters.

Note that the class of SW–sets (above some b) is uniformly definable in R. Slaman and Woodin (unpublished) constructed sets of this kind (we supply a construction and proof in Theorem 4.1) and used them to give a uniform coding of an arbitrary recursive partial order ≤_{P} in R by proving that there exists a u.r.e. sequence ⟨g_{i}⟩ of degrees and an l ∈ R such that {g_{i} : i ∈ ω} is an SW–set and, for each i, j ∈ ω, i ≤_{P} j ⇔ g_{i} ≤ g_{j} ∨ l. They also gave a coding of (ω, +, ×) in a particular partial order P_{A} which, together with their coding of arbitrary recursive partial orders in R, determines a scheme S_{M}(\overline{p}) as in Example 2.2 such that some coded model M is standard. To construct this particular partial order P_{A} coding arithmetic, one starts with a countable antichain of minimal elements p_{n} which will represent the numbers n. Then, for each n, m ∈ ω one adds an element c_{n,m} to P_{A} which represents the pair (p_{n}, p_{m}). Next, one adds ascending chains of lengths 2 and 3, respectively, from p_{n} to c_{n,m} and from p_{m} to c_{n,m}. Finally, to code addition, add a chain of length 4 from p_{n+m} to c_{n,m} and for multiplication, add a chain of length 5 from p_{n×m} to c_{n,m}. We provide the recursion theoretic constructions in §4.

The scheme S_{M}(\overline{p}) = S_{M}(p, q, r, ℓ) (or S_{M}(b, p, q, r, ℓ)) will be extended later by a further correctness condition. For now, we just assume the general correctness condition from Example 2.2. Since the elements of a model M are members of some SW–set, they form an antichain in R. We use subscripting or superscripting by M to indicate the interpretations in M of the usual objects of arithmetic. In particular, i^{M} denotes the (i+1)^{st}element of M for i ∈ ω and +_{M} denotes addition in M.

The above considerations show that some coded M is standard. Moreover, combining the Slaman–Woodin construction with permitting, we will be able to produce a coding with the parameter r below any given nonzero a. Thus all the elements of M are below a. In addition, we can make r (and even r ∨ p ∨ q) low (Theorem 4.7).

For an arbitrary M (standard or not), we say that M is coded below a if all elements of M are ≤ a and M is low if all elements are low. (This does not restrict the parameters used for coding M.)

2.3. Comparison Maps Between Coded Models

After finding a way to code SMA’s with particular parameters in a structure A, we would like to find a first order condition on parameters that picks out a subclass of coded models which are standard. This would give an interpretation of true arithmetic in the theory of A. Various ways to find such a condition have been used in other settings. We employ the method of comparison maps. A comparison map between M_{0} and M_{1} is a 1–1 partial map M_{0} → M_{1} which extends the isomorphism between the standard parts. We intend to find a uniform way to define such maps between any two (good) models M_{0}, M_{1} coded in R: Then, since some model M^{∗} is standard, a (good) model M is standard iff for each (good) M′, such a map g : M → M′ exists which is total.

Theorem 2.5. There is a scheme S_{g} such that ∀M_{0}∀M_{1}∃g, g is a comparison map from M_{0} to M_{1}.

Keep in mind that the current definition of S_{M} will be extended by one more correctness condition to make the scheme “good”. This condition will be determined during the proof. The precise way the scheme S_{g} is obtained will be of little relevance for the rest of the paper.

Proof. We combine recursion theoretic methods with coding tricks. As the recursion theoretic component, we use the following lemma to develop a preliminary scheme S_{h} which allows us to uniformly define the natural embedding M_{0} → M_{1}, if both M_{0}, M_{1} are low and M_{0} is standard. Interpolating with several such embeddings and their inverses, we will find a uniform way to define comparison maps.

Lemma 2.6. Suppose q_{0}, …, q_{m−1}, r_{1} are nonzero low degrees. Then there is a low standard M such that for i, j < m, i^{M} ≤ q_{i} and q_{i} Θ q_{j} ⇒ i^{M} Θ q_{j} while for j ≥ m, j^{M} Θ r_{1}.

To prove Theorem 2.5 (assuming Lemma 2.6 which is a special case of Theorem 5.1), we first describe how to uniformly define the isomorphism h̃ between the initial segments of M_{0} and M_{1} up to n^{M_{i}}, for each n ∈ ω. Let q_{i} = i^{M_{0}} for i < n and q_{i} = (i − n)^{M_{1}} for n ≤ i < 2n and let r_{1} be the appropriate parameter in the definition of M_{1} bounding all the elements of the model. Note that (q_{i})_{0≤i<n} and (q_{i})_{n≤i<2n} are antichains. Now let M be the SMA obtained applying the Lemma. For x ∈M_{0} and y ∈ M_{1} we wish to define the map taking x to y if and only if x = i^{M_{0}} and y = i^{M_{1}} for some i < n. Suppose then that x ∈ M_{0} and y ∈ M_{1}. We claim that by the incomparability requirements of Lemma 2.6,

(∃i < n)(i^{M_{0}} = x & y = i^{M_{1}}) ⇔ (∃z ∈ M)(x is the M_{0}-least w
such that z ≤_{T} w & y is the M_{1} least v such that z +n^{M} ≤_{T} y).

The implication from left to right is immediate from the conditions of Lemma 2.6 with z = i^{M}. For the converse, let z ∈ M be as described. Since z +n^{M} ≤_{T} y ∈M_{1}, the conditions on r_{1} in the Lemma guarantee that in M, z+n < 2n and so z < n in M. The conditions on q_{j} for j < n now guarantee that, if i^{M} = z (necessarily with i < n), then the M_{0}-least w Turing above z is i^{M_{0}}. Similarly, those on q_{j} for n ≤ j < 2n guarantee that the M_{1}-least v Turing above z + n^{M} is i^{M_{1}} as required.

So h̃ can be defined via the formula

φ̃(x, y; \overline{p}_{0}, \overline{p}_{1}, \overline{p}, n) ≡ [n ∈ M(\overline{p}) ∧ x ∈ M_{0} ∧ y ∈ M_{1} ∧ ∃z ∈ M(\overline{p})

(x is the M_{0}-least w such that z ≤_{T} w & y is the M_{1} least v such that z + n^{M} ≤_{T} y)].

(We denote M(\overline{p}_{i}) by M_{i}.)

Clearly h̃ satisfies the following condition, which can be expressed as a first order correctness condition α on the parameters involved:

h̃(0^{M_{0}}) = 0^{M_{1}} ∧ (∀x ∈ M_{0})[h̃(x +_{M_{0}} 1) is defined ⇒
h̃(x) is defined and h̃(x +_{M_{0}} 1) = h̃(x) +_{M_{1}} 1]  (2.1)

Now, to obtain the desired preliminary scheme S_{h}, we take the union of such maps defined by parameters satisfying the condition α:

φ(x, y; \overline{p}_{0}, \overline{p}_{1}) ≡ (∃\overline{p})(∃n)α(\overline{p}_{0}, \overline{p}_{1}, \overline{p}, n) ∧ φ̃(x, y; \overline{p}_{0}, \overline{p}_{1}, \overline{p}, n).

If M_{0} is standard, there is, by (2.1), a unique map defined in this way, namely the natural embedding M_{0} → M_{1}. Because we are currently only interested in the case that M_{0} is standard, we impose as a correctness condition for the scheme S_{h} that the relation defined by φ be an embedding M(\overline{p}_{0}) → M(\overline{p}_{1}) which satisfies (2.1). (Note that we have not yet expressed the standardness of M_{0} by a first order condition on parameters.)

We now define the scheme S_{g} to code comparison maps between any two models M_{0}, M_{1}, at the cost of adding an additional correctness condition to the scheme S_{M}.

Recall that, by definition, M is coded below c if the elements of M are ≤ c. The following notion is a first order approximation to the lowness of c. We say that c is good via M^{∗} if the model M^{∗} which is coded below c can be embedded via the scheme S_{h} into any other model coded below c, i.e.,

(∀M coded below c)(∃h : M^{∗} → M)[h is total].

(Recall that h is 1–1 by the correctness condition on S_{h}.) As mentioned above, some M coded below c is standard, so M^{∗} must be standard. If c is low, we can (by Lemma 2.6) take as M^{∗} any SMA coded below c, so each low degree is good. Thus we can safely add as a correctness condition in S_{M}(b, p, q, r, l) that the upper bound r is good via M, i.e., M is coded below r and can be embedded via S_{h} into any other model coded below r.

Since we can make r low, there are parameter lists satisfying the condition; moreover, any model coded in that way will be standard. Now, existentially quantifying over such parameter lists, we obtain an interpretation of true arithmetic in T h(R).

For clarity, temporarily call the extended scheme S_{M}^{∗}. The scheme S_{g} to uniformly define a comparison map (i.e., the isomorphism) between two models M_{i}(\overline{p}_{i}) coded by S_{M}^{∗} is obtained by interpolating with two low models.

By the new correctness condition, r_{i} ∈ \overline{p}_{i} is good via M_{i}. Choose low standard models M_{i}^{L} coded below r_{i} via S_{M}, and let h_{i} : M_{i} → M_{i}^{L} be the natural embedding coded via S_{h}. We already know that the isomorphism h : M_{0}^{L} → M_{1}^{L} is coded via S_{h}. Now the isomorphism M_{0} → M_{1} equals h_{1}^{−1} ∘ h ∘ h_{0}, and it can then be defined via a scheme S_{g} including parameters to code all the models involved. With any choice of parameters coding intermediate models M_{i}^{L}, the composition must be the isomorphism M_{0} → M_{1} by the correctness condition in S_{h} requiring that h be an embedding of models. This proves Theorem 2.5 , assuming Lemma 2.6. □

We are now ready to obtain a parameterless interpretation of N.

Theorem 2.7. (i) There is a uniformly definable class C_{st} of coded standard models of arithmetic. (ii) Let Ñ = \{(x, \overline{p}) : M(\overline{p}) ∈ C_{st}∧ x ∈ M(\overline{p})\}. The equivalence relation Q on Ñ given by

(x, \overline{p})Q(y, \overline{q}) ⇔ (∃n ∈ ω)[x = n^{M(\overline{p})} ∧ y = n^{M}(\overline{q})]

is definable in R. (iii) An SMA N can be defined on the set of equivalence classes Ñ/Q without parameters.

Proof. (i) By the above, the scheme S_{M} (which from now on includes the additional correctness condition) only codes SMA’s. (ii) For (x, \overline{p}), (y, \overline{q}) ∈ Ñ,

(x, \overline{p})Q(y, \overline{q}) ⇔ (∃g)[g : M(\overline{p}) → M(\overline{q}) ∧ g(x) = y].

(iii) Addition and multiplication of equivalence classes representing numbers in Ñ can be carried out by choosing tuples with a common parameter list \overline{p} and carrying out the operations in M(\overline{p}). For instance,

[(x_{0}, \overline{p}_{0})] + [(x_{1}, \overline{p}_{1})] = [(x_{2}, \overline{p}_{2})] ⇔ ∃\overline{p} ∃x̃_{0}, x̃_{1}, x̃_{2} ∈ M(\overline{p})

( ⋀_{i=0,1,2}(x_{i}, \overline{p}_{i})Q(x̃_{i}, \overline{p}) ∧ x̃_{0} +_{M(\overline{p})} x̃_{1} = x̃_{2}). □

2.4. Biinterpretability of R and N up to second jump

In this paragraph, we develop the additional coding tools needed to obtain a definable map f : R → N such that a^{2} ≠ b^{2} ⇒ f(a) ≠ f(b). We first concentrate on an easier result:

For each a, the class {x : x^{(2)} = a^{(2)}} is invariant  (2.2)

under automorphisms of R.

Recall that (2.2) is a consequence of (1.2) of the introduction which in turn is a consequence of the strongest formulation (1.1). Combining the methods developed here with the comparison map machinery will lead us to the full result (1.1).

We now consider SMA’s which are also equipped with an “effectively” coded successor function. This way of coding the successor function was first used by Shore in [26].

Definition 2.8. An effective SMA is an SMA G above b with u.r.e. elements {g_{i} : i ∈ ω} (listed in the order of the model G) which is coded by parameters b, p, q, r, e_{0}, f_{0}, e_{1}, f_{1} such that

• for each i, (g_{2i} ∨ e_{1}) ∧ f_{1} = g_{2i+1}, and (g_{2i+1} ∨ e_{0}) ∧ f_{0} = g_{2i+2}.

Note that the sequence ⟨g_{i}⟩ is an antichain. Moreover, g_{2i+1} Θ f_{0} and g_{2i+2} Θ f_{1}: If, say, g_{1} ≤ f_{0}, then g_{2} = (g_{1}∨e_{0})∧f_{0} ≥ g_{1}. It follows that we can recognize in a first–order way which pair of parameters e_{i}, f_{i} to choose to obtain the successor operation σ in the model: for g, h ∈ G,

σ(g) = h ⇔ for some i ≤ 1, g Θ f_{i} and h = (g ∨ e_{i}) ∧ f_{i}.

So we obtain a scheme for coding effective SMA’s, denoted by S_{G}.

Our coding is effective in the sense that there is a way to find an index for g_{n} in an arithmetically not too complex way. The reason is that for n > 0, g_{n} is simultaneously a minimal element in the set {x ≤ r : x ∨ p ≥ q} and, as an infimum, the greatest element in the set {x : x ≤ (g_{n−1} ∨ e_{i}) ∧ x ≤ f_{i}} (i = n mod 2)). Both sets have quantifier free definitions from parameters in the language of uppersemilattices. Using these facts, we will show in Lemma 2.13 that, if a low upper bound on all parameters involved exists, then g_{i} = deg_{T} {β(i)}^{R} for some map β ≤_{T} ∅′′.

Now, the idea for proving the invariance result (2.2) is to look at the interaction of a with sets of numbers coded as subsets of effective SMA’s. Since it is too much to ask that all parameters needed be below a, we use the following weaker requirement:

Definition 2.9. Let a > 0 and u > 0 (u will be noncappable in the applications).

(i) G is coded below (a, u) if r ≤ a and all parameters involved are ≤ u. (ii) A set X ⊆ ω is represented below (a, u) if there is a G coded below (a, u) and there are further parameters c, d ≤ a such that

X = {i : c ≤ g_{i} ∨ d}.

We say that a is automorphic to c if there is an automorphism φ of R such that φ(a) = c. Consider the following class of sets:

S(a) = {X : (∀u)[u noncappable ⇒ X is represented below (a, u)]}. (2.3)

Then

a automorphic to c ⇒ S(a) = S(c).  (2.4)

The reason is that an automorphism π such that π(a) = c maps a representation of X below (a, u) to one below (c, π(u)). To establish the invariance fact (2.2) we prove the following:

Theorem 2.10. If a = deg(A), then S(a) = Σ_{3}^{0}(A).

Thus {x : x ∼_{2} a} = {x : Σ_{3}^{0}(X) = Σ_{3}^{0}(A)} is invariant under automorphisms by (2.4). One immediate corollary shows that many relations are invariant.

Definition 2.11. An n-ary relation P (x_{1}, …, x_{n}) on R is invariant under the double jump if, whenever R ⊧P (x_{1}, …, x_{n}) and x′′_{1} ≡_{T} y′′_{1}, …, x′′_{n} ≡_{T} y′′_{n}, it is also true that R ⊧P (y_{1}, …, y_{n}). (In these circumstances, we also say that P is invariant under ∼_{2}.) We say that P is invariant in R if whenever R ⊧P (x_{1}, …, x_{n}) and φ is an automorphism of R, R ⊧P (φ(x_{1}), …, φ(x_{n})).

Corollary 2.12. Any relation on R which is invariant under the double jump is invariant in R. □

The Theorem is established in a sequence of auxiliary results. First, to prove that S(a) ⊆ Σ_{3}^{0}(A), we exploit the effectivity of our coding of SMA’s along with the fact that there is a low noncappable degree.

Lemma 2.13. Suppose u is low.

(i) If G is coded below (a, u) then there is a total function β ≤_{T} ∅′′ such that g_{i} = deg{β(i)}^{A}.

(ii) If X is represented below (a, u) then X is in Σ_{3}^{0}(A).

Thus, since we quantify over all possible noncappable u in the definition of S(a), S(a) ⊆ Σ_{3}^{0}(A).

Proof. (i) Recall that all the g_{i} are below r which is itself low. Thus, using ∅′′ as an oracle, we can determine if, for given e, {e}^{R} is total. Since R ≤_{T} A, it will be enough to find a function β such that the conclusion of (i) holds with R in place of A. Let β(0) be some e such that g_{0} = deg({e}^{R}). Inductively, assume we have already determined β(i), for even i, say. To find β(i + 1), look for a j such that {j}^{R} is total, Z = {j}^{R} ≤_{T} U and the T –reductions which determine the degree g_{i+1} holds for Z : Q ≤_{T} Z ⊕ P, Z ≤ {β(i)}^{R} ⊕ E_{1} and Z ≤ F_{1}. Since all the relevant oracle sets are low and lowness indices for them are known, to search for j we only have to answer some Σ_{3}^{0}–questions, i.e., carry out a search for j and for three indices of T –reductions recursively in ∅′′. We know this search will terminate because G is an effective SMA. (ii) Note that i ∈ X ⇔ C ≤_{T} {β(i)}^{A} ⊕ D. The clause on the right is a Σ_{3}^{0}(A) property of i since C, D ≤_{T} A. □

We now address the more delicate inclusion relations Σ_{3}^{0}(A) ⊆ S(a). For any Σ_{3}^{0}(A) set X, and any noncappable u, we have to find a G coded below (a, u) so that X can be represented using G. First, we show that appropriate low effective SMA’s exist. We use the fact from [3] that noncappable degrees are the degrees of promptly simple sets to obtain enough permitting by U.

Theorem 2.14. For any a ≠ 0 and for any promptly simple u, there is an effective SMA G coded below (a, u) such that ⟨g_{i}⟩ is a u.r.e. sequence and ⊕_{i}g_{i} is low.

This follows from Theorem 6.1. Then we prove that all Σ_{3}^{0}(A)–sets can be represented below (a, u) using a model as above. Note that the sequence ⟨g_{i}⟩ from Theorem 2.14 satisfies the hypotheses of the following Theorem which we prove later as Theorem 7.1.

Theorem 2.15. If ⟨g_{i}⟩ is a u.r.e. antichain, ⊕_{i}g_{i} is low and (∀i)[a Θ g_{i}], then for each Σ_{3}^{0}(A)–set S there are c, d ≤ a such that S = {i : c ≤ g_{i} ∨ d}.

The proof of Theorem 2.14 is another extension of the techniques introduced by Slaman and Woodin, incorporating methods of Downey and Shore [8] while the proof of Theorem 2.15 uses methods of Nies [20] and is independent of the rest of the paper. Clearly, these two theorems together show that Σ_{3}^{0}(A) ⊆ S(a) and so establish Theorem 2.10. □

We now apply the fact that S(a) = Σ_{3}^{0}(A) to prove that, up to second jump, the biinterpretability conjecture holds for R.

Theorem 2.16. There is a definable map f : R →N such that (∀a)[W_{f(a)}^{(2)} = a^{(2)}].

Proof. To give a first–order definition of f, we have to provide an appropriate definable relation R_{f} which holds between degrees a and tuples (i, \overline{p}) representing an equivalence class in N. Note that a^{(2)} is the least degree v such that each set in Σ_{3}^{0}(A) is r.e. in v. (If the last statement holds for v, then A^{(2)} and \overline{A^{(2)}} are r.e. in v.) But Σ_{3}^{0}(A) = S(a), so if we had a first–order way to obtain, from the degree a, representations of S(a) “inside” N we could define R_{f} since finding an index for such a least v is an arithmetical process.

Fix a and a list \overline{p} satisfying the correctness condition for S_{M} (so M(\overline{p}) is standard). If a = 0, we assert that R_{f}(a, (i_{0}, \overline{p})) holds, where i_{0} is some fixed index for the empty set. If a ≠ 0, consider the following representation of S(a) as a subset of M(\overline{p}):

S(a, \overline{p}) = \{j ∈ M(\overline{p}) : (∀u noncappable)[\{n : M(\overline{p}) ⊧ n ∈ W_{j}^{ϕ^{(3)}}\} (2.5)

is represented below (a, u)}].

Thus we need to show that “j ∈ S(a, \overline{p})” is definable. This follows from the existence of comparison maps between any two SMA’s whether effective or not. We simply note that

j ∈ S(a, \overline{p}) ⇔ (∀u noncappable)(∃G coded below (a, u))
(∃g : G ↔ M(\overline{p}))[g^{−1}(W_{j}^{∅^{(3)}}) is represented below (a, u) via G].

As g can be uniformly defined via the scheme S_{g}, the right hand side can be expressed in a first–order way. Finally, let R_{f}(a, (i, \overline{p})) hold if i is the least element of M(\overline{p}) such that for each j ∈ S(a, \overline{p}), W_{j}^{∅^{(3)}} is r.e. in (W_{i})^{(2)} and, if the same holds for i′ ∈ M\overline{p} then W_{i}^{(2)} ≤_{T} W_{i′}^{(2)}.

Since “j ∈ (a, \overline{p})” is definable in R and the other expressions involved can be expressed in the SMA M\overline{p}, R_{f} is definable. □

We now derive some consequences of Theorem 2.16. Consider the following equivalence relations: x ∼ _{k}y ⟺ x^{(k)} = y^{(k)}. From Theorem 2.16, the following general definability result can be derived.

Corollary 2.17. If C ⊆ R^{n} is a relation which is invariant under ∼_{2} such that the corresponding relation on indices of r.e. sets is arithmetical, then C is definable in R without parameters.

Proof. Since C invariant under ∼_{2}, it is sufficient to show that the image relation f(S) is definable in N, where f : R → N is the map of Theorem 2.16. But f(C) is arithmetical as a relation on N, since f is definable and C has an arithmetical index relation. □

We give a few more examples of such relations.

Corollary 2.18. For each k ≥ 2 the relation x s_{k}y is definable in R. □

Corollary 2.19. For each c r.e. in and above 0′′, the set of r.e. degrees a with double jump c is definable in R. □

Corollary 2.20. The jump classes Low_{n} = {a| a^{(n)} = 0^{(n)}} and High_{n} = {a| a^{(n)} = 0^{(n+1)}}, are definable in R for n ≥ 2. □

The second example gives a partition of R_{T} into infinitely many definable automorphism bases, since by [1] already each first-jump class is an automorphism base. So each second-jump class D is a union of orbits, and each automorphism is determined by its action on D.

The definability of ∼_{2}, together with the Robinson Jump Interpolation Theorem (see [36]) and a result by Soare and Stob [36] implies the definability of High_{1}. For the rest of this section the letters u, v, w, s, t denote degrees which are not necessarily r.e. Recall that v is REA in u if v ≥ u and v is r.e. in u.

Theorem 2.21. In R, x ∈ High_{1} ⇔ (∀y)(∃z ≤ x)[z ∼_{2} y]

Proof. We quote the Robinson Jump Interpolation Theorem (RJIT): if w ≤ v are r.e. degrees, s ≥ w′ and s is r.e. in v, then s = t′ for some r.e. t such that w ≤ t ≤ v. The RJIT will be used in relativized form, i.e. with “r.e.” replaced by “REA in v” for some v.

First suppose x ∈ High_{1}. Given y, let s = y^{(2)}. We apply the RJIT two times according to the following diagram. The lowest line (except for the first column) contains the degree to which we are relativizing the RJIT, and each step to the right means going down by one jump.

x′ x
s  t z
0^{(2)}  0′ 0
x′ = 0^{(2)} x 0

In words, first we relativize the RJIT to x in order to obtain t′ = s with t REA in s. We use the highness of x to ensure that s is r.e. in x′. Now, by the unrelativized RJIT, t = z′ for some r.e. z ≤ x. So z ∼_{2} y.

Now suppose x ∉ High_{1}, i.e. x′ < 0′. By the main result in [36], relativized to x′, there exists a u REA in 0′ such that u is not r.e. in x′. Now by a twofold application of the RJIT, first relativized to 0′ and then unrelativized, u = y′ for some y. But u = z′ for some z ≤ x implies that u is r.e. in x′. Λ

3. Relativizations of R and Other Structures

We now use our coding methods to investigate definability in relativizations of R and to distinguish among different relativizations. We will also see how they can be combined with Shore’s methods from [29] to improve the invariance and definability results for D(≤ 0′), the degrees below 0′, derived there by one jump to get ones analogous to the ones established here for R. The invariance results for the double jump in D(≤ 0′) will then be used to prove Slaman and Woodin’s result that every automorphism of D fixes every degree above 0′′. In this section degrees will not be r.e. unless explicitly so specified.

We begin with relativizations of R: R^{z} is the partial order of degrees REA in z. We show that, as a consequence of relativizations of our coding results, z^{(2)}≢_{T} w^{(2)} implies that R^{z} Æ R^{w}. Moreover, under suitable additional conditions, the two structures are not even elementarily equivalent. These results are analogous to those of Shore for relativization of D(≤ 0′) [26] and are improvements of similar results for relativizations of R in [27].

The relativization of a definition or result such as the ones above to a degree z is obtained by replacing the notions “recursive” by “recursive in z” and r.e. by “REA in z” (recursively enumerable in and above z). In particular, the role of 0 is now played by z = deg(Z) (which we also denote by 0).

An examination of the arguments in Sections 2, 4, 6 and 7 reveals that Theorem 2.10 relativizes:

If a ∈ R^{z}, then S(a) = Σ_{3}^{0}(A).  (3.1)

For instance, Lemma 2.13, which showed that S(a) ⊆ Σ_{3}^{0}(A), relativizes because now in the search to find β(i + 1) we have to evaluate Σ_{3}^{0}(Z) questions, so we obtain a map β ≤_{T} Z^{(2)}. But Z is recursive in all sets involved, so, as before, X ∈ Σ_{3}^{0}(A) if X is represented below (a, u), where u′ = z′.

Theorem 3.1. If z^{(2)}≢_{T} w^{(2)}, then R^{z} Æ R^{w}.

Proof. It is sufficient to recover Σ_{3}^{0}(Z) from the structure R^{z} in a way that depends only on the isomorphism type of the structure. To do so, note that

Σ_{3}^{0}(Z) = ⋂_{a≠0} S(a)  (3.2)

since one can apply (3.1) to some a ∈ R^{z} − {0} such that a′ = z′. □

We now consider definability issues for relativized versions of R and implications for their theories. One can check that the comparison map machinery, along with its extension to effective SMA’s, relativizes to any R^{z} (via the same schemes). In particular, the correctness condition in S_{M} on \overline{p} that the parameter r be good implies that M\overline{p} is standard, and Theorem 2.7 defines a standard model N^{z} in each relativization R^{z}. However, when we consider relativizing the discussion of sets coded in the model N^{z}, we can no longer simply use an index in N^{z} as a code. Instead we use pairs of degrees outside the model and interpret the sets coded as prescribed by Theorem 2.15. Thus, while the notions of invariant and invariant under the double jump remain the same as in the unrelativized case, we must adjust our definition of “definable in arithmetic” accordingly. We now allow free set variables in our formulas ψ and the usual binary relation symbol ∈ for membership (i.e., the membership of a degree coding a natural number in these coded sets).

An n-ary relation P on degrees is then said to be definable in arithmetic if there is such a formula ψ such that P = {⟨deg(X_{1}), …, deg(X_{n})⟩|N ⊧ ψ(X_{1}, …, X_{n})}. (Of course, this agrees with the definition in terms of indices when all the sets X_{i} are r.e.) With this definition, we immediately get the appropriate relativized version of Theorems 2.7 and 2.16 and most of the associated corollaries:

Theorem 3.2. For every degree z, there is a definable copy N^{z} of the structure (N , +×) in R^{z}and a definable relation associating each degree a REA in z with codes for sets of degree a′′. □

Corollary 3.3. For every degree z, any relation on R^{z} which is invariant under the double jump is invariant in R^{z}. □

Corollary 3.4. For every degree z, any relation on R^{z} which is definable in arithmetic (as redefined above) and invariant under the double jump is definable in R. □

Corollary 3.5. For every degree z, and for each k ≥ 2 the relation x s_{k}y defined by x^{(k)} ≡_{T} y^{(k)} is definable in R^{z}. □

Corollary 3.6. For every degree z, the jump classes Low_{n}^{z} = {a ∈ R^{z}| a^{(n+1)} = z^{(n+1)}} and High_{n}^{z} = {a ∈ R^{z}| a^{(n)} = z^{(n+1)}} are definable in R^{z} for n ≥ 2. □

Corollary 3.7. For every degree z, the jump class High_{1}^{z} = {a ∈ R^{z}| a′ = z′′} is definable in R^{z}. □

On the other hand, the proofs of the last part of Theorem 2.16 and of Corollary 2.19 do not relativize. Indeed, any attempt at talking about maps from degrees to indices or even any form of unique codes for sets of given degrees is doomed to failure as any function definable in R^{z}(and so arithmetic) taking degrees d to (unique) representatives of d would contradict arithmetic determinacy. The same is true even if we try to associate degrees (REA in z) with integers (in the standard model of arithmetic defined in R^{z}) up to any jump:

Theorem 3.8. There are degrees z such that there is no k ∈ ω and no map f from R^{z} to N^{z}, the isomorphic copy of N definable in R^{z}, which is definable in R^{z}such that f(a) = f(b) implies that a^{k} ≡_{T} b^{k}.

Proof. If not, there would be a k and a well-ordering of R^{z^{(k)}} which is Borel definable from z. Then using the coding of reals by parameters in R^{z^{(k)}}, one could map the degree z to a real X in a uniformly Borel way so that this map is not constant on any cone. For example, order the reals coded in R^{z^{(k)}} by the ordering of the parameters which code them and choose the first real X such that every real coded in R^{z} is similarly coded in R^{x}. The existence of such a map contradicts Borel determinacy. □

Thus, in general, no analog of the second part of Theorem 2.16 is possible for R^{z}. A similar argument shows that the analog of Corollary 2.19 also fails:

Theorem 3.9. There are degrees z and c with c REA in z′′, such that the set of degrees in R^{z} with double jump c is not definable in R^{z}.

We can, in fact, use the relativized results that do hold for every z to improve the nonisomorphism results derived above to nonelementary equivalence for certain z and w. A subset Z of the natural numbers N is implicitly definable if, for some formula ψ_{Z} in the language L(+, ×, P) with a symbol P for a unary predicate, Z is the unique set satisfying the description. Formally, for each X ⊆ ω

(N, X) ⊧ ψ_{Z} ⇔ Z = X.

In the literature, such sets Z are also called “arithmetical singletons”. For example, each arithmetical set and ∅^{(ω)} are implicitly definable. It is easy to verify that the class of implicitly definable sets is closed under the equivalence relation of having the same arithmetical degree.

Theorem 3.10. If Z is implicitly definable (for example, Z = ∅) and R^{z} ≡ R^{w} then z′′ = w′′.

Proof. It is easy to see that there is sentence θ in L(+, ×, P) such that

(N , X) ⊧ θ ⇔ Z^{(2)} =_{T} X^{(2)}.

Of course, in R^{z} the sentence saying that there is a (code for a) set in N^{z} satisfying θ and that this set is in L_{2}^{z} is true. The only way this sentence can hold in some other R^{w} is for z and w to have the same double jump. □

Note that some condition on z and w is needed in this theorem since, by Borel determinacy, there is a degree z such that R^{z} ≡ R^{w} for every w ≥ z.

Turning next to D(≤ 0′), the degrees below 0′, we briefly explain how the coding procedures here can be used to improve Shore’s invariance and definability results in [29] by one jump to get results for D(≤ 0′) analogous to the ones provided in §2 for R. (References in the discussion below refer to [29].) Effective standard models of arithmetic are coded by intervals of degrees which are lattices using Lerman’s results [17, XII] on lattice initial segments of D(≤ 0′). The crucial change needed is simply to require (as is part of the definition of Slaman-Woodin sets) that the elements of the model M coded below some e also join some p < e above some other q < e. This makes the collection of (indices for) the elements of M a Σ_{3}^{E} set rather than one recursive in e^{(3)}. Thus the function h (of Theorem 1.1) enumerating these indices is recursive in e′′ rather than e^{(3)}. We can now argue that the structure of the degrees below any a ≤ 0′ determines a′′ (rather than just a^{(3)}) and so the double jump is invariant in D(≤ 0′) as it is in R.

By Lemma 1.3, if f is r.e. in and strictly above e, any Σ_{3}^{E} set S can be coded in M by a pair x, y < f (with i ∈ S ⇔ i^{M} ≤ x, y). Consider then any a ≤ 0′. If a′′ = 0′′ then only Σ_{3} sets can be coded by pairs below a in effective standard models which are segments [b, e] below a. On the other hand, if a is not Low_{2} then we argue that the sets coded by pairs below a in models given by segments below a determine a′′: For g < a let

H(g) = lub{deg(X)| Every set coded by a pair below g in an effective standard model given by a segment below g is Σ_{1}^{X}}.

As every set in H(g) is Σ_{3}^{G}, H(g) ≤ g′′≤ a′′. Thus it suffices to show that every x ≥ 0′′ which is r.e. in a′ is actually H(g) for some g < a as the least upper bound of such x’s is a′′ by standard density type results on r.e. degrees (relativized to a′). This then implies that a′′ = lub{H(g)|g < a} as required to determine a′′ from D(≤ a). Now consider any such x. The proof of Theorem 2.1 shows that there are degrees k < b < e < g < a such that k′′ = x; g is 1-generic over k and r.e. in b; [e, b] codes an effective standard model of arithmetic; and there are x, y < g coding each Σ_{3}^{E} set in M. As g is 1-generic over k and k < e < g, g′′ = x and Σ_{3}^{E} = Σ_{3}^{G} = Σ_{3}^{K}. Thus x =H(g) as required.

This proves the invariance of the double jump in D(≤ 0′). By using the language of arithmetic in the coded models, the invariance result can be converted into definitions of the jump classes Low_{n} and High_{n} for n ≥ 2 (rather than n ≥ 3). Now, an argument similar to that for our Theorem 2.21 above shows that High_{1} is definable in D (≤ 0′) by the same formula used in R. The only change is that the final application of the RJIT is replaced by the jump interpolation theorem given in Theorem 1.6(b) and due to Jockusch and Posner [13]. We have thus proved the following results:

Theorem 3.11. i) Any relation on D(≤ 0′) invariant under the double jump is invariant. ii) The jump classes Low_{n+1} and High_{n} for n ≥ 1 are definable in D(≤ 0′). iii) For each c REA in 0′′, the set of degrees x ≤ 0′′ with x′′ = c is definable in D(≤ 0′).

The general definability results for arithmetical relations invariant under the double jump in D(≤ 0′) can then be derived (as mentioned in [29]) using comparison maps between models via the methods of Slaman and Woodin [34] as explicated in [25]. One can then derive results on relativizations to structures [z, z′] as we did above for R^{z}.

Assuming the definability of the jump (as now proved by Cooper [5]) Nerode and Shore [19] showed that every degree above 0^{(3)} is fixed under every automorphism of D. Slaman and Woodin improved this result by replacing 0^{(3)} with 0′′. As the last application of our results we note that the relativization of the characterization of a′′ from D(≤ a) supplies another proof of this result:

Theorem 3.12. (Slaman and Woodin): Every automorphism of D is fixed on every x ≥ 0′′.

Proof. If x ≥ 0′′ then there is (by the Friedberg jump theorem) a degree z such that z′′ = x. As the jump is definable in D by [5], this relation is definable from x as is z′ from z. Our arguments now show that x is determined by the sets coded as above in such structures [z, z′] and so is fixed by all automorphisms of D. □

In the above proof our constructions show that we can actually definably get a representative of the degree x in the coded model. Moreover, in D we can definably map one such model to any other. Thus we can definably choose a representative of any degree up to double jump and for example prove the following:

Theorem 3.13. Any relation on D definable in second order arithmetic and invariant under the double jump is definable in D.

Of course, as we see from the codings described in §2, there is no need for the degrees coding the model of arithmetic to determine an entire interval of degrees and so require full initial segment type arguments. Thus simpler constructions (if done from scratch) would suffice to construct such codings that would be sufficient to prove these results for D(≤ 0′) and D.

4. Slaman-Woodin Sets

We begin the discussion of our constructions with a description of Slaman and Woodin’s basic scheme for constructing a countable set of incomparable degrees g_{i} which are definable in R from finitely many parameters p, q, r as the minimal degrees x below r such that q ≤_{T} x ∨ p.

Theorem 4.1. (Slaman and Woodin): There are r.e. sets P, Q, R and G_{i} (for i ∈ ω) with R = ⊕G_{i} 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.

We first give a preliminary description of the basic strategies for insuring each of the requirements (1)-(3) above.

4.1. The individual requirements

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

This requirement is met by building a functional Γ_{i} such that Γ_{i}(G_{i} ⊕P) = Q. It introduces the set G_{i} in the construction and so no requirement preceding it can involve G_{i}. A crucial goal of the construction will be to arrange that a number x is put into Q to satisfy some requirement of lower priority than T_{i} only when we can safely put the associated marker γ_{i}(x) (which is the use of Γ_{i}(G_{i} ⊕P)) into P. Of course, we can move this marker if we so desire when G_{i} (or P) has changed on the use of the functional at x. The typical situation will be that, before x can go into Q, x or some smaller number must enter G_{i}. At that point, we will redefine γ_{i}(x) to be large enough so that, when x goes into Q, we can put γ_{i}(x) into P without injuring the P preservation associated with the requirement putting x into Q. We must also somewhere in the construction maintain this ability to put x into Q by keeping γ_{i}(x) above this P restraint or cancel the possibility that x might enter Q. (Requirements of type 4 below will play a role here.)

2. D_{i,j,e}: Ψ_{e}(G_{i}) ≠ G_{j}. (⟨Ψ_{e}| e ∈ ω⟩ is a listing of all partial recursive functionals.)

This requirement is met by a Friedberg-Muchnik type of argument. We begin by choosing a suitable follower y which is larger than any number used so far in the construction. The conditions on suitability of followers are intimately connected with the strategy for minimality of the G_{i} (3) and cannot be precisely defined until we describe the strategy for those requirements. Suffice it to say that maintaining the suitability of followers will consist of imposing P restraint and will be D_{i,j,e}’s major task in the construction. We wait for a stage s at which the (still suitable) follower is realized, Ψ_{e}(G_{i}; y) = 0 [s]. We then put y into G_{j} and preserve G_{i} on the appropriate use ψ_{e}(y) by initializing all lower priority requirements.

3. M_{i}: If Θ_{i}(R) = W_{i} and Φ_{i}(W_{i} ⊕ P) = Q, then G_{j} ≤_{T} W_{i} for some j ∈ ω. (Here ⟨W_{i}, Θ_{i}, Φ_{i}| i ∈ ω⟩ is a listing of all triples consisting of an r.e. set W and two partial recursive functionals Θ and Φ.)

These requirements, which insure minimality, are by far the most complicated ones. Suppose, for example, that the sets G_{0}, … G_{n} have been introduced by the requirements T_{j} for j ≤ n of higher priority than M_{i}. Our first task is to see if the hypotheses of M_{i} seem satisfied. Thus we first see if we have a new i-expansionary stage: We define a length of agreement function l(i, s) =

μz{¬[Φ_{i}(W_{i} ⊕ P; z) ↓= Q(z) [s] ∧ (∀w ≤ ϕ_{i}(z))(Θ_{i}(R; w) ↓= W_{i}(w) [s] )] }.

We say that a stage s of our construction is i-expansionary if l(i, s) > l(i, t) for every stage t < s.

If there are infinitely many expansionary stages for the functionals in the hypothesis of M_{i}, we will, for each j ≤ n, build functionals Δ_{i,j}. Moreover, we will guarantee that, for some j ≤ n and some m, Δ_{i,j}(W_{i}; x) = G_{j}(x) for every x > m. (We could build distinct functionals Δ_{i,j,m} so that one of them would work for all x but it is technically more convenient to build just one functional that works almost everywhere. Of course this suffices to get G_{j} ≤_{T} W_{i} as desired.) If, on the other hand, the last functional, Δ_{i,n}, is seen to fail, we will kill off the requirement M_{i} by putting some number x into Q while preserving the Φ_{i} use ϕ_{i}(x) to guarantee that Φ_{i}(W_{i} ⊕ P) ≠ Q. Thus there will be only finitely many i-expansionary stages. The preservation of this win on requirement M_{i} has two components. We preserve first P ¯ ϕ_{i}(x) and then W_{i} ¯ ϕ_{i}(x) by preserving R ¯ θ_{i}ϕ_{i}(x), the amount of R needed to compute W_{i} ¯ ϕ_{i}(x) via Θ_{i}, by initializing all lower priority requirements.

Our main goal in setting up the situation to produce this win on M_{i} is to insure that when we put x into Q, we can correct all the functionals Γ_{j}(x) of higher priority than M_{i} that are supposed to be computing Q from G_{k} ⊕ P for some k. We expect to be able to do this by putting the number γ_{k}(x) into P. The crucial point is then that we must insure that each γ_{k}(x) is greater than ϕ_{i}(x) as our diagonalization against Q depends on preserving P ¯ ϕ_{i}(x). The basic idea for getting γ_{k}(x) to be greater than ϕ_{i}(x) is that before x can go into Q it, or some smaller number, must go into each such G_{k}. When that happens we can increase γ_{k}(x) to maker it larger than ϕ_{i}(x). Some restraint will also be imposed in the usual way (as, for example, in the minimal pair argument) between expansionary stages to preserve P ¯ ϕ(x) until the next expansionary stage even after the associated number has gone into G_{k}. It is dropped, and so may be violated (even by lower priority requirements), at expansionary stages. Other preservation will be indirectly imposed (by type 4 requirements) that will prevent this from happening infinitely often. In addition, we must know that no W_{i} change can later increase ϕ_{i}(x) without allowing us to restore the computations Δ_{i,j}(W_{i}; x) whose failure prompted us to consider putting x into Q. This condition translates into the requirement that δ_{i,j}(x) ≥ ϕ_{i}(x) as, in this case, any W_{i} change on ϕ_{i}(x) would allow us to redefine Δ_{i,j}(W_{i}; x) to once again equal G_{j}(x). Thus insuring such inequalities as δ_{i,j}(x) ≥ ϕ_{i}(x) will be an important, if only implicit, concern in the construction.

Although it is a considerable oversimplification, it may be instructive to first consider the case that n = 0. Here, there is only one set, G_{0}, that we can compute from W_{i} to satisfy the requirement and only one functional Δ_{i} = Δ_{i,0} is constructed.

Now, our concern is that some requirement S of lower priority may want to put x into G_{0} (and so destroy the correctness of Δ_{i}). If such a requirement appoints x as a follower, it will be its responsibility to preserve the suitability of x (until x enters G_{0}) by imposing restraint on P ¯ ϕ_{i}(x). As far as the requirement M_{i} is concerned, the suitability of x will be equivalent to being able to insure that, if and when needed, we can make γ_{0}(x) > ϕ_{i}(x). An additional point to notice is that even though S is preserving P ¯ ϕ_{i}(x), it is not preserving R. Hence W_{i} may change on ϕ_{i}(x) before we put x into G_{0}. As mentioned above, when this happens we redefine the axiom for Δ to make δ_{i}(x) ≥ ϕ_{i}(x). In addition, S now imposes restraint on P up to the new Φ_{i}(x) use. (A more precise description of this restraint will be given when we formally define the action of the Friedberg-Muchnik type diagonalization requirements. We will also explain below how we add new requirements (type 4) to the construction to prevent ϕ_{i}(x), and so the P restraint imposed by S, from becoming unbounded.)

On the other hand, if s is i-expansionary and there is a point at which Δ_{i} has failed (to correctly compute G_{0}) let x be the least number such that Δ_{i}(W_{i}; x) ↓≠ G_{0}(x) [s]. Consider now which requirement S put x into G_{0} at a stage t < s. On general principles, S must have lower priority than M_{i} or we would simply cancel M_{i} and start it over. In accordance with the above provisions, S then imposed restraint on P ¯ ϕ_{i}(x) [v] as soon as l(i, v) ≥ x.

Note that, by our definition of Δ_{i}, δ_{i}(x)[v] = v > ϕ_{i}(x)[v]. As long as x is not cancelled, this restraint will not be violated. Thus the only way ϕ_{i}(x) can change between v and t is for W_{i}¯ ϕ_{i}(x) to change. When this happens we redefine Δ_{i} at i-expansionary stages so as to keep δ_{i}(x) ≥ ϕ_{i}(x).

Now, before we return to M_{i} at an i-expansionary stage there is a stage r, t < r ≤ s, at which we deal with the requirement T_{0}. At stage r, we must redefine Γ_{0}(G_{0} ⊕ P; x). Of course, x has not yet gone into Q and so we will set Γ_{0}(G_{0} ⊕ P; x) = 0; but, we will define the functional by an axiom of length γ_{0}(x) = r > ϕ_{i}(x) [t]. When we now finally return to M_{i} at the first i-expansionary stage s > t and see that Δ_{i}(W_{i}; x) ↓≠ G_{0}(x) = 1 [s], we are ready to kill M_{i}. Note that W_{i} ¯ ϕ_{i}(x)[t] has not changed or we would not have Δ_{i}(W_{i}; x) ↓ and a failure at x. (The point here is again that δ_{i}(x)[t] ≥ ϕ_{i}(x)[t] by our maintaining this inequality whenever W_{i} ¯ ϕ_{i}(x) changes. A change in P would cause us to cancel x.) We put x into Q, r into P and preserve R¯ θ_{i}ϕ_{i}(x)[s] and P¯ ϕ_{i}(x)[s] by initializing lower priority requirements. As long as this restraint is not violated l(i, v) < x and there are no more i-expansionary stages. (As R ¯ θ_{i}ϕ_{i}(x) does not change, W_{i}¯ ϕ_{i}(x) cannot change without forever preventing l(i, v) from getting above x because of the clause requiring that Θ_{i}(R; w) ↓= W_{i}(w) for every w ≤ ϕ_{i}(x)[s]. Moreover, no numbers enter P ¯ ϕ_{i}(x)[s] by our initialization procedure and so if W_{i} ¯ ϕ_{i}(x)[s] also does not change, Φ_{i}(W_{i} ⊕ P; x) remains constant at its value at t which was necessarily 0 as x was not in Q at that time. Thus our preservation guarantees that either Φ_{i}(W_{i} ⊕ P; x) ≠ Q(x) or Θ_{i}(R; w) ≠ W_{i}(w) for some w ≤ ϕ_{i}(x), i.e. there are no more i-expansionary stages.)

Finally, we can correctly redefine Γ_{0}(x) at the next stage because we put r < γ_{0}(x) into P. Thus if Δ_{i} ever fails to correctly compute G_{0} from W_{i}, we can kill off the requirement M_{i} and still correct the functionals of higher priority. Of course, we can only follow this plan of action if no requirement of higher priority than M_{i} restrains r from entering P.

To describe the action for a requirement M_{i} in general, suppose that the sets G_{0}, … G_{n} (n > 0) are the ones that have been introduced by requirements T_{j} for j ≤ n of higher priority than M_{i}. As mentioned above we will be constructing various functionals Δ_{i,j} and attempting to see that, for some j, Δ_{i,j}(W_{i}) =^{∗} G_{j}. We say that a functional Δ = Δ_{i,j} fails at a number x at stage s if Δ_{i,j}(W_{i}; x) ↓≠ G_{j}(x) [s]. This failure remains active at stages t > s as long as there is no change in W_{i} ¯ δ_{i,j}(x)[s].

At stages s which are not i-expansionary, we take no action for M_{i} but we do maintain restraint on P ¯ u where u is the last i-expansionary stage. At iexpansionary stages we drop M_{i}’s P restraint and proceed for j = 0 by trying to build a functional Δ_{i,0} such that Δ_{i,0}(W_{i}) =^{∗} G_{0}. Suppose s is an i-expansionary stage. We begin the construction with a chit for each number y. We will use these chits to keep track of the failures of functionals Δ_{i,j}. We first find the least x < l(i, s) such that Δ_{i,0}(W_{i}; x) ↑ and the least y < l(i, s) such that the chit for y has not been assigned to any Δ_{i,0} computation and has not been cancelled. Assign the chit for y to Δ_{i,0}(W_{i}; x) and set Δ_{i,0}(W_{i}; x) = G_{0}(x)[s] with use ϕ_{i}(y)[s]. This chit for y can be assigned to various computations Δ_{i,j}(W_{i}; z) subject to the provisos that at any given stage it is assigned to at most one such computation for any single j and it cannot be assigned to one for j + 1 until the one for j to which it is assigned fails. The chit will be cancelled if the failure of Δ_{i,0} at x becomes inactive. Moreover, we will insure that the use δ_{i,j}(z)[t] of any convergent computation to which it is assigned at t is ϕ_{i}(y)[t] for any t ≥ s until y enters the set for which it is targeted. Thus if the chit becomes inactive, any computation associated with a chit for x becomes undefined (and so can be corrected at the next stage if necessary).

If n > 1, we proceed for j = 1 much as we did above for j = 0 except that we must restrict our actions by the availability of chits. If there is no active uncancelled chit which is assigned to some failure of Δ_{i,0} but not to any Δ_{i,1} computation, we terminate this substage of stage s. If there is such a chit, we assign the least such chit to the computation Δ_{i,1}(W_{i}; x) where x is least such that Δ_{i,1}(W_{i}; x) ↑. If there is now a failure of Δ_{i,1} whose chit (for some number y) has not been assigned to any Δ_{i,2} computation, we continue on with j = 2. Note that if we assign the chit for y to Δ_{i,1}(W_{i}; x), then y > x. Thus, for example, x < γ_{1}(y) and so when we put x into G_{1} we can change γ_{1}(y) as well as γ_{1}(x) to be larger than ϕ_{i}(y).

At any point we may cancel the chit for a number y because of certain changes in P that would interfere with our correcting higher priority Γ_{k} should we put y into Q. If some x enters G_{j} at a stage t when the chit for y is assigned to a computation Δ_{i,j}(W_{i}; x) and at a later i-expansionary stage s > t, before y has gone into Q, ϕ_{i}(y)[s] > t then we cancel the chit for y (and so it can never be assigned to any other computation and y can never enter Q).

If we reach a point where there are no unassigned active chits to pass on to the next level of functionals, we terminate this substage of stage s. Otherwise, we reach the functional Δ_{i,n}. If there is a failure of this functional at x and the (uncancelled, active) chit for y is assigned to Δ_{i,n}(W_{i}; x) and our action would not violate any higher priority P restraint, then we act to kill M_{i}. We put y into Q, γ_{j}(y) into P for each j ≤ n and preserve R¯ θ_{i}ϕ_{i}(y) and P ¯ ϕ_{i}(y) by initialization. The point to verify is that γ_{j}(y) > ϕ_{i}(y) for each j ≤ n.

4. K_{e,x}: If there are infinitely many s such that Ξ_{e}(R ⊕ P; x) ↓ [s], then Ξ_{e}(R ⊕ P; x) ↓.

Here {Ξ_{e}} lists all partial recursive functionals and includes various ones appearing in the construction with the approximations given in the construction. In particular, it includes Δ_{i,j}(W_{i}; x) and the function of i, j, n which converges when there are n failures of the functional Δ_{i,j} at an i- expansionary stage. When we consider such functionals as included in the Ξ_{e} we intend their uses (from R) to include the Θ_{i} uses needed to compute the relevant Φ_{i} uses on W_{i}. These requirements are not explicit in the statement of the theorem but they are used, for example, to prevent the uses ϕ_{i}(y) of the chit assigned to the computation (and so the associated P restraint) from going to infinity. They also play a role in maintaining conditions of the form γ_{k}(x) > ϕ_{i}(y) discussed above and making the functionals Γ_{k} total. The requirement K_{e,x} simply attempts to preserve P ¯ ξ_{e}(y) and R¯ ξ_{e}(y) by initialization.

We now turn to the formal construction of our sets L, P, Q, R and G_{i}.

4.2. Construction

We begin by listing all the requirements T_{i}, D_{i,j,e}, M_{i}, K_{e,x} in a priority list of order type ω such that T_{i} and T_{j} appear on the list before any D_{i,j,e}. Each stage s of our construction will have at most s many substages n at which we may deal with requirement n. Each requirement may put numbers into some sets, axioms into a functional and impose restraint on various sets in the usual fashion. Whenever a requirement puts numbers into a set we initialize all requirements of lower priority. Initialization of a requirement at stage s means that all followers, chits and all restraint associated with the initialized requirement are cancelled and no further attempts are made at maintaining the correctness at numbers less than s of any functionals it is constructing. (As we only care about the functional being correct almost everywhere, this will not cause problems as long as the requirement is initialized only finitely often.) As new followers are always chosen larger than any number previously used in the construction, initialization also acts to preserve various computations. At other times we may cancel chits because the situation that made them usable has been destroyed. We now describe our actions at substage n of stage s of the construction according to the type of the nth requirement on our list. We let r be the last stage at which the requirement being considered at substage n was injured (r = 0 if there is no such stage). Material enclosed in double brackets [[]] is motivational only and not part of the formal construction. When we choose a “large” number at a stage s we mean a number larger than any used in the construction before s. We use the style of i-expansionary stage restraint on P as in the minimal pair construction in [35, IX.1].

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

Find the least x > r such that Γ_{i}(G_{i} ⊕ P; x) ↑ [s] and set Γ_{i}(G_{i} ⊕ P; x) = Q(x)[s] with large use γ_{i}(x). [[That Γ_{i} will be defined almost everywhere will follow from the type 4 requirements below. That it will be correct almost everywhere is tied to the action of the type 3 requirements which put numbers into Q and will require proof below.]] We now continue on to the next substage of stage s.

2. D_{i,j,e} : Ψ_{e}(G_{i}) ≠ G_{j}.

If this is the first stage at which we deal with this requirement since r, we choose a new large follower x for D_{i,j,e} from the column ω^{⟨0,i,j,e⟩} associated with D_{i,j,e}. At every stage t ≥ s until x is cancelled or enters G_{j}, D_{i,j,e} imposes restraint r(D, i, j, e, t) on P where

r(D, i, j, e, t) = max{δ_{k,j}(W_{k}; x)[t]| M_{k} has higher priority than D_{i,j,e}}.

[[Our definition of Δ_{i,j} will make this equivalent to max{ϕ_{k}(z)[t]| M_{k} has higher priority than D_{i,j,e} and there is a computation of Δ_{k,j}(W_{k}; x) ↓ [t] which is associated with a chit for z.}]] This restraint is dropped when x is cancelled by some higher priority requirement or enters G_{j}. [[This restraint can be violated only when we act for a type 3 requirement of higher priority in which case we would initialize D_{i,j,e} and all lower priority requirements.]]

If D_{i,j,e} has an uncancelled follower x and Ψ_{e}(G_{i}; x) ↓= 0, we say the follower is realized. If the realized follower is not yet in G_{j}, we put it into G_{j}, initialize all lower priority requirements and terminate stage s. [[This has the effect of preserving G_{i} ¯ ψ_{e}(x) with priority D_{i,j,e}.]] Otherwise, we continue on to the next substage of stage s.

3. M_{i}: If Θ_{i}(R) = W_{i} and Φ_{i}(W_{i} ⊕ P) = Q, then G_{j} ≤_{T} W_{i} for some j such that T_{j} has higher priority than M_{i}.

We first define a length of agreement function and i-expansionary stages as above:

l(i, u) = μz{¬[Φ_{i}(W_{i} ⊕ P; z) ↓= Q(z) [u]
∧ (∀w ≤ ϕ_{i}(z))(Θ_{i}(R; w) ↓= W_{i}(w) [u] )] }.

We then define the notion of an e-expansionary stage and the restraint r(M, e, u) imposed on P by M_{e} by induction on e ≤ i as in [37, IX.1]. If u = 0 or l(0, u) is larger than l(0, t) for every t < u, the stage u is 0-expansionary and r(M, 0, u) = 0. Otherwise, u is not 0-expansionary and r(M, 0, u) is the largest number used in the construction up through the last 0-expansionary stage. The stage u is (e + 1)- expansionary if l(e + 1, u) > l(e + 1, t) for every t < u for which r(M, e, t) = r(M, e, u). We let r(M, e + 1, u) be the maximum of r(M, e, u), any number used at a stage t < u at which r(M, e, t) < r(M, e, u) and, if u is not (e + 1)- expansionary, any number used at any (e + 1)-expansionary stage t < u for which r(M, e, t) = r(M, e, u). Now we can describe our action for M_{i} at stage s.

If s is not i-expansionary or M_{i} has put a number into Q since r, we go on to the next substage of stage s. Otherwise, suppose that T_{0}, …, T_{n} are the requirements of type 1 of higher priority than M_{i} (n is really n_{i} but we drop the subscript for this description). We are constructing functionals Δ_{i,j} with the expectation that, for some j ≤ n, Δ_{i,j}(W_{i}) =^{∗} G_{j}. We say that a functional Δ_{i,j} fails at a number x at stage s if Δ_{i,j}(W_{i}; x) ↓≠ G_{j}(x) [s]. This failure remains active at stages t > s as long as there is no change in W_{i} ¯ δ_{i,j}(x)[s]. At the start of the construction, there is a chit (for M_{i}) for each number y. We will assign these chits to various computations of the functionals Δ_{i,j} and use them to keep track of the failures of these functionals.

We begin with j = 0 by finding the least x > r such that Δ_{i,0}(W_{i}; x) ↑ [[necessarily x < l(i, s)]]. Let y be the least number < l(i, s) such that the chit for y is not assigned to any computation of Δ_{i,0} and has not been cancelled. (If there is no such y we go on to the next substage of stage s.) We assign the chit for y to Δ_{i,0}(W_{i}; x) and set Δ_{i,0}(W_{i}; x) = G_{0}(x)[s] with use ϕ_{i}(y)[s]. This chit for y can be assigned to various computations Δ_{i,j}(W_{i}; z), 0 < j ≤ n, subject to the provisos that at any given stage it is assigned to at most one such computation for any single j and it cannot be assigned to one for j + 1 until the one for j to which it is assigned fails. The chit will be cancelled if the failure of Δ_{i,0} at x becomes inactive or M_{i} is initialized. It may also be cancelled at stages where certain changes occur in P on computations associate with the chit. [[Moreover, we will insure that, unless cancelled, the use δ_{i,j}(z)[t] of any convergent computation to which the chit is assigned at t is ϕ_{i}(y)[t] for any t ≥ s. Thus if the chit for y becomes inactive any computation at a number larger than the last initialization of M_{i} to which the chit for y is assigned becomes undefined, and so can be corrected at the next stage.]]

If n > 1, we proceed for j > 0 much as we did above for j = 0 except that we must restrict our actions by the availability of chits. If every uncancelled chit which is assigned to some failed computation of Δ_{i,j−1} has been assigned to some Δ_{i,j} computation, we terminate this substage of stage s. If there is such an unassigned chit, we assign the least such chit to the computation Δ_{i,j}(W_{i}; x) where x is least such that Δ_{i,j}(W_{i}; x) ↑. If there is now a failure of Δ_{i,j} whose chit (for some number y) has not been assigned to any Δ_{i,j+1} computation, we continue on with j + 1. [[Note that if we assign the chit for y to Δ_{i,j}(W_{i}; x), then y > x. Thus, for example x < γ_{1}(y) and so when we put x into G_{1} we can change γ_{1}(y) as well as γ_{1}(x) to be larger than ϕ_{i}(y).]]

If we assign the chit for y to a computation Δ_{i,j}(W_{i}; x) at s, x enters G_{j} at t ≥ s and we return to M_{i} at an i-expansionary stage u ≥ t such that ϕ_{i}(y)[u] > t, then we cancel the chit for y [[and so y will never enter Q]].

If we reach a point where there are no appropriate active chits to pass on to the next level of functionals, we terminate this substage of stage s. Otherwise, we reach the functional Δ_{i,n}. If there is a failure of this functional at x and the uncancelled chit for y is assigned to Δ_{i,n}(W_{i}; x) and y is larger than any restraint of higher priority on P (i.e. y > r(D, k, l, m, s), r(M, k, s) for every D_{k,l,m} and M_{k} of higher priority than M_{i}), then we act to kill M_{i}: We put y into Q, γ_{j}(y) into P for each j ≤ n and preserve R ¯ θ_{i}ϕ_{i}(y) and P ¯ ϕ_{i}(y) by initializing all requirements of lower priority than M_{i} and terminate stage s. [[The point to verify will be that γ_{j}(y) ≥ ϕ_{i}(y) for each j ≤ n.]]

4. K_{e,x}: If there are infinitely many s such that Ξ_{e}(R ⊕ P; x) ↓ [s], then Ξ_{e}(R ⊕ P; x) ↓.

Here {Ξ_{e}} lists all partial recursive functionals and includes various ones appearing in the construction with the approximations given in the construction. In particular, it includes the ones Γ_{i}(G_{i} ⊕ P; x), Δ_{i,j}(W_{i}; x) and the function of i, j, n which converges when there are n failures of the functional Δ_{i,j} at an iexpansionary stage associated with uncancelled chits. When we consider such functionals as included in the Ξ_{e} we intend their uses (from R) to include the Θ_{i} uses needed to compute the relevant Φ_{i} uses on W_{i} as well as the information directly used about P, R and any G_{k} viewed as a component of R.

If Ξ_{e}(R ⊕ P; x) ↓ for the first time since K_{e,x} was last initialized, we initialize all requirements of lower priority. [[This has the effect of imposing restraint on P ¯ ξ_{e}(x)[s] and on R ¯ ξ_{e}(x)[s] and hence, for example, on W_{i} ¯ δ_{i,j}(x)[s] for the appropriate e.]] In any case, continue on to the next substage of stage s.

At the end of substage s, we terminate stage s (if it has not been terminated before). When stage s is terminated, we go on to stage s + 1.

4.3. Verifications

First, note that (other than through initialization) the only restraint imposed in the construction is on P. Moreover, by definition of the e-expansionary stages and the restraint functions r(M, e, u), the restraint r(M, i, s) imposed on P by requirements M_{j} of priority greater than or equal to that of M_{i} have a finite lim inf which is realized on the i-expansionary stages if there are infinitely many such stages and, if not, on almost all the stages at which r(M, i − 1, s) realizes its lim inf. We are proving by induction that each requirement succeeds and that those of type 2 impose at most finite restraint. (Of course, requirements of type 1 never impose any restraint.) It is immediate from the definition of their actions that if a requirement of type 2,3 or 4 is never initialized after stage r, it acts at most once after r to put numbers into sets and to initialize lower priority requirements. As the other requirements never initialize anything, it is obvious by induction that each requirement has a stage after which it is never initialized. Let us consider the fate of any requirement which is last initialized at stage r.

4. If Ξ_{e}(R ⊕ P; x) never converges after stage r, we never act for K_{e,x} and it is satisfied. If Ξ_{e}(R ⊕ P; x) converges for the first time at s > r, it remains convergent at every later stage. The point is that K_{e,x} initializes all requirements of lower priority and so none can put any elements below the use into R or P. No requirement of higher priority can put a number into R or P as that would initialize K_{e,x} contrary to our choice of r. Thus the K_{e,x} succeed.

In particular, lim δ_{i,j}(x) exists and is finite (possibly 0 if Δ_{i,j}(W_{i}; x) ↑) for every i, j, x. Thus the restraint imposed by any particular follower x of a requirement D_{m,n,e} is bounded by lim max{δ_{k,l}(x)[t]| M_{k} has higher priority than D_{m,n,e}}. (Note that the set of relevant δ_{k,l} is finite as l ≤ n_{k} and each M_{k} must have higher priority than D_{m,n,e}.) As only one follower is ever appointed for such a requirement after it is last initialized, the restraints of this type are bounded for each such requirement.

2. D_{i,j,e}: At stage r + 1, D_{i,j,e} appoints some large follower x. If the follower x is never realized, the requirement is satisfied. If it is realized at a stage t, we put x into G_{j} and initialize all lower priority requirements. Now, no higher priority requirement can put a number below ψ_{e}(x)[t] into G_{i} as this would initialize D_{i,j,e} contrary to our assumption. No lower priority argument can put any number below ψ_{e}(x)[t] into G_{i} after stage t as all such numbers are appointed as followers after stage t and so are larger than ψ_{e}(x)[t]. (The only requirements which can put numbers into G_{i} are of type 2 and these always choose new followers larger than any number previously used in the construction.) Thus D_{i,j,e} is satisfied. The argument in the proceeding paragraph shows that the P restraint imposed by D_{i,j,e} now goes to a limit.

1. T_{i}: Consider each x > r in turn. It is clear from the construction that we build a functional Γ_{i} such that Γ_{i}(G_{i} ⊕ P; x) ↓ [t] = Q(x)[t] for infinitely many t. The success of the requirements K_{e,x} now guarantees that Γ_{i} is defined for all x > r. Now, only requirements of type 3 put numbers into Q and when they put some y into Q they put γ_{k}(y) into P for every T_{k} of higher priority. Thus at any later stage we can correctly redefine Γ_{k}(G_{k} ⊕ P; y). At all other stages this functional is obviously correct when defined and so G_{i} ⊕ P ≥_{T} Q as required.

3. M_{i}: If the hypotheses of M_{i} (Θ_{i}(R) = W_{i} and Φ_{i}(W_{i} ⊕ P) = Q) are satisfied, there are infinitely many i-expansionary stages at which the P restraint of higher priority is constant. If the hypotheses are not satisfied, the success of the requirements K_{e,x} guarantee that lim l(i, s) < ∞ and so we eventually stop all action for M_{i} and in particular, the restraint it imposes is eventually constant.

We begin by supposing that the hypotheses are satisfied and prove a series of lemmas.

Lemma 4.2. Δ_{i,0}(W_{i}; x) is defined for every x > r.

Proof. If not, let x be the least counterexample and s a stage by which Δ_{i,0} has settled down for every z, r < z < x. It is clear from the construction and our hypotheses that Δ_{i,0}(W_{i}; x)[t] ↓ for infinitely many t > s. As this corresponds to some Ξ_{e}(R ⊕ P; x)[t] ↓, the success of the requirements of type 4 guarantees that Δ_{i,0}(W_{i}; x) ↓. □

Lemma 4.3. Suppose Δ_{i,j}(W_{i}; x) is defined for almost every x. If there are infinitely many x such that Δ_{i,j}(W_{i}; x) ≠ G_{j}(x), then there are infinitely many x such that the computation of the failure of Δ_{i,j} at x is associated with a chit which is never cancelled and so, if j < n_{i}, there are infinitely many chits which are never cancelled and are available for assignment to Δ_{i,j+1}.

Proof. We proceed by induction on n and so assume there are n − 1 many failures of Δ_{i,j} with computations associated with chits which are never cancelled. Let x be a larger failure point for Δ_{i,j}. Consider the stage t at which x enters G_{j}. Suppose Δ_{i,j}(W_{i}; x) was last defined at (a necessarily i-expansionary) s < t with δ_{i,j}(x)[s] = ϕ_{i}(y)[s] where the chit for y was assigned to this computation of Δ_{i,j}(W_{i}; x). We can later get our failure at x only if x is already a follower of some D_{k,j,e} of lower priority than M_{i}. Thus the restraint associated with this requirement after stage s is at least δ_{i,j}(x)[s] = ϕ_{i}(y)[s]. If P changes below this restraint before x enters G_{j}, x would be cancelled (as P can change only if a requirement of higher priority puts a number in and so initializes D_{i,j,e}) and so would never enter G_{j} and never produce a failure of Δ_{i,j}. Thus when x enters G_{j} at t ≥ s, P ¯ ϕ_{i}(y)[s] has not changed since the last stage at which Δ_{i,j}(W_{i}; x) was defined. Now no number enters P at t because only one requirement can put numbers into R ⊕ P at any stage. Let u be the first i-expansionary stage after t. No number below ϕ_{i}(y)[s] can enter P at any v between t and u by the definition of the restraint r(M, i, v) as M_{i} can no longer be initialized. Thus when we return to M_{i} at stage u, we have a failure of Δ_{i,j} at x which has not been cancelled and so seem to have W_{i} ⊕ P correct on the use ϕ_{i}(y)[u]. Our assumption guarantees that this happens for infinitely many x. Consider now the functional Ξ_{e}(R⊕P; k) which gets defined at s if there are k many failed computations of Δ_{i,j} which are associated with chits whose computations are R ⊕ P correct at s. Once again, the success of requirements of type 4 and our assumptions guarantee that this functional is defined at n. As (after M_{i} is never initialized) a chit for y such that R ¯ θ_{i}ϕ_{i}(y) and P ¯ ϕ_{i}(y) are correct is never cancelled, we have the existence of the desired nth instance of a failed computations of Δ_{i,j} associated with a chit which is never cancelled. □

Lemma 4.4. If j < n_{i} and there are infinitely many chits which are never cancelled and available for assignment to Δ_{i,j+1}, then Δ_{i,j+1} is defined for every x > r.

Proof. The argument is like the one above for Δ_{i,0}. By construction, we must infinitely often define Δ_{i,j+1} at some x as there are new chits available infinitely often. Thus, for each x at which we can try to define Δ_{i,j+1} infinitely often (i.e. each x > r), the functional is actually defined by the success of requirements of type 4. □

Lemma 4.5. If Δ_{i,j}(W_{i}) ≠^{∗} G_{j} for every j ≤ n_{i} then M_{i} eventually puts a number into Q.

Proof. Arguing by induction and using the above Lemmas, we see that Δ_{i,n_{i}} is defined for every x > r. If there were infinitely many failures of Δ_{i,n_{i}}, there would be infinitely many whose associated chit is never cancelled. So, in particular, there would be an x associated with such a chit y which is larger than the lim inf of the restraint of higher priority than M_{i} imposed on P. It is clear by construction that we would then eventually put one such y into Q. □

Finally, we conclude the verification of the success of M_{i} with the following lemma.

Lemma 4.6. If M_{i} ever puts a number y into Q after stage r, then lim l(i, s) < ∞ and so M_{i} is satisfied. (Of course, in this case there are only finitely many iexpansionary stages and the restraint imposed by M_{i} is constant after the last one.)

Proof. Suppose it does so at stage s. We first claim that no number used in the computations associated with y at s can ever be put into R or P. As no higher priority requirement ever puts a number into R⊕P by our choice of r and no lower priority one puts one in which is used in the computations at s by initialization, it suffices to prove that each γ_{k}(y)[s] put into P at s is larger than these uses from P. In order for us to put y into Q at s, we must have a chit for y which is uncancelled and associated with failed computations Δ_{i,j}(W_{i}; x_{j}) = 0 ≠ G_{j}(x) for each j ≤ n_{i}. Consider the stage s_{j} < s at which x_{j} was put into G_{j} by some requirement of type 2 of lower priority than M_{i} (as otherwise s_{j} < r and so the chit for y would have been cancelled at r). Suppose Δ_{i,j}(W_{i}; x_{j}) was last defined before s_{j} at the i-expansionary stage t_{j} with a chit for y and use ϕ_{i}(y)[t_{j}]. At some stage u_{j} > s_{j} we redefine Γ_{j}(W_{j} ⊕ P; y) with a large use and so one larger than ϕ_{i}(y)[t_{j}], t_{j}. If there were any later i-expansionary stage (including s) at which ϕ_{i}(y) increased above this Γ use, we would cancel the chit for y by construction and so it could not later go into Q as assumed. Of course, as time goes by γ_{j}(y) is nondecreasing. Thus when we put y into Q, γ_{j}(y) > ϕ_{i}(y) as required. □

This completes the proof that each requirement succeeds and so we have constructed the required sets. □

4.4. Codings

We now describe the additional requirements needed to code enough relations on the definable set of degrees ⟨g_{i}⟩ constructed above to get a definition of arithmetic on the defined set of degrees and so the undecidability of R. Although other codings are possible (such as graphs), we follow Slaman and Woodin’s original plan and code an arbitrary recursive partial ordering P = ⟨ω, ⪯⟩ on the g_{i} by constructing an additional set L and adding requirements that guarantee that G_{j} ≤_{T} G_{i} ⊕ L ⇔ j ⪯ i. For the “only if” direction, we adjust the construction so that any number x put into G_{j} is also simultaneously put into G_{i} or L. In particular, when a requirement D_{i,j,e} puts a number x into G_{j} it also puts x into L. For the “if” direction, we add in requirements of type 5.

5. N_{i,j,e}: If i ffl j then Ψ_{e}(G_{i} ⊕ L) ≠ G_{j}.

This requirement is met by a Friedberg-Muchnik type strategy like that used for requirements D_{i,j,e}. The only additional features are the ones necessitated by the coding for the positive ordering facts as described above. When a new large follower x is appointed, N_{i,j,e} imposes restraint r(N, i, j, e, t) on P that takes into account the fact that a witness x targeted for G_{j} will also have to be put into G_{l} for l ⪰ j:

r(N, i, j, e, t) = max{δ_{k,l}(W_{k}; x)[t]| M_{k} has higher priority than N_{i,j,e} and l ⪰ j}.

[[Our definition of Δ_{i,j} will make this equivalent to max{ϕ_{k}(z)[t]| M_{k} has higher priority than N_{i,j,e}, l ⪰ j and there is a computation of Δ_{k,l}(W_{k}; x) ↓ [t] which is associated with a chit for z.}]] This restraint is dropped when x is cancelled by some higher priority requirement or enters G_{j}. If N_{i,j,e} has an uncancelled follower x and Ψ_{e}(G_{i}; x) ↓= 0, we say the follower is realized. If the realized follower is not yet in G_{j}, we put it into G_{l} for every l ⪰ j, initialize all lower priority requirements and terminate stage s. The argument that these requirements are satisfied and impose only finite restraint on the rest of the construction is again exactly as for the D_{i,j,e}. (A more detailed version of the treatment of such requirements is presented in the construction for, and verification of, Theorem 5.1.)

4.5. Permitting

The next extensions of the basic construction with the coding apparatuses described above involve permitting. First, we can make the sets G_{i} and L constructed recursive in any given nonrecursive r.e. set B. The requirements D_{i,j,e} and N_{i,j,e} now wait for a realized follower x which is permitted by B. While all followers are realized but none has been permitted, they appoint new followers (initializing all lower priority requirements) and wait for them to be realized (again initializing all lower priority requirements). As B is nonrecursive, they either get a follower which is never realized or eventually put a realized follower into the appropriate sets. In any case they act only finitely often and are eventually satisfied. (Again a more detailed argument for a similar requirement is presented in Theorem 5.1.)

The situation for the M_{i} requirements and so for the sets P and Q is somewhat different. The restraint imposed on P by higher priority M_{j} only has finite lim inf. Thus coordinating action by M_{i} to put numbers into Q and so P with permitting by an arbitrary nonrecursive r.e. B requires B permission on expansionary stages. There is no reason to believe that this is possible. Indeed, in the analogous situation for minimal pairs it is known that there are nonrecursive r.e. B below which it is not possible to construct a minimal pair. Thus we view the problem of constructing Slaman-Woodin definable sets as in Theorem 4.1 below an arbitrary r.e. degree as an open question.

If, however, the given set recursively in which we wish to construct P and Q is a promptly simple set S rather than an arbitrary one B, the usual arguments (as in [3]) work. Thus if S is promptly simple, we can let M_{i} put a number y into Q (and so various γ_{j}(y) into P) only when y is permitted by S by using the function p witnessing the prompt simplicity of B. As we saw in the proof of Lemma 4.5, if we are reduced to the case that all the Δ_{i,j} fail then there are infinitely many y’s which remain permanently eligible to enter Q once S permits. We let M_{i} impose restraint to preserve the eligibility of such numbers as they become candidates for M_{i} to put into Q. We then enumerate these numbers into an auxiliary set when we next have an M_{i} expansionary stage. At each such stage s we enumerate S up to stage p(t) to see if it permits the number to go into Q. (Here t is the stage at which these numbers are enumerated in a standard enumeration of the auxiliary set given by the recursion theorem.) As usual, since S is promptly simple, one will eventually be allowed to enter Q. Of course, the numbers γ_{j}(y) going into P are larger than y and so both P and Q are permitted by S as required.

We can combine all of these modifications to construct a Slaman-Woodin set below any nonrecursive B along with the coding apparatus for a partial ordering. Moreover, if S is promptly simple, we can get the auxiliary sets P and Q needed to define the Slaman-Woodin set to be below S as well:

Theorem 4.7. Given a recursive partial ordering P = ⟨ω, ⪯⟩, a nonrecursive r.e. set B and a promptly simple one S, there are r.e. sets L, P, Q, R and G_{i} for k < n and i ∈ ω) with R = ⊕G_{i}, L ≤ B and P, Q ≤_{T} S with the following properties:

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. R ⊕ P is low. (Indeed we can just as easily make the join of all the sets constructed low.)

5. (N) : i ffl j ⇔ G_{i} ⊕ L Λ_{T} G_{j}. □

5. Cone Avoiding and Comparisons

The next modification we wish to consider is cone avoiding combined with permitting. More specifically, given various U_{i} Θ_{T} V_{j} with V_{j} low, we wish (under certain other assumptions) to make G_{i} ≤_{T} U_{i} and G_{i} Θ_{T} V_{j}. We first briefly describe the necessary additions to the basic construction for Theorem 4.1 to handle one triple G_{i}, U_{i}, V_{i}. To begin, we will only allow numbers x to enter G_{i} when permitted by U_{i} and so will follow the procedure described above for all requirements D_{k,i,e} putting numbers into G_{i} so that they are permitted by U_{i}. The new requirements of type 6 are as follows:

6. Z_{i,e}: Ψ_{e}(V_{j}) ≠ G_{i}.

The basic plan is as for the diagonalization requirements D of type 2 with permitting. We plan to appoint suitable followers x; preserve their suitability by imposing P restraint; and look for one which is realized (Ψ_{e}(V_{j}; x) = 0 at the current stage) that we are permitted to put into G_{i}. To guarantee that we eventually put in a follower such that Ψ_{e}(V_{j}; x) really is 0, our diagonalization procedure will include a two step guessing procedure exploiting the lowness of V_{j} and taking into account that we need U_{i} permission to put the desired V_{j}-correctly realized follower into G_{i}.

To hope to be able to handle a list of such triples G_{i}, U_{i}, V_{j} we have some obvious restrictions that we want to impose. First of all, as our notation indicates, we do not want to have to build a single G_{i} below more than one prescribed set U_{i}. The next issue arises because we want to combine these requirements with the coding apparatus (for partial orderings) described above. The problem here is that the coding procedures require that when we put some x into a G_{i} for a diagonalization requirement, we must also put it into L (which we do not need to permit) or into G_{k} for k ⪰ i. If we are required to put it into another G_{k} which must be permitted by some U_{k} we have hit the first (essentially insurmountable) problem. Thus we restrict our attention to codings of partial orderings and to requirements of type 6 for G_{i} which are minimal element of the given ordering. In this situation, no requirements other than those directly diagonalizing against G_{i} put numbers into G_{i} and so we have no worries about multiple permitting. We state and prove a theorem of which Lemma 2.6 (needed to define the comparison maps) is clearly a special case.

Theorem 5.1. Suppose 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 V_{i,j} are uniformly low (i.e. 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, P, Q, R, and G_{i} (for i ∈ ω) with R = ⊕G_{i} 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 ffl 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.

We have already discussed the procedures for all the requirements and so directly give the construction and verification.

5.1. Construction

The basic terminology and procedures are that same as for Theorem 4.1 with the addition of the requirements N_{i,j,e} for i ffl j and Z_{i,j,e} for i ∉ H to the priority listing of type ω. There are no direct actions for properties 5 (O) and 8 (Q) as these are satisfied by putting numbers entering various G_{i} into other sets (various G_{k} or L) and by permitting, respectively. The actions for T_{i}, M_{i} and K_{e,x} are exactly the same as in the basic construction. The only change for the D_{i,j,e} with j ∉ H is that when one puts an x into G_{j} one also puts the same x into L. We describe the action for the other requirements at the appropriate substage of stage s. (Remember, r is the stage at which the requirement being considered was last initialized and 0 if there is no such stage.)

2. D_{i,j,e} : Ψ_{e}(G_{i}) ≠ G_{j} for j ∈ H.

If we have put a number into G_{j} since stage r for requirement D_{i,j,e}, we continue on to the next substage of stage s. If not, we see if we have a realized follower x of D_{i,j,e} which is permitted by U_{j} (i.e. some z ≤ x entered U_{k} at s). If so, we put x into G_{j} and L, initialize all lower priority requirements and terminate stage s. If not, and every uncancelled follower x_{0}, …, x_{n−1} of D_{i,j,e} is realized, (if there are no followers, n = 0), we appoint a new large follower x_{n} ∈ ω^{⟨0,i,j,e⟩} of D_{i,j,e}, initialize all lower priority requirements and impose P restraint at all t ≥ s equal to

r(D, i, j, e, x_{n}, t) = max{δ_{k,j}(W_{k}; x_{n})[t]| M_{k} has higher priority than D_{i,j,e}}.

As before, this P restraint is dropped if x_{n} is cancelled or some follower of D_{i,j,e} enters G_{j}. At any stage t (until a number is put into G_{j} for D_{i,j,e}) the P restraint imposed by D_{i,j,e} is

r(D, i, j, e, t) = max{r(D, i, j, e, x_{n}, t)| x_{n} is a follower of D_{i,j,e} at t}.

6. N_{i,j,e}: If i ffl j then Ψ_{e}(G_{i} ⊕ L) ≠ G_{j}. Case 1: j ∉ H.

If this is the first stage at which we deal with this requirement since r, we choose a new large follower x for N_{i,j,e} from the column ω^{⟨1,i,j,e⟩} associated with it. As long as x is not cancelled or put into G_{j}, N_{i,j,e} imposes restraint r(N, i, j, e, t) on P as described above:

r(N, i, j, e, t) = max{δ_{k,l}(W_{k}; x)[t]| M_{k} has higher priority than N_{i,j,e} and l ⪰ j}.

This restraint is dropped when x is cancelled by some higher priority requirement or enters G_{j}. If N_{i,j,e} has an uncancelled follower x and Ψ_{e}(G_{i}; x) ↓= 0, we say the follower is realized. If the realized follower is not yet in G_{j}, we put it into G_{l} for every l ⪰ j, initialize all lower priority requirements and terminate stage s. Otherwise, we continue on to the next substage of stage s. Case 2: j ∈ H.

If we have put a number into G_{j} since stage r for requirement N_{i,j,e}, we continue on to the next substage of stage s. If not, we see if we have a realized follower x of N_{i,j,e} which is permitted by U_{j} (i.e. some z ≤ x entered U_{j} at s). If so, we put x into G_{l} for every l ⪰ j (but not into L) initialize all lower priority requirements and terminate stage s. If there is no realized follower which is permitted and every uncancelled follower x_{0}, …, x_{n−1} of N_{i,j,e} is realized (if there are no followers, n = 0), we appoint a new large follower x_{n} ∈ ω^{⟨1,i,j,e⟩} of N_{i,j,e}, initialize all lower priority requirements and impose P restraint at all t ≥ s equal to

r(N, i, j, e, x_{n}, t) = max{δ_{k,l}(W_{k}; x_{n})[t]| M_{k} has higher priority than N_{i,j,e} and l ⪰ j}.

As before, this P restraint is dropped if x_{n} is cancelled or some follower of N_{i,j,e} enters G_{j}. At any stage t (until a number is put into G_{j} for N_{i,j,e}) the P restraint imposed by N_{i,j,e} is

r(N, i, j, e, t) = max{r(N, i, j, e, x_{n}, t)| x_{n} is a follower of N_{i,j,e} at t}.

7. Z_{i,,j,e}: Ψ_{e}(V_{i,j}) ≠ G_{i} (for i ∈ H).

We first note that, by the lowness of V_{i,j} and the recursion theorem, we have recursive functions f(i, j, e, s) and g(i, j, e, s) such that

• lim_{s→∞} f(i, j, e, s) and lim_{s→∞} g(i, j, e, s) are each 0 or 1 for every i, j, e with i ∈ H;

• lim_{s→∞} f(i, j, e, s) = 1 iff there is a stage t of our construction at which there is a realized follower z of Z_{i,j,e} such that Ψ_{e}(V_{i,j}; z) ↓= 0 [t] via a V_{i,j} correct computation and z ∈ G_{i}; and

• lim_{s→∞} g(i, j, e, s) = 1 iff there is a stage t of our construction at which we do not terminate the substage of t dealing with Z_{i,j,e} because of our analysis of the realized followers already in G_{i} and there is an uncancelled follower z of Z_{i,j,e} such that Ψ_{e}(V_{i,j}; z) ↓= 0 [t] via a V_{i,j} correct computation and some x ≤ z enters U_{i} at t.

A follower y of Z_{i,j,e} is realized at s if Ψ_{e}(V_{i,j}; y) = 0 [s]. If there is a realized follower y of Z_{i,j,e} in G_{i}, we find the first u ≥ s such that f(i, e, u) = 1 or V_{i,j} ¯ ψ_{e}(y)[u] ≠ V_{i,j} ¯ ψ_{e}(y)[s]. If f(i, e, u) = 1, we terminate this substage of stage s and go on to the next substage. If f(i, e, u) ≠ 1, we first check to see if there is a realized follower y of Z_{i,j,e} which is permitted by U_{i}, i.e. some number ≤ y has entered U_{i} at s. If so we find the least u ≥ s such that either g(i, e, u) = 1 or V_{i,j} ¯ ψ_{e}(y)[u] ≠ V_{i,j} ¯ ψ_{e}(y)[s]. If g(i, e, u) = 1, we put every realized follower y permitted by U_{i} into G_{i}, initialize all requirements of lower priority and terminate stage s. If g(i, e, u) ≠ 1, and this is the first time we have dealt with requirement Z_{i,j,e} since it was last initialized at r (or all followers, y_{0}, …, y_{n−1}, appointed since r are realized or in G_{i}), we appoint a new large follower y_{0} (y_{n}) ∈ ω^{⟨2,i,e⟩} of Z_{i,j,e}. Whether we appoint a new follower or not, we now go on to the next substage of stage s.

The P restraint imposed by Z_{i,j,e} at stage t ≥ s is given by

r(Z, i, j, e, t) = max{δ_{l,i}(x)[t]| M_{l} has higher priority than Z_{i,j,e} and

x is a follower of Z_{i,j,e} at t}

5.2. Verifications

The success of the positive coding requirements (O) is immediate by the construction as is that of the permitting condition (Q). The general format of the rest of the verifications is as for Theorem 4.1 and we are proving the same claims by induction. The arguments for K_{e,x}, T_{i}, D_{i,j,e} for j ∉ H and M_{i} are exactly as for Theorem 4.1. We thus just give the analyses for the other requirements.

Lemma 5.2. (D_{i,j,e} for j ∈ H): If D_{i,j,e} is never initialized after stage r, there is a stage after which D_{i,j,e} never puts any more numbers into G_{j} and so never initializes other requirements. Moreover, D_{i,j,e} is satisfied, appoints only finitely many followers and the P restraint it imposes, r(D, i, j, e, t), is eventually constant.

Proof. If we eventually put a number into G_{j} for D_{i,j,e} after stage r, then we argue as before that the requirement succeeds and never acts again. Suppose then that we never put a number into G_{j} for D_{i,j,e}. If there is a last follower x_{n} ever appointed, say at t > r, then for one of the followers x appointed after r, ¬(Ψ_{e}(G_{i}; x_{k}) = 0); for if all these computations converged correctly to 0, we would eventually appoint another follower by construction. In this case, D_{i,j,e} is satisfied and certainly appoints only finitely many followers. Now suppose that we appoint infinitely many followers x_{n}. Each time we appoint a new one, x_{n}, every previous one y is realized by construction and we initialize all lower priority requirements. In particular, no number z < ψ_{e}(y) can ever be put into G_{i} and so all the previous followers remain realized at every later stage. Were one of them ever later permitted by U_{j}, it would go into G_{j} contrary to our assumption. Thus we can compute U_{j} recursively for a contradiction.

Finally, we argue that lim r(D, i, j, e) < ∞. In every case, only finitely many followers are ever appointed. The P restraint r(D, i, j, e, x_{n}, t) which is just max{δ_{k,j}(W_{k}; x_{n})[t]| M_{k} has higher priority than D_{i,j,e}} associated with each such x_{n} is eventually constant by the success of the requirements of type 4 as in the verification of Theorem 4.1. □

Lemma 5.3. (N_{i,j,e}): If N_{i,j,e} is never initialized after stage r, there is a stage after which N_{i,j,e} never puts any more numbers into G_{j} and so never initializes other requirements. Moreover, N_{i,j,e} is satisfied, appoints only finitely many followers and the P restraint it imposes, r(N, i, j, e, t), is eventually constant.

Proof. We argue as for D_{i,j,e}. □

Lemma 5.4. (Z_{i,j,e}): If Z_{i,j,e} is never initialized after stage r, there is a stage after which Z_{i,j,e} never puts any more numbers into G_{i} and so never initializes other requirements. Moreover, Z_{i,j,e} is satisfied.

Proof. If lim_{s→∞} f(i, j, e, s) = 1, we eventually have a realized follower y with a V_{i,j} correct computation of Ψ_{e}(V_{i,j}; y) = 0 which is in G_{i}. In this case, it is clear from the construction that Z_{i,j,e} is satisfied and eventually stops acting entirely. Suppose then that lim_{s→∞} f(i, e, t) = 0 and (for the sake of a contradiction to the first claim of the lemma) that infinitely often we put a realized follower of Z_{i,j,e} into G_{i}. By construction, this can happen at a stage s only if there is a u ≥ s such that g(i, e, u) = 1. Thus it can happen infinitely often only if lim g(i, e, u) = 1. In this case, there is a stage t at which we do not terminate the substages of t dealing with Z_{i,j,e} because of our analysis of the realized followers already in G_{i} and there is an uncancelled follower z of Z_{i,j,e} such that Ψ_{e}(V_{i,j}; z) ↓= 0 [t] via a V_{i,j} correct computation and some x ≤ z enters U_{i} at t. At such a stage t, we would put z into G_{i} by construction. As the V_{i,j} computation is correct, z will remain a realized follower with a correct computation which is in G_{i}. As this contradicts our assumption that lim f(i, j, e, s) = 0, we have proved the first assertions of the lemma.

Finally, we argue that Z_{i,j,e} is satisfied if lim f(i, j, e, s) = 0 = lim g(i, j, e, s). If there is a follower y ∉ G_{i} such that ¬(Ψ_{e}(V_{i,j}; y) = 0), the requirement is satisfied. So suppose there is no such y. Under these hypotheses, we would appoint infinitely many followers z of Z_{i,j,e} and, for almost all of them, Ψ_{e}(V_{i,j}; y) = 0. Let t_{0} be a stage by which f(i, j, e, s) and g(i, j, e, s) have reached their limits (0) and such that Ψ_{e}(V_{i,j}; y) = 1 for every follower y > t_{0} of Z. Consider the sequence of followers y_{n}, y_{n+1}, … appointed after t_{0}. Recursively in V_{i,j} we can find the stages t_{k} by which Ψ_{e}(V_{i,j}; y_{k}) = 0 by V_{i,j} correct computations. If U_{i} ¯ y_{k} ever changed at some t > t_{k} we would contradict the assumption that lim g(i, j, e, s) = 0 by providing a stage t as required to make lim g(i, j, e, s) = 1 by our choice of g. On the other hand, if there is never such a change in U_{i}, U_{i} ≤_{T} V_{i,j} for the desired final contradiction. □

6. Lattice Embeddings and Effective Successor Models

We need to combine the basic construction of a Slaman-Woodin set (§4) with the lattice embedding properties necessary to construct an effective SMA below (a, u) for any given nonzero r.e. degree a and promptly simple u. As u is promptly simple and so noncappable, there is always a degree below both a and u. Thus, without loss of generality, we may assume that a ≤ u and so state a theorem sufficient to establish Theorem 2.14 as follows:

Theorem 6.1. Given any 0 <_{T} A ≤_{T} U with U promptly simple and 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 ffl 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}) ∧ F_{0} = deg(G_{h_{2i+2}}).

The individual requirements of the types previously considered are indexed as in the basic construction with the exception that in M_{i} we replace W_{i} by W_{i} ⊕ B to take into account the fact that we are only constructing a Slaman-Woodin set above B. The new infimum requirements Y are indexed as follows:

7. Y_{f,2m+l} : If Φ_{f}(G_{h_{2m+l−1}} ⊕ E_{l}) = Φ_{f}(F_{l}) = h then h ≤_{T} G_{h_{2m+l}} for the pair m = 0 and l = 1 as well as all m > 0 and l ∈ {0, 1}.

We want to use the pinball model due to Lerman [16] to satisfy the lattice preservation properties Y. If we consider for the moment, only the lattice type requirements (D for j ∈ H and Y), the construction is like that for the lattice N_{5} (the pentagon) in that the tracing procedure is finitary and the construction falls into the class of partial lattices (the TPP partial lattices) considered and embedded in the r.e degrees by Lerman, Shore and Soare [18]. A somewhat new ingredient, even in the lattice case, is the permitting required to get all the relevant sets recursive in A. Although it is generally known that this can be done (for example Ambos-Spies and Fejer [2] prove this for the particular lattice N_{5} by an indirect argument; Ambos-Spies, Lempp and Soare have announced [4] the much more difficult result that every TPP partial lattice can be embedded in every nontrivial interval of r.e. degrees) and an argument showing that M_{5} the basic nondistributive lattice not in TPP can be embedded below any nonlow_{2} r.e. degree is given in [7], no proof combining ordinary permitting with TPP type lattice embedding has appeared in the literature. Thus we first explain (for the reader familiar with some pinball machine argument with traces (see, for example, [7]) how to satisfy all the requirements except (T) and (M) and only then how to combine them with the basic construction of a Slaman-Woodin set.

All the positive ordering facts needed are guaranteed by direct coding as specified in the theorem except for the requirements that G_{h_{2i+1}} ≤_{T} G_{h_{2i}} ⊕ E_{1} and G_{h_{2i+2}} ≤_{T} G_{h_{2i+1}} ⊕ E_{0}. These reductions are constructed by the usual tracing procedure. Whenever we have a ball (number) x^{h_{2i+1}}(x^{h_{2i+2}}) targeted for G_{h_{2i+1}}(G_{h_{2i+2}}) on the machine, it will have a trace t targeted for either G_{h_{2i}}(G_{h_{2i+1}}) or E_{1}(E_{0}). The rules of the construction will guarantee that if t does not enter the set for which it is targeted, then x^{h_{2i+1}}(x^{h_{2i+2}}) cannot enter its set either. If t does enter its set then either x^{h_{2i+1}}(x^{h_{2i+2}}) enters its set at the same stage or we appoint a new trace t′. As we will also guarantee that every ball targeted for some G_{j}, for j ∈ H, gets a last trace appointed, this procedure gives us the required reductions of G_{h_{2i+1}}(G_{h_{2i+2}}) to G_{h_{2i}} ⊕ E_{1}(G_{h_{2i+1}} ⊕ E_{0}).

The infimum requirements, Y_{f,2m+l} are met by a procedure that in essence makes (almost) every ball targeted for some G_{j} with j ∈ H (or some smaller number associated with it) pass a gate devoted to the infimum requirement that, roughly speaking, does not allow balls targeted for both sides of the pair with the specified infimum to pass simultaneously unless they are targeted for the infimum itself and forces later balls (larger numbers) to wait until the relevant length of agreement has recovered before letting new balls go by that might injure the other side.

The diagonalization requirements D and N for j ∈ H are met by appointing balls in the “holes” of the pinball machine as followers of the requirement associated with the hole. for example, the hole H_{i,j,e} devoted to the requirement D_{i,j,e} that Ψ_{e}(G_{i}) ≠ G_{j} appoints a follower x = x_{i,e,n}^{j} (the nth follower appointed for this requirement) which is targeted for G_{j}. When appointed, the ball immediately gets an appropriate sequence of traces associated with it which may change over time. The set of balls so associated with a particular follower is called the entourage of the follower. When the follower is realized (Ψ_{e}(G_{i}; x) ↓= 0), it and its entourage are released from the hole and roll down the machine until they come to the first unoccupied gate. The last ball in the entourage rolls out to the gate and receives its own sequence of traces (if needed). The rest of the entourage waits in the corral associated with this gate. The balls waiting at the gate wait until the length of agreement associated with it reaches a new maximum. The gate then opens and the balls waiting at the gate are released to roll down the machine in the same way. When a set of balls passes the last gate they enter the permitting bin. The last ball in the entourage is given a trace targeted for B and the set of balls waits for permission from A. When they are permitted by a number less than the original follower with which they are associated being enumerated into A, each one of them is put into the set for which it is targeted. If the follower itself enters its target set, the requirement is satisfied and, if not injured by the action of higher priority requirements, requires no further attention. If not, the previous ball in the entourage (which is necessarily in the corral of an unoccupied gate) moves out to the gate in whose coral it has been waiting, gets an appropriate sequence of traces (if necessary) and waits for the gate to open. Whenever a ball is placed on the machine or moves, all lower priority balls are cancelled and removed from the machine. In order to precisely describe the priority listing we must first define the tracing procedure.

6.1. Tracing and Priorities

Only balls targeted for some G_{j} for j ∈ H, j ≠ h_{0} need traces. Whenever we have a ball x^{h_{2i+1}}(x^{h_{2i+2}}) targeted for G_{h_{2i+1}}(G_{h_{2i+2}}) on the machine, it will have a trace t targeted for either G_{h_{2i}}(G_{h_{2i+1}}) or E_{1}(E_{0}). When a follower x = x_{i,e,n}^{j} is first appointed in the hole associated with a diagonalization requirement D_{i,j,e} or N_{i,j,e} it is targeted for G_{j}. If j = h_{2i+k} (k ∈ {0, 1} and 2i + k > 0), x is given a trace t targeted for E_{k}. When a ball x of the form x^{h_{2i+k}} rolls out to a gate for some infimum requirement Y_{f,2m+l}, we assign traces as follows:

a) If 2i + k = 2m + l no trace is necessary.

b) If l = k (but i ≠ m), then x gets a trace t targeted for G_{h_{2i+k−1}} and t gets a trace r targeted for E_{l} − k.

c) If l ≠ k then x gets a trace targeted for E_{k}.

When a sequence of balls (necessarily the tail end of some entourage) rolls past the last gate, the entire sequence is put into the permitting bin and the last ball in the sequence is given a trace targeted for B. (These balls then wait for A to permit the follower which is the first ball in their entire entourage and then all go simultaneously into the sets for which they are separately targeted.)

The crucial point for this construction is that we can clearly calculate a bound on the number of balls that can ever be assigned to the entourage of a follower of a requirement D_{i,j,e} or N_{i,j,e}. Indeed, the calculation of such a bound can be made solely as a function of the number of gates of higher priority than D_{i,j,e}(N_{i,j,e}). We denote such a bound by g(i, j, e) and use it to assign priorities to followers of this requirement. (For technical convenience, we have D_{i,j,e} and N_{i,j,e} between the same gates and so have a single function g(i, j, e) for both.) The idea is that g(i, j, e) is a bound on the number of permissions needed from A (at particular stages) to eventually get the follower into its target set. Contrary to the usual practice of assigning priorities to followers in the order in which they are appointed, we prefer those that have received more permissions. To be precise, each ball x is assigned a triple ⟨a, b, c⟩ that determines its priority by the lexicographic ordering of triples from ω. The first entry is the index of the requirement D_{i,j,e}(N_{i,j,e}) of which the first ball in x’s entourage is a follower. The second entry is g(i, j, e) − n where n is the number of times a ball in x’s entourage has been permitted to leave the permitting bin and enter its target set. The third entry is simply x itself. (This last coordinate orders otherwise similar balls by the point at which they are placed on the machine since new balls are always chosen larger than any already on the machine.)

The construction of the required partial lattice and the verification that it succeeds are now fairly standard with some additional care being need because of the permitting conditions and the associated change in priority ordering. Before giving a formal description of the full construction for Theorem 6.1, we will informally describe the modifications needed to combine the lattice embedding argument with the construction of a Slaman-Woodin set. The constructions should be viewed almost as two distinct ones with certain interactions. The diagonalization requirements for j ∈ H are shared between the two constructions and mediate the interactions. (Note that, as every j ∈ H is a minimal element of P, no other requirements put numbers into such G_{j}.) These requirements now sit in the appropriate hole of the pinball machine but need to appoint followers that are suitable in the sense of the Slaman-Woodin construction and impose P restraint to maintain their suitability as in that construction. Once appointed, however, they get traces assigned, wait for realization and then roll down the machine as for the pinball argument. The only interaction that they then have with the rest of the Slaman-Woodin construction is that they might initialize lower priority requirements or be cancelled by actions of higher priority requirements. Such cancellation by requirements not involved in the pinball construction, however, is finitary and so no worse than the cancelation by higher priority requirements already inherent in this construction. The gates of the pinball machine act as before and so the infimum requirements are satisfied as for the pinball argument alone. The minimality requirements M_{i} of the Slaman-Woodin construction proceed as before to assign chits, define functionals and, perhaps in the end, put a number into Q (but now only when promptly permitted by U) to kill off the requirement. The only change caused by the pinball argument is again the possibility of extra finitary cancelation of followers by actions of higher priority. The other diagonalization requirements D_{i,j,e} and N_{i,j,e} for j ∉ H, the lowness conditions K and functional constructions T are similarly affected only by additional finitary initializations. The coding requirements O are handled exactly as before. (Again noting that the minimality within P of all j ∈ H guarantees that this procedure does not put any numbers into sets involved with the pinball construction.) Thus there is no real difficulty in combining the two constructions.

6.2. Construction

We begin by listing all the requirements T_{i}, D_{i,j,e}, N_{i,j,e}, M_{i}, K_{e,x}, Y_{f,2m+l} in a priority list of order type ω such that T_{i} and T_{j} appear on the list before any D_{i,j,e} and such that each N_{i,j,e} immediately follows D_{i,j,e} and so lies between the same Y_{f,2m+l} requirements. The pinball machine is the usual one with gates corresponding to the Y_{f,2m+l} requirements and holes to the D_{i,j,e} and N_{i,j,e} ones for j ∈ H. The other requirements make no direct appearance on the machine. Each stage s of our construction will have at most s many substages n at which we may deal with requirement n. Each requirement may move balls (numbers) on the pinball machine, put numbers (balls) into some sets, axioms into a functional and impose restraint on various sets in the usual fashion.

We act to satisfy the direct coding requirements in the obvious way. Whenever a ball (number) x is put into G_{2i+k}, ⟨2i + k, x⟩ is put into R and F_{k}. Whenever a ball (number) x is put into B, ⟨0, x⟩ is put into every G_{i}. Whenever action for a requirement D_{i,j,e} puts a number x into some G_{k} the same number x is put into L. When action for a requirement N_{i,j,e} puts a number x other than the original follower of the requirement into some G_{k} the same number x is put into L [[these numbers will be larger than the computation from G_{i} ⊕ L that N_{i,j,e} needs to preserve]] ; when the follower x itself of N_{i,j,e} goes into G_{j} it also goes into all G_{k} with k ⪰ j. Whenever any action is taken for some ball we cancel all balls of lower priority (i. e. remove them from the machine) and initialize all requirements of lower priority than the one associated with the ball for which we acted. Initialization of a requirement at stage s means that all balls, chits and all restraint associated with the initialized requirement are cancelled and no further attempts are made at maintaining the correctness at numbers less than s of any functionals it is constructing. (As we only care about the functional being correct almost everywhere, this will not cause problems as long as the requirement is initialized only finitely often.) As new followers are always chosen larger than any number previously used in the construction, initialization also acts to preserve various computations. At other times we may cancel chits because the situation that made them usable has been destroyed.

We now describe our actions at substage n of stage s of the construction according to the type of the nth requirement on our list. Note that there is no direct action by the infimum requirements Y_{f,2m+l} other than the restraint imposed by the usual action of the corresponding gates. This effect is implicit in the rules of motion for the balls on the machine and so there are no explicit steps in the construction devoted to the Y_{f,2m+l} requirements. We let r be the last stage at which the requirement being considered at substage n was last initialized (r = 0 if there is no such stage). When we choose a “large” number at a stage s we mean a number larger than any used in the construction before s.

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

As in the basic construction.

2. D_{i,j,e} : Ψ_{e}(G_{i}) ≠ G_{j}.

If j ∉ H the procedure is exactly the same as in the previous constructions so we describe the new procedure if j ∈ H. If we have put a follower of D_{i,j,e} into G_{j} since stage r, we go on to the next substage. If not, we find the ball x of highest priority (as defined above) associated with a follower of D_{i,j,e} that requires attention according to one the following cases cancel all balls of lower priority, initialize all requirements of lower priority and then act as indicated in each of the cases before going on to the next substage.

a) x is a previously unrealized follower of D_{i,j,e} sitting in the associated hole and it is now realized, i. e. Ψ_{e}(G_{i}; x) ↓= 0. Release x and its trace t from the hole and let them fall down to the first unoccupied gate for a requirement Y. The trace t for x rolls out to the gate (which it now occupies) and x is put into the corral for this gate. If there is no such gate below them they

roll into the permitting bin and t gets a new large trace targeted for B.

b) x is occupying a gate for Y_{f,2m+l} and the associated length of agreement reaches a new maximum, i. e. ℓ(f, 2m+l, s) = μz{¬(Φ_{f}(G_{h_{2m+l−1}} ⊕E_{l}; z) ↓= Φ_{f}(F_{l}; z) [s])} is greater than ℓ(f, 2m + l, t) for every t < s. Let x and the later elements in its entourage [[the traces also occupying the same gate]] roll down the machine leaving the gate at which it now resides unoccupied. They roll to the first unoccupied gate. The last element of the entourage rolls out to the gate which it now occupies and the others are put into the associated corral. If there is no such gate, the balls roll into the permitting bin and the last of them is given a new large trace targeted for B.

c) x is in the permitting bin and a number less than the follower in x’s entourage is enumerated in A. We put x and the later elements of its entourage [[which are larger and also sitting in the permitting bin]] into the sets for which they are targeted. Moreover, if x is not itself the follower, we find the last element y of its entourage [[which is necessarily in some corral whose gate is unoccupied]], move it out to the gate associated with the corral in which it is waiting and appoint traces in accordance with the requirement associated with this gate as described above and cancel all balls of lower priority than y which, together with its traces, now occupies this gate. [[Note that we cancel balls again as the priority of y is now higher than that of x before our action since one more permission has been acted upon.]]

If there is no such ball that requires attention and there is no unrealized follower sitting in the hole for D_{i,j,e}, all requirements of lower priority are initialized and we choose a new large follower x for D_{i,j,e} from the column ω^{⟨0,i,j,e⟩} associated with D_{i,j,e}. [[There are no balls associated with this requirement with lower priority than x.]] We also appoint a new large trace t for x as described above and put both t and x in the hole for D_{i,j,e}. At every stage t ≥ s until x is cancelled or enters G_{j}, D_{i,j,e} imposes restraint r(D, i, j, e, x, t) on P for each element y of the entourage of x which is targeted for some G_{n} as in the basic construction. Thus we define the restraint as follows:

• r(D, i, j, e, t) = max{δ_{k,n}(W_{k}; y)[t]| y is in the entourage of some (uncancelled) follower x of D_{i,j,e} and targeted for G_{n} and M_{k} has higher priority than D_{i,j,e}}.

This restraint is dropped when some follower of D enters G_{j}. Because the action of D_{i,j,e} is not obviously finitary we must also act to stabilize this restraint: If a y in the entourage of a current follower of D_{i,j,e} is targeted for G_{n}, M_{k} has higher priority than D_{i,j,e} and some Δ_{k,n}(W_{k}; y) has just converged at s then we initialize all requirements of lower priority than D_{i,j,e} and terminate stage s.

If none of the above conditions are satisfied, we simply move on to the next substage.

3. M_{i}: If Θ_{i}(R) = W_{i} ⊕ B and Φ_{i}(W_{i} ⊕ B ⊕ P) = Q, then G_{j} ≤_{T} W_{i} ⊕ B for some j such that T_{j} has higher priority than M_{i}.

Our action here is the same as in the basic construction until we reach a point at which we would have killed the requirement by putting some particular y into Q and various γ_{j}(y) into P. At such a point we use the function p witnessing the prompt simplicity of U in the usual way to determine if U will permit us to put y into Q. If so, we proceed as in the basic construction and terminate stage s. If not, we just move on to the next substage. (We will never consider this same y again for killing M_{i}.)

[[Note that we do not have to worry about the suitability of numbers x targeted for B as any Δ computation that might be invalidated by the corresponding code entering some G_{i} is immediately repaired by x’s entering B and destroying any previously defined computation of Δ(W_{i} ⊕ B; ⟨i, x⟩).]]

4. K_{e,x}: If there are infinitely many s such that Ξ_{e}(R ⊕ P; x) ↓ [s], then Ξ_{e}(R ⊕ P; x) ↓.

We proceed exactly as in the basic construction.

At the end of substage s, we terminate stage s (if it has not been terminated before). When stage s is terminated, we go on to stage s + 1.

5. The procedure for N_{i,j,e} for j ∉ H is as in §4.4. For j ∈ H, it is like that of the D_{i,j,e} with j ∈ H modified with the same modification that relates N_{i,,j,e} to D_{i,j,e} in the basic construction. To be specific, we adjust the restraint r(N, i, j, e, x) imposed by N_{i,j,e} on P at stage t to be the following:

• r(N, i, j, e, x) = max{δ_{k,l}(W_{k}; y)[t]| y is in the entourage of some (uncancelled) follower x of N_{i,j,e} and targeted for G_{n}, l ⪰ n and M_{k} has higher priority than D_{i,j,e}}.

6.3. Verifications

The verification procedure is somewhat more complicated than in the previous arguments. Of course, we must now verify that the infimum requirements are met but the primary new source of complications in the rest of the argument is the action for the diagonalization requirements. It is no longer true that a single requirement D_{i,j,e} or N_{i,j,e} for j ∈ H acts at most once after it is last initialized. Indeed, it is not obvious that it acts at most finitely often. Thus we cannot argue ab initio that the lowness requirements of type 4 automatically succeed.

It is still true that (other than through initialization) the only restraint imposed in the construction is on P and the restraint r(M, i, s) imposed on P by requirements M_{j} of priority greater than or equal to that of M_{i} have a finite lim inf which is realized on the i-expansionary stages if there are infinitely many such stages and, if not, on almost all the stages at which r(M, i − 1, s) realizes its lim inf. As for the action of the gates, for now we simply note that it is immediate from the construction that if there is a ball which permanently occupies a gate then there are finitely many (indeed, at most two) balls which are permanently at that gate and once they occupy the gate all other balls roll past that gate when they reach it in their movement down the machine.

Once again it is immediate from the definition of their actions that if a requirement M_{i} or K_{e,x} of type 2 or 4 is never initialized after stage r, it acts at most once after r to put numbers into sets (for M_{i}) and to initialize lower priority requirements. The only other requirements that initialize anything are the D_{i,j,e} and N_{i,j,e}. We prove a lemma that shows by induction that these types of requirements eventually never initialize any other requirement and in other ways have finite effect on the construction and are satisfied.

Lemma 6.2. (D_{i,j,e}/N_{i,j,e}): If D_{i,j,e} is never initialized after stage r, there is a stage after which D_{i,j,e} never puts any more numbers into G_{j} and never initializes other requirements. Moreover, D_{i,j,e} is satisfied, appoints only finitely many followers and the P restraint it imposes, r(D, i, j, e, t), is eventually constant. The same facts are also true about the requirements N_{i,j,e}.

Proof. The arguments for D_{i,j,e} and N_{i,j,e} are essentially the same (just replace Δ_{k,n}(W_{k}; y) by Δ_{k,l}(W_{k}; y) for l ⪰ n) and for simplicity we present only that for D_{i,j,e}. If j ∉ H it is obvious that the requirement can act at most once after stage r and as in the basic construction must be satisfied. Thus we assume that j ∈ H. We can assume that any gate of higher priority than D_{i,j,e} that gets a permanent occupant already has it by stage r. Thus no members of the entourage of any later follower of D_{i,j,e} ever stop at these gates. Moreover, they can temporarily stop at other gates but must then either be released by the gate opening or cancelled by actions for a ball of higher priority also in the entourage of some follower of D_{i,j,e} (any other cancelation would contradict our choice of r). As there can be only finitely many actions taken for the balls in the entourage of a single follower, the only situations that could prevent the appointment of infinitely many followers are one of them entering G_{j} or one remaining in the hole for D_{i,j,e} forever unrealized. In either of these cases it is clear from the construction that we never act for D_{i,j,e} again. Moreover, D_{i,j,e} is then satisfied by the same argument as in the basic construction.

We therefore suppose that infinitely many followers are appointed and argue that A is recursive for a contradiction. Consider then the follower x_{1} of D_{i,j,e} that attains the highest priority of any follower appointed after r. By our choice of r and the rules of the construction x_{1} can never be cancelled. Since it must eventually be realized but never enters G_{j} by our assumptions, some member of its entourage must be permanently stuck in the permitting bin. Let x_{2}, x_{3}, … be the successively next highest priority ball to reach this same state. Remember that the priorities of these balls are given by triples the first coordinate of which is simply the global priority of D_{i,j,e}. The second coordinate is g(i, j, e) minus the number of times balls in the entourage have been permitted to enter their target sets. Thus this coordinate must eventually stabilize as well, say at n. Consider now the balls x_{m} for m ≥ m_{0} which all have the second coordinate of their priorities equal to n. It is clear that once such a ball is in the permitting bin, it can never be permitted to enter its target set as that would increase the priority of the remaining balls in the entourage contrary to the choice of n. Moreover, it can be cancelled only by some smaller ball with the same first two coordinates of its priority triple the same as its own moving. This can happen only when the smaller ball was stopped at one of the gates that are not permanently occupied when the larger one entered the permitting bin. As we know which these gates are and that any occupants are only temporary, we can tell when any ball in the final priority state (as far as the first two coordinates are concerned) enters the permitting bin if it will ever be cancelled. (It will be cancelled if and only if there is a higher priority ball at one of these gates in which case one of those balls must eventually enter the permitting bin.) Thus we can recursively list the x_{m} which enter the permitting bin in this final state and are never cancelled. As usual this listing provides a way of recursively computing A for the desired contradiction.

Finally, we argue that lim r(D, i, j, e) < ∞. Consider any y > r targeted for G_{n} which is in the entourage of one of the finitely many followers of D_{i,j,e}. If some Δ_{k,n}(W_{k}; y) converges for the first time at a stage t after x is appointed, we initialize all lower priority requirements. Thus no number below θ_{k}δ_{k,n}(y) can ever enter R after stage t and so none below δ_{k,n}(y) can enter W_{k}. Thus δ_{k,n}(y) is fixed from now on and so can never again cause initialization by its convergence. □

Thus we know that for each requirement there is a stage r after which it is never initialized. The argument that the requirements K_{e,x} are met is now routine and exactly as in the basic construction. Given the success of these requirements and the fact that initializations for each requirement are bounded, we can now argue for the success of the M_{i} requirements. As in the basic construction we see that if all of the functionals Δ_{i,j} fail infinitely often then there are infinitely many x for which we reach a point in the construction when we would put x into Q if permitted by U at that particular stage. The prompt simplicity of U then guarantees that we actually put one of these numbers into Q. The argument of the basic construction then shows that M_{i} never acts again, imposes only a finite, eventually constant restraint and is satisfied.

All that remains is to verify that the infimum requirements are met. We first prove a technical lemma about the priority ordering.

Lemma 6.3. If balls x < y are both on the machine at stage s then x has higher priority than y.

Proof. Suppose for the sake of a contradiction that y has higher priority than x. As y is larger than x it must have been placed on the machine after x. If it had higher priority than x when initially placed on the machine then x would have been cancelled by construction. On the other hand, if y’s priority improved at some stage to make it higher than that of x, then x would have been cancelled at that stage according to clause (c) of item 2 (or 5) of the construction. □

Lemma 6.4. If Φ_{f}(G_{h_{2m+l−1}} ⊕ E_{l}) = Φ_{f}(F_{l}) = h then h ≤_{T} G_{h_{2m+l}} for the pair m = 0 and l = 1 as well as all m > 0 and l ∈ {0, 1}.

Proof. Let r be a stage after which the corresponding requirement Y_{f,2m+l} is never initialized and every gate of higher priority that has a permanent occupant already has one. We claim that h(x) can be correctly computed by finding a stage s > r at which ℓ(f, 2m + l, s) > x, the computations are G_{h_{2m+l}} correct (i.e. G_{h_{2m+l}} ¯ u[s] = G_{h_{2m+l}} ¯ u where u is the use of the relevant computations at x) and only balls that never move again are at gates, corral or bins at or below the gate for Y_{f,2m+l}. Now, we can recognize such a stage recursively in G_{h_{2m+l}} as there are only finitely many balls permanently at gates or corrals below the gate for Y_{f,2m+l} while ones in the permitting bin are there permanently if and only if the trace targeted for B at the end of their entourage is not in B, a fact recursive in B = G_{h_{2m+l}}^{[0]} and, of course, G_{h_{2m+l}}-correctness is recursive in G_{h_{2m+l}}. By the hypothesis of the Lemma there is a t > r such that at every s > t the length of agreement is larger than x and G_{h_{2m+l}}-correct . Thus all that remains to be shown is that there is one at which only balls that will permanently remain in their current positions are on the machine at or below the gate for Y_{f,2m+l} and that the value computed at such a stage s is the correct one.

As for the first claim, consider any stage s > t at which some cancellation or initialization is caused by a requirement and no requirement of the same or higher priority ever causes any cancellation or initialization again. (Clearly such stages exist by the arguments above.) It is clear from the definition of the construction that any ball now on the machine at or below the gate for Y_{f,2m+l} must remain in its current location forever. Thus any such stage s is as required and there are obviously infinitely many such.

We now argue by induction that the computation at x found at a stage s as described above remains constant and is G_{h_{2m+l}}-correct on at least one side of the infimum at every later stage. Now at s any ball that can injure the computation at x must already be on the machine (ones appointed later are larger than the use) and above the gate for Y_{f,2m+l} (by hypothesis the associated length of agreement goes to infinity and so no ball permanently occupies the gate for Y_{f,2m+l}). Let z be the first ball below the use which enters one side of the infimum (it cannot enter both as the computation is assumed to be G_{f,2m+l}-correct). We claim that z occupies the gate for Y_{f,2m+l} at some stage after s_{0} and before it enters the set for which it is targeted. If not, then by the construction at the stage at which it rolls past this gate, the gate must be occupied by a ball of higher priority. (If it were occupied by one of lower priority that ball would be cancelled when we are about to move z and so the gate would become unoccupied in which case z would have to stop at the gate or the corral. In the latter case, it would have to move out to the gate before going past it.) Thus z was not on the machine when the ball occupying the gate reached it (for it would then have been cancelled). The gate has not opened since the ball of higher priority than z reached it (or the ball would have left the gate) and so z is larger than the use of the computation at x for a contradiction.

Suppose x occupies the gate for Y_{f,2m+l} and is about to leave it at stage t. It leaves the gate because a new maximum length of agreement has been reached. As no number less than the use at s has entered either side of the infimum, the value is the same as at s. We claim that the computation from the side of the infimum for which x is not targeted now becomes G_{h_{2m+l}}-correct. Of course, any ball larger than x is cancelled when x moves by the rules of the construction and Lemma 6.3. On the other hand, any ball smaller than x is within the range already assumed to be G_{2m+1}-correct. To continue the inductive hypotheses we now only need to argue that all balls less than the use at t that might enter this (now certified as G_{h_{2m+l}}-correct) side of the infimum are above the gate for Y_{f,2m+l}. Any such ball below the gate must have passed the gate at some stage after s (as the ones below at s never move and no balls are placed on the machine by requirements of higher priority than Y_{f,2m+l} by our choice of r). If the ball has lower priority than x then it would have been cancelled at t and so no longer be on the machine. If it had higher priority than x it would have cancelled x when attempting to pass the gate contrary to our assumption that x is still at the gate at t. Similarly, if it had passed the gate with lower priority than x but gotten higher priority afterwards then it would have cancelled x when it got its higher priority. We can now continue by induction to prove that at every stage when a ball that would injure the previously certified G_{h_{2m+l}}-correct side leaves the gate associated with Y_{f,2m+l} that the computation from one side of the infimum is made G_{h_{2m+l}}-correct and gives the same output as that given at s. □

7. Coding Σ_{3} Sets

Our goal in this section is to prove the coding results needed in §2 as given by Theorem 2.15 which we recall as follows:

Theorem 7.1. If ⟨g_{i}⟩ is a u.r.e. antichain, ⊕_{i}g_{i} is low and (∀i)[a Θ g_{i}], then for each Σ_{3}^{0}(A)–set S there are c, d ≤ a such that S = {i : c ≤ g_{i} ∨ d}.

We begin by giving an effective approximation to S, using methods similar to ones of Nies in [20] and [23].

Lemma 7.2. There is a u.r.e. sequence X_{⟨i,n,m⟩} of initial segments of ω such that

i ∈ S ⇒ a.e. n, m X_{⟨i,n,m⟩} is finite and  (7.1)

i ∉ S ⇒ ∀n ∃m(X_{⟨i,n,m⟩} = ω).  (7.2)

Moreover, there is a partial A–recursive function χ_{X} for the array X_{k}, which is defined at k = ⟨i, n, m⟩ iff X_{k} is finite, in which case X_{k} equals X_{k,χ_{X}(k)}.

Proof. Since S is Σ_{3}^{0}(A), there is an r.e. set W such that

i ∈ S ⇔ ∃n ∀m(⟨i, n, m⟩ ∈ W^{A}).

Let Y_{k} = {s : (∃t ≥ s)(k ∉ W^{A}[t])}. Then this sequence is u.r.e., each Y_{k} is an initial segment of ω and k ∈ W^{A} ⇔ Y_{k} is finite and so (7.2) holds for ⟨Y_{k}⟩. Moreover, the second claim of the lemma holds for the sequence: To calculate the partial function χ_{Y} (k) required for the array Y_{k}, search for an s such that k ∈ W^{A}[s] by an A–correct computation.

We now modify ⟨Y_{k}⟩ to satisfy (7.1) by first reducing the number of sets which equal ω. By the row ⟨i, n⟩ (of Y = {Y_{k}|k ∈ ω}) we mean the collection of sets {Y_{⟨i,n,m⟩}|m ∈ ω}. First we replace Y_{⟨i,n,m⟩} by Y′_{⟨i,n,m⟩} = Y_{⟨i,0,m⟩} ∩ … ∩ Y_{⟨i,n,m⟩}. Then, if the row ⟨i, n⟩ (of Y′) contains only finite sets, so do all rows ⟨i, n′⟩, n′ > n. To compute the partial function χ_{Y′} required for the array Y′_{k} as in the Lemma proceed as follows: Given ⟨i, n, m⟩ start computations with oracle A for χ_{Y} (⟨i, j, m⟩), j ≤ n in parallel; if any of these computations converge, continue computing and enumerating all the sets Y_{⟨i,j,m⟩} until we have, for each j ≤ n, either χ_{Y} (⟨i, j, m⟩) converges or Y_{⟨i,j,m⟩} contains all the elements in the smallest of the Y_{⟨i,j′,m⟩} for which χ_{Y} (⟨i, j′, m⟩) has converged.

Next, we modify Y′ once more to produce the desired sequence ⟨X_{k}⟩ by guaranteeing that each row has at most one infinite member: Let C_{m} = Y′_{⟨i,n,m⟩}. We replace this set in Y′ by a class of sets D_{⟨m,g⟩} = X_{⟨i,n,⟨m,g⟩⟩} where g is thought of as a guess about | ⋃_{j<m} C_{j}|. As long as the guess is correct, D_{⟨m,g⟩} is allowed to copy C_{m}. Formally, let D_{p,0} = ∅ and, for s > 0 and p = ⟨m, g⟩, if g = | ∪_{j<m} C_{j,s}|, let D_{p,s} = C_{m,s}, otherwise let D_{p,s} = D_{p,s−1}. Clearly, there is at most one ⟨m, g⟩ such that D_{⟨m,g⟩} = ω. (It is the pair for which m is least such that Y′_{⟨i,n,m⟩} is infinite and g = | ∪_{j<m} C_{j,s}|.)

We now show how to compute the required partial function χ = χ_{X} for the array ⟨X_{k}⟩ that we have obtained. Suppose k = ⟨i, n, p⟩. As before, let C_{m} = Y′_{⟨i,n,m⟩} and let p = ⟨m, g⟩. To compute χ_{X}(k), we find an s such that either | ⋃_{j<m} C_{j,s}| > g, in which case we give this s as output, or all computations χ_{Y′}(⟨i, n, j⟩) have converged at stage s for j < m. If | ⋃_{j<m} C_{j,s}| < g, again we give s as output, but if it equals g, we start simulating the computation of χ_{Y′}(⟨i, n, m⟩). □

To prove Theorem 7.1, we want to build r.e. sets C, D ≤_{T} A such that

i ∈ S ⇒ C ≤_{T} G_{i} ⊕ D  (7.3)

and

i ∉ S ⇒ ∀n (C ≠ Ψ_{n}^{G_{i}⊕D}),  (7.4)

where ⟨Ψ_{n}⟩ is an effective listing of all Turing functionals such that, to compute the value at input x, we first compute all values for smaller inputs (this will be technically convenient).

Intuitively, to satisfy (7.4) we view the number n in (7.2) as an index for a T – reduction. For each m, a requirement Q_{⟨i,n,m⟩} tries to guarantee that C ≠ Ψ_{n}^{G_{i}⊕D}. If i ∉ S, then the first requirement such that X_{⟨i,n,m⟩} = ω will succeed. If X_{⟨i,n,m⟩} is finite, Q_{⟨i,n,m⟩} acts only finitely often. Thus the diagonalization requirements are

Q_{⟨i,n,m⟩} : X_{⟨i,n,m⟩} = ω ⇒ C ≠ Ψ_{n}^{G_{i}⊕D}.

We write i_{Q}(k) = i if Q_{k} works on (7.4) for i, i.e., if k = ⟨i, n, m⟩ for some pair n, m.

For each i, there are infinitely many coding requirements C_{k} (k = ⟨i, n⟩), whose goal is to build a functional Δ_{k} such that C = Δ_{k}^{G_{i}⊕D}. We write i_{C}(k) = i if k = ⟨i, n⟩ for some n. Fix C_{0} < Q_{0} < C_{1} < Q_{1} … as the priority ordering of the requirements. C_{k} may be affected by lower priority requirements Q_{p} such that i_{C}(k) = i_{Q}(p). However, each such Q_{p} can affect the functional Δ_{k} at only finitely many inputs (which are distinct for distinct p) and, if X_{p} is finite, only finitely often at each of those inputs. Thus, if it needs to succeed, the coding requirement relies on the hypothesis that each single requirement Q_{p} affects it only finitely often:

C_{k} : (∀p ≥ k)[i_{Q}(p) = i_{C}(k) ⇒ X_{p} finite] ⇒ C = Δ_{k}^{G_{i}⊕D}.

If i ∈ S then, since infinitely many coding requirements work on (7.3), we can, by (7.1), choose k with i_{C}(k) = i such that the hypothesis is correct. Therefore C ≤_{T} G_{i} ⊕ D.

We now describe the strategies for the requirements. C_{k} tries to build the functional Δ_{k}. For an input x, let δ_{k}(x) be the use of this functional. Whenever G_{i}⊕D ¯ δ_{k}(x)+1 changes, we have a chance to declare Δ_{k}^{G_{i}⊕D}(x) to be undefined, and C_{k} will have to redefine it at a later stage t to the correct value C_{t}(x), with a new use δ_{t}(x) (normally a large number). We can only enumerate x into C while Δ_{k}^{G_{i}⊕D}(x) is undefined. To make Δ_{k}^{G_{i}⊕D} total, we have to make sure that, for each x, Δ_{k}^{G_{i}⊕D}(x) is defined at some stage and is redefined only finitely often.

We now explain the Q_{p} strategy, and describe when to correct the functionals Δ_{k}. Let p = ⟨i, n, m⟩ and suppose that X_{p} = ω. The goal of the Q_{p}–strategy is to diagonalize against C = ψ_{n}^{G_{i}⊕D}. To do so, Q_{p} has to enumerate, at some stage s, a follower y such that Ψ_{n}^{G_{i}⊕D}(y) = 0 into C where ψ_{n}^{G_{i}⊕D}(y) does not change later. To ensure that C ≤_{T} A, Q_{p} also requires an A–permission, i.e., A_{s} ¯ y ≠ A_{s−1} ¯ y, before enumerating y into C at stage s. Now, the computation Ψ_{n}^{G_{i}⊕D}(y) = 0 could later be destroyed by a G_{i}–change not under our control. However, using the lowness of G_{i}, we can prevent Q_{p} from acting infinitely often because of this kind of injury. On the other hand, the computation could also be destroyed by an enumeration of uses δ_{k}(z) into D (k ≤ p). The main case to worry about is the necessity of enumerating δ_{k}(y) into D for any k ≤ p for which Δ_{k}(y) is already defined, since we need to make Δ_{k}(y) undefined before enumerating y into C. To avoid the destruction of ψ_{n}^{G_{i}⊕D}(y) by such an enumeration, Q_{p} tries to ensure that ψ_{n}^{G_{i}⊕D}(y) is k–cleared for each k ≤ p, i.e.,

δ_{k}(y) > ψ_{n}^{G_{i}⊕D}(y)  (7.5)

(where ψ_{n}^{G_{i}⊕D}(y) is, as usual, the use of Ψ_{n}^{G_{i}⊕D}(y)). If i_{C}(k) = i_{Q}(p) the k-clearing is done in an active way: First, Q_{p} picks a “killing point” x where it intends to make Δ_{k}(x) undefined in the limit if X_{p} is infinite. The followers y of Q_{p} will all be chosen to be ≥ x. If X_{p} increases, then δ_{k}(x) is enumerated into D and Δ_{k}(x) is declared to be undefined. Since δ_{k}(x) will be redefined to be a large number, eventually we reach the desired inequality (7.5) (provided that Ψ_{n}^{G_{i}⊕D}(y) converges). The second claim in Lemma 7.2 is used to show that A can calculate when such enumerations have ceased and so to prove that D ≤_{T} A. For technical reasons, we will actually require that ψ_{n}^{G_{i}⊕D}(y) ≤ max X_{p} whenever we consider putting a follower y into D in this way. We also ensure that δ_{k}(x) > max X_{p} whenever k ≤ p ≤ x and i_{Q}(p) = i_{C}(k).

Now we discuss clearing the computation Ψ_{n}^{G_{i}⊕D}(y) of markers δ_{k}(y) when k < p and i_{Q}(p) ≠ i_{C}(k) = j. In this case, Q_{p} relies on G_{j}–changes to ensure that Ψ_{n}^{G_{i}⊕D}(y) will be k–cleared. Q_{p} maintains a whole list of followers y_{n,s} at stage s such that Ψ_{n}^{G_{i}⊕D}(y_{r}) = 0[s] with use below max(X_{p,s}). If y is appointed as a new follower, Q_{p} restrains D ¯ ψ_{n}^{G_{i}⊕D}(y) and requests that ψ_{n}^{G_{i}⊕D}(y) be k-cleared (i.e., that δ_{k}(y) be moved above at the next stage where G_{j} ¯ δ_{k}(y) changes). Since G_{j} Θ_{T} G_{i}, (if the requirement is not met in some trivial way) there will be infinitely many r with stages s such that ψ_{n}^{G_{i}⊕D}(y_{r}) = 0[s] by a G_{i}–correct computation and G_{j} ¯ y_{r} changes at s. Since δ_{k}(x) ≥ x for any x, this allows Q_{p}’s request for clearing to be carried out.

Altogether a Q_{p} strategy is confronted with p + 1 coding strategies of higher priority, C_{k} (k ≤ p). The above actions are carried out for each k in parallel. In the end we can argue that potentially infinitely many G_{i}–correct computations Ψ_{n}^{G_{i}⊕D}(y) are cleared for all k ≤ p: By the D–enumeration of Q_{p} all computations we consider are eventually k–cleared if i_{C}(k) = i_{Q}(p). For the other numbers k ≤ p, we argue by induction on descending k: If k ≤ p the above argument can be carried out to k–clear computations which are already k′-cleared for all k′ with k < k′ ≤ p, because we can (by induction, G_{i}–recursively enumerate infinitely many G_{i}–correct computations Ψ_{n}^{G_{i}⊕D}(y) which are already so cleared. Thus, infinitely many G_{i}–correct computations will be k–cleared for all k ≤ p. As A Θ_{T} G_{i}, one such will have its input y permitted by A. At this point we will put y into C successfully diagonalizing and the action for Q_{p} will cease.

There is one final problem: For p′ < p, the D–enumeration of the higher priority Q_{p′} due to X_{p′}–increase may destroy computations Ψ_{n}^{G_{i}⊕D}(y) on which Q_{p} relies. If X_{p′} is finite, Q_{p} can assume this side effect has ceased to occur, but if X_{p′} = ω, Q_{p} must choose followers in a way such that the associated uses are ≤ max X_{p′} (as it did for X_{p} itself). So we have to equip Q_{p} with a guess at which sets X_{p′} = ω for p′ < p. This is done in a standard way using a priority tree. We use 2^{<ω} as our tree of strategies. If s > 0, we define the sequence δ_{s} of accessible nodes by induction on k. Of course, δ_{s}(0) = ∅. For 1 ≤ k ≤ s, we define δ_{s}(k) as follows: Let t < s be the greatest stage such that t = 0 or δ_{s} ¯ k ⊆ δ_{t}, let δ_{s}(k) = 0 if |X_{k,t}| < |X_{k,s}| and δ_{s}(k) = 1 otherwise. For α ∈ 2^{<ω}, s is an α–stage if s = 0 or α ⊆ δ_{s}. Since the tree is finitely branching there exists a true path f (as defined in [35]), and

X_{p} = ω ⇔ f(p) = 0.

If α ∈ 2^{<ω}, |α| = k, we say that α has a version of the C_{k}–strategy and α 0 is has a version of the Q_{k}–strategy (recall that Q_{k} only has to be active if X_{k} = ω, i.e., if f(k) = 0). We adopt the notation above in the obvious way. For instance, we write i_{C}(α) instead of i_{C}(|α|), etc. As in [35], ω^{[α]} stands for ω^{[n(α)]}, where α ↦ n(α) is some effective numbering of strings.

If k = ⟨i, n, m⟩, let ℓg(p, s) = max{x : (∀z < x)(ψ_{n}^{G_{i}⊕D}(z) = C(z)[s])} be the length of agreement associated with Q_{p}. To avoid the problem explained above, α 0’s version of the Q_{p} strategy only considers numbers y as followers at stage s which are eligible for α 0, i.e.,

y ∈ ω^{[α]} ∧ ℓg(p, s) > y ∧ Ψ_{n}^{G_{i}⊕D}(y) = 0[s]∧
(∀β)[β 0 ⊆ α 0 ⇒ max X_{|β|} > ψ_{n}^{G_{1}⊕D}(y)[s]].

Note that, unlike the case of more involved tree constructions, the sequence ⟨δ_{s}⟩ and hence the true path are predetermined by ⟨X_{k}⟩. This is the reason why we can prove that C, D ≤_{T} A: A can enumerate those nodes which are to the left of the true path (this follows from Lemma 7.2) and hence can give an upper bound on the stages at which a Q–strategy α 0 can possibly enumerate a number into D.

We now present the formal construction and verification needed to prove the theorem.

Construction:

Stage 0. Let C_{0} = D_{0} = ∅. Initialize all strategies. Stage s, s > 0. Initialize all strategies β >_{L} δ_{s}. For each k ≤ s in order, carry out the substage k. Substage k. Let α = δ_{s} ¯ k, and let t < s be the last α–stage. Let i = i_{C}(k).

Actions for the C_{k}–strategy α. Firstly, if there is an x such that G_{i,t} ¯ δ_{α,t}(x) ≠ G_{i,s} ¯ δ_{α,t}(x), and some Q–strategy β, α ⊂ β, is requesting clearing of Δ_{α}(x), now let x be minimal such, declare Δ_{α}(x′) undefined for each x′ ≥ x_{n} and cancel all clearing requests for such x′.

Secondly, for all x such that Δ_{0}(x) is now undefined, redefine it with value C_{s}(x), and a large use δ_{α}(x), so that δ_{α} is monotonic.

Suppose k < s and α 0 ⊆ δ_{s}. We describe the actions for the Q_{k}–strategy α 0. The strategy has as parameters a “killing point” x > k and a chain y_{0} < ⋯ < y_{n−1} of followers, where x < y_{0}.

Suppose k = ⟨i, n, m⟩.

Step 1. (Killing higher priority C requirements) If the killing point x is undefined, assign a large number as its value. If δ_{β}(x) is defined, where β ⊆ α and i_{C}(β) = i_{Q}(α), enumerate δ_{β}(x) into D and declare Δ_{β}(x′) undefined for x′ ≥ x. [We continue this action even if it seems that Q_{k} has already been met.]

Step 2. (Cancelling followers) Let t < s be the last α 0–stage. If a follower y_{p} was already appointed at stage t, but G_{i} changed below, the use ψ_{n}^{G_{i}⊕D}(y_{p}), then cancel y_{p} and the clearing request associated with y_{p}.

Step 3. (Appointing a new follower) Let ỹ be the maximal follower which is still uncancelled (and ỹ = 0 if no such follower exists), and let s̃ be the last stage at which the Q_{k}–strategy α 0 appointed ỹ (and s̃ = 0 if ỹ = 0). Since ⊕G_{i} is low, there is, by the recursion theorem, a total recursive function g(α, ỹ, s̃, t) such that lim_{t} g(α, ỹ, s̃, t) exists, equals 0 or 1, and the limit is 1 iff the following Σ_{1}^{0}(G_{i})–question has an affirmative answer:

(∃s > s̃)(∃y > ỹ)[at stage s of our construction

y is eligible for α 0 via a G_{i}–correct computation].  (7.6)

Now, at the actual substage k of stage s of the construction, look for a minimal number y > ỹ which is eligible for α 0. Find the least number s′ ≥ s such that either G_{i} changes below the use ψ_{n}^{G_{i}⊕D}(y)[s] by stage s′ or f(α, ỹ, s̃, s′) = 1. In the second case, we view y as certified and therefore appoint y as a new follower. To restrain C and D, initialize all strategies β such that α 0 ⊂ β or α 0 <_{L} β.

Step 4. (Diagonalization) If there is a follower y which was already appointed at the last α 0 stage t < s, remained uncancelled since t, is β cleared for all β ⊆ α, and moreover, A_{t} ¯ y ≠ A_{s} ¯ y, then let y be the least such follower. To diagonalize, enumerate y into C. For each β ⊆ α, enumerate δ_{β}(y) (if defined) into D and declare Δ_{β}(y′) undefined for y′ ≥ y.

Verification:

Lemma 7.3. Suppose that α 0 is a Q_{k}–strategy on the true path. Then the action of α 0 in Steps 2, 3 and 4 is finitary, and Q_{k} is met.

Proof. Let k = ⟨i, n, m⟩ = |α|.

By induction, let s_{0} be the least α 0 stage such that α 0 is not initialized at any stage s ≥ s_{0}. Assume for a contradiction that

for each p, α 0 eventually appoints a follower y_{p} at stage s ≥ s_{0}

and this follower is never cancelled.  (7.7)

We call such a follower stable. Since α 0 has highest priority from s_{0} on, stability can be recognized recursively in G_{i}.

Claim: Assume (7.7). Then there are infinitely many stable followers of α 0 which are eventually β–cleared for all β ⊆ α. Proof of Claim: Since the follower is automatically β-cleared if i_{C}(β) = i_{Q}(α) by the definition of eligibility, we only need to consider those β such that i_{C}(β) ≠ i_{Q}(α). For these β, we argue by downward induction on the length of β. Suppose the claim is true for all β′, β ⊂ β′ ⊆ α, and j = i_{C}(β) ≠ i_{Q}(α). If after stage s_{1} ≥ s_{0} no more stable followers which are already β′ cleared for β ⊂ β′ become β–cleared, then G_{j} ≤_{T} G_{i}: Given an input z, G_{i}–recursively find an α 0 stage s ≥ s_{1}, such that a stable y > z has been appointed which is β′–cleared for all β′ ⊃ β. Since α 0 requests clearing of Δ_{β}(y), any G_{j} ¯ y change would lead to β–clearing of Ψ_{n}^{G_{i}⊕D}(y). So G_{j,s}(z) = G_{j}(z).

To obtain a contradiction from (7.7) we now argue that α 0 could successfully diagonalize in Step 4 through a stable completely cleared y. Since A Θ_{T} G_{i}, by a similar argument as above, there must be an α 0–stage s ≥ s_{0} where a stable y which is cleared for all β ⊆ α has been appointed such that A ¯ y changes by the next α 0 stage. So in Step 4, α 0 diagonalizes through the least such y_{1} which causes the length of agreement associated with Q_{k} to be permanently below y, contrary to the assumption (7.7) .

Since (7.7) fails, there is a pair (ỹ, s̃) such that ỹ is the maximum stable follower ever appointed after stage s_{0}, and it is appointed at the α 0–stage, s̃ for the last time (let ỹ = 0, s̃ = s_{0} if no stable follower exists at all). We claim that there can be no pair of witnesses y, s for (7.6) as otherwise lim_{s} f(α, ỹ, s̃, s) = 1. Choose a minimal y > ỹ which witnesses (7.6) , and let s > s̃ be the first α 0 stage where Ψ_{n}^{G_{i}⊕D}(y) converges and is G_{i}–correct. Then we would appoint y as the next follower > ỹ at stage s: by the properties on the function Ψ_{n} described in the beginning, if we had appointed some y′ > y at the stage s′, s̃ < s′ < s and it were uncancelled, we would have seen the computation Ψ_{n}^{G_{i}⊕D}(y)[s] already at the stage s′. Moreover, if some y′, ỹ < y′ < y were appointed at s, then Ψ_{n}^{G_{i}⊕D}(y′) would also be G_{i}–correct, contrary to the minimality of y. Finally, G_{i} ¯ ψ_{n,s}(y) is stable, so we can appoint y at s. A new stable follower has been found, contrary to the definition of ỹ.

Since there is no witness to (7.6), lim g_{t}(α, ỹ, s̃, t) = 0, so α 0 will stop all actions through Steps 2, 3 (and hence through 4) at some point. To finish the proof of Lemma 1, we show that Q_{k} is met: If Ψ_{n}^{G_{i}⊕D} = C, there is a number y ∈ ω^{[α]} above all numbers in ω^{[α]} that are ever appointed by α 0 such that Ψ_{n}^{G_{i}⊕D}(y) = 0. But then the answer to (7.6) is “yes”! □

Lemma 7.4. i ∈ S ⇔ C ≤_{T} G_{i} ⊕ D.

Proof. For one direction suppose that i ∉ S. For arbitrary n, we show that C ≠ Ψ_{n}^{G_{i}⊕D}. Let m be the number such that X_{⟨i,n,m⟩} = ω. Then, for some α, |α| = ⟨i, , m⟩, α 0 is on the true path. So, by Lemma 7.3 , Q_{⟨i,n,m⟩} is met.

Now suppose that i ∈ S. The, by (7.1) , there exists a k, i_{C}(k) = i, such that the hypothesis of C_{k} is correct. Let α on the true path have a version of the C_{k}–strategy. Suppose α is not initialized after s_{0}. Since a Q–strategy β 0, α ⊆ β, enumerates δ_{α}(y) into D whenever it enumerates y into C, after stage s_{0} the functional Δ_{α} can always be redefined correctly. It remains to verify that Δ_{α} is not partial, i.e., Δ_{α}(y) is only declared undefined finitely often for each y. Δ_{α}(y) can be declared undefined for two reasons:

(1) Some Q–strategy β 0, α ⊆ β, requests clearing and its killing point is ≤ y. This can happen only finitely often, by initialization if β 0 is to the right of the true path, and by Lemma 7.3 if β 0 is on the true path.

(2) If i_{Q}(β) = i for some β, α ⊆ β, the killing point of the Q–strategy β 0 is ≤ y (hence |β| ≤ y) and X_{|β|} increases, i.e., β 0 ⊆ δ_{t}. By the choice of k, this can only happen finitely often. □

Lemma 7.5. C, D ≤_{T} A

Proof. We first analyze what A knows about the true path.

Claim. There is an A–recursive function p(α, t_{0}) such that, for each t_{0}, p(α, t_{0}) is the first stage t ≥ t_{0} such that one of the following happens:

(a) α ⊆ δ_{t}, or

(b) δ_{t} <_{L} α, or

(c) α <_{L} δ_{t′} for all t′ > t.

We define p by recursion on k = |α|. Let p(∅, t_{0}) = t_{0}, and, for each t, let p(α 1, t_{0}) = p(α, t_{0}) (in these cases, (a) through (c) are satisfied). Now let

p(α 0, t_{0}) = p(α, t̃),

where t̃ is the first stage ≥ t_{0} where |X_{k}| increases or we have determined in t̃ stages, using the computation procedure from Lemma 7.3 with A as an oracle, that X_{k} = X_{k,χ(k)} (in which case χ(k) < t̃, so also X_{k} = X_{k,t̃}).

To verify the required properties, if α <_{L} δ_{t}, for t > p(α, t̃), then also α 0 <_{L} δ′_{t}. If δ_{p(α,t̃)} <_{L} α, then δ_{t} <_{L} α 0. Finally if (a) holds for α, i.e., α ⊆ δ_{p(α,t̃)}, then we consider two cases: if t̃ is the first stage where |X_{k}| increases, then α 0 ⊆ δ_{p(α,t̃)}. If we found out that X_{k} = X_{k,t̃}, then p(α, t̃) is an upper bound for the last stage t where a previous increase of |X_{k}| can possibly lead to α 0 ⊆ δ_{t}, so we are in case (c) for α 0.

Now to prove that C ≤_{T} A, consider an input y ∈ ω^{[α]}. If y ever enters C it must enter at an α 0–stage, where A ¯ y changed since the last α 0–stage . Let t_{0} be such that A ¯ y = A_{t_{0}} ¯ y, and evaluate t = p(α, t_{0}) recursively on A. Then t is the last stage where this C–enumeration can take place. So C ≤_{T} A.

Finally, to prove that D ≤_{T} A, first apply a similar argument to the D– enumeration of y = δ_{β}(z) along with a diagonalization of a Q–strategy through z (note that y ≥ z). If y is enumerated because y = δ_{β}(x) and x is the killing point of some Q–strategy α 0, β ⊆ α, this strategy can be identified by stage y. So p(α, y) is an upper bound for any stage at which such an enumeration of y into D can take place. Λ

8. References

1. K. Ambos-Spies [ta], Automorphism bases of the r.e. degrees, preprint, University of Heidelberg .

2. K. Ambos-Spies and P. Fejer [1988], Degree theoretical splitting properties of the recursively enumerable sets, J. Symb. Logic 53, 1110-1137.

3. K. Ambos-Spies, C. G. Jockusch, R. A. Shore and R. I. Soare [1984], An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc. 281, 109-128

4. K. Ambos-Spies, L. Lempp and R. I. Soare [ta], Intervals of recursively enumerable degrees: Lattice embeddings and non-ℵ_{0}-categoricity of the partial order, in Proceedings of Logic Colloquium ’97, S. B. Cooper et al., eds., to appear.

5. S. B. Cooper [1993], On a conjecture of Kleene and Post, University of Leeds, Department of Pure Mathematics Preprint Series No. 7.

6. S. B. Cooper [1996], Beyond Gödel’s theorem: the failure to capture information content, University of Leeds, Department of Pure Mathematics Preprint Series, No. 4.

7. R. G. Downey and Shore, R. A. [1995], Degree theoretic definitions of the low_{2} recursively enumerable sets, J. Symb. Logic 60 (1995), 727-756.

8. R. G. Downey and Shore, R. A. [1996], Lattice embeddings below a nonlow_{2} recursively enumerable degree, Israel J. Math. 94, 221-246.

9. L. Harrington and A. Nies [ta], Coding in the lattice of recursively enumerable sets, Advances in Mathematics, to appear.

10. L. Harrington and S. Shelah [1982], The undecidability of the recursively recursively enumerable degrees (research announcement), Bull. Amer. Math. Soc. 6, 79-80.

11. W. Hodges [1993], Model Theory, Cambridge University Press, Cambridge, England.

12. W. Hodges and A. Nies [ta], Interpreting infinite linear orders, in Proceedings of Logic Colloquium ’95, J. Makowsky ed., Springer-Verlag, to appear.

13. Jockusch, Jr., C.G. and D. Posner [1978], Double jumps of minimal degrees, J. Symb. Logic 43, 715-724.

14. Jockusch, Jr., C.G. and Simpson, S. G. [1976], A degree theoretic definition of the ramified analytic hierarchy, Ann. Math. Logic 10, 1-32

15. S. Lempp, A. Nies and T. Slaman [1996], The Π_{3}-theory of the partial order of r. e. T-degrees is undecidable, Trans. Amer. Math. Soc., to appear.

16. M. Lerman [1973], Admissible ordinals and prority arguments, in Cambridge Summer School in Mathematical Logic, LNMS 37, Springer-Verlag, Berlin, 311-344.

17. M. Lerman [1983], Degrees of Unsolvability, Springer-Verlag, Berlin.

18. M. Lerman, R. A. Shore and R. I. Soare [1984], The Elementary Theory of the Recursively Enumerable Degrees is not ℵ_{0}-categorical, Adv. Math. 3, 301-320.

19. A. Nerode and R. A. Shore [1980], Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18, 61- 89.

20. A. Nies [1992], Definability and Undecidability in Recursion Theoretic Semilattices, Ph.D. Thesis, Universität Heidelberg.

21. A. Nies [1994], The last question on recursively enumerable many one degrees, Algebra i Logika 33(5), 550-563.

22. A Nies [1995], Undecidable fragments of elementary theories, Algebra Universalis 35, 8-33.

23. A. Nies [1996], On a uniformity in degree structures, in Complexity, Logic and Recursion Theory,A.Sorbi, ed., Lecture Notes in Pure and Applied Mathematics, 187, (1997), 261-276.

24. A. Nies [ta], Flexible coding of standard models of arithmetic, preprint, University of Chicago.

25. G. Odifreddi and R. A. Shore [1991], Global properties of local structures of degrees, Bul. U. Mat. Ital., 7, 97-120.

26. R. A. Shore [1981], The theory of the degrees below 0′, J. London Math. Soc (2) 24, 1-14.

27. R. A. Shore [1982], On homogeneity and definability in the Turing degrees, J. Symb. Logic 47, 8-16.

28. R. A. Shore [1982], Finitely generated codings and the degrees r. e. in a degree d, Proc. Am. Math. Soc. 84, 256-263.

29. R. A. Shore [1988], Defining jump classes in the degrees below 0′, Proc. Am. Math. Soc. 104, 287-292.

30. R. A. Shore and T. A. Slaman [1990], Working below a low recursively enumerably degree, Arch. Math. Logic 29, 201-211.

31. R. A. Shore and Slaman T. A. [1993], Working below a high recursively enumerable degree, J. Symb. Logic 58, 824-859.

32. S. G. Simpson [1977], First order theory of the degrees of recursive unsolvability, Ann. Math. (2), 105, 121-139.

33. T. A. Slaman [1991], Degree structures, in Proc. Int. Cong. Math., Kyoto 1990, Springer-Verlag, Tokyo, 303-316.

34. T. A. Slaman and H. W. Woodin [1986], Definability in the Turing degrees, Illinois J. Math. 30, 320-334.

35. R. Soare [1987], Recursively enumerable sets and degrees, Springer-Verlag, Berlin.

36. R. Soare and M. Stob [1982], Relative recursive enumerability, in Proccedings of the Herbrand Symposium: Logic Colloqium ’81, J. Stern ed., North-Holland, Amsterdam, 299-324.