Direct and local definitions of the Turing jump

Richard A. Shore^{∗} Department of Mathematics Cornell University Ithaca NY 14853

May 19, 2008

Abstract

We show that there are Π_{5} formulas in the language of the Turing degrees, D, with ≤ ,∨ and ∧, that define the relations x′′≤ y′′, x′′ = y′′ and so x ∈ L_{2}(y) = {x ≥ y|x′′ = y′′} in any jump ideal containing 0^{(ω)}. There are also Σ_{6}&Π_{6} and Π_{8} formulas that define the relations w = x′′ and w = x′, respectively, in any such ideal I. In the language with just ≤ the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Π_{2} or Σ_{2} formula in the language with just ≤ defines L_{2} or L_{2}(y). Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of I is fixed on every degree above 0′′ and every relation on I which is invariant under the double jump or under join with 0′′ is definable over I if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in I.

1 Introduction

The structure of relative computability as given by Turing reductions and the corresponding structure, D, of the Turing degrees has been the object of extensive study over the past sixty years. A central concern in this research over the past thirty years has been the issue of definability. The general question is which (interesting, apparently external) relations on D are actually definable in terms of relative computability alone. One important line of research has produced a sequence of results of the form that all relations on D which could possibly be definable, i.e. they are definable in arithmetic with quantification over both numbers and sets, are definable if restricted to “sufficiently” large degrees where sufficiently large has undergone a series of successive weakenings. The other major line of investigation into definability in D has centered on proving that specific important natural, but apparently external, degrees or relations on D are definable in D.

∗Partially supported by NSF Grant DMS-0554855.

The first major results (Jockusch and Simpson [1976]) on definability in D were in the structure with the Turing jump, ′, as well as ≤_{T}. By classical results of Kleene and Post, this operator (A ⟼ A′) corresponds to definability in arithmetic (extended by a predicate for membership in A) by formulas with only one quantifier. Its nth iterate A^{(n)} corresponds to definability by such formulas with n quantifiers. Thus, for example, A = {x|∃n ∈ ω(x ≤_{T} 0^{(n)})} are the degrees of the sets definable in arithmetic. This operator has played a major role in much of the work on D over the years and the issue of whether it is actually intrinsic to, or definable in, D was raised already in the fundamental paper of Kleene and Post [1954]. This question essentially asks if quantification in arithmetic can be expressed, level by level, solely in terms of relative computability. It became the overarching goal in the investigations of definability in D.

The first approximation to a definition of the Turing jump (or of any direct definition of a nontrivial class of degrees in D without the jump) was the definition of the hyperartihmetical degrees and the hyperjump (Harrington and Shore [1981]). It used codings of arithmetic and the calculation (Harrington and Kechris [1975]) that Kleene’s O is the base of a cone of minimal covers, i.e. ∀x ≥_{T} O∃y <_{T} x¬∃z(y <_{T} z <_{T} x). (We say that x is a minimal cover of y if y <_{T} x and there is no z with y <_{T} z <_{T} x and that x is a minimal cover if it is a minimal cover of some y.) Harrington and Shore [1981] also showed that every automorphism of D is fixed on every degree above all the hyperarithmetic ones and that every relation on such degrees (or ones invariant under joining with arbitrary hyperarithmetic degrees) that is definable in second order arithmetic is definable in D. Jockusch and Shore [1984] then introduced and analyzed the notion of pseudojumps or iterated REA operators (e.g. J_{e}(A) = A ⊕ W_{e}^{A} and then iterations of such operators into the transfinite). This analysis lead to a proof that 0^{(ω)} is the base of a cone of minimal covers and it, and the ω-jump (X^{(ω)} = {⟨x, n⟩|x ∈ X^{(n)}}), are definable in D as are all relations on degrees above the arithmetic ones (or invariant under join with these degrees) which are definable in second order arithmetic. These proofs also used codings of arithmetic but were based on one natural definition that did not: A is the downward closure of C_{ω} = {c|∀z(z ∨ c is not a minimal cover of z}.

Cooper [1990, 1993 and elsewhere] suggested an approach similar to that of Jockusch and Shore [1984] to the problem of defining the jump operator. It relied on two ingredients. The first was a version of a cone-avoiding join and completeness theorem like ones proven in Jockusch and Shore [1984] for certain types of 2-REA operators. The second was the existence of a specific such operator that would produce a degree with an order-theoretic property that no r.e. degree could have (even relative to any degree below it). This later claim turned out to be false as Shore and Slaman [2001] proved that no n-REA degree for any n < ω could have the property claimed by Cooper to hold of one 2-REA one.

The jump was then proven definable by Shore and Slaman [1999]. (Cooper later, as in [2001], made other claims for a definition along the lines of his original proposals that were either refuted or unsubstantiated. See Shore [2006] and Jockusch [2002] for more details.) Again the ingredients were a new cone-avoiding join and completeness theorem but now for all n-REA operators and a specific 2-REA one with the required properties. A remarkable feature of the proof was the specific operator used and the proof that it was definable in D. The operator was the double jump and the proof of its definability followed from much earlier work of Slaman and Woodin. Although not included in the announcement of their work in Slaman [1991], their metamathematical arguments that gave many other results such as the definability of all relations on degrees above 0′′ that are definable in second order arithmetic and that all such degrees are fixed under every automorphism of D, also proved that the double jump was definable in D. The definition requires their entire machinery to internalize their analysis of automorphisms of D within D itself. It relies on set theoretic forcing to collapse the continuum and absoluteness arguments to capture full automorphisms of D by countable approximations that can then be defined within the structure. The full proof appears in Slaman and Woodin [2008]. The join theorem for n-REA operators of Shore and Slaman [1999] then defines the Turing jump from that of the double jump: For any degree x, x′ = max{z ≥_{T} x|(∀g ≥_{T} x)(z ∨ g ≠ g′′)}, i.e. x′ is the greatest degree z such that there is no g greater than or equal to x such that z ∨ g is equal to g′′.

Our goal in this paper is to give a direct definition of the jump operator that uses no metamathematical or set theoretic methods such as absoluteness or forcing over models of (large fragments of) ZFC. We also avoid coding models of arithmetic and using definability in them on the road to our definition. We do begin with the definition given above of A from Jockusch and Shore [1984] and at the end apply the definition above of the jump from the double jump of Shore and Slaman [1999]. In between, we define another class C (and its upward closure C̃) that is a version of a generalization of classes from the familiar generalized high/low hierarchy: C = {x|(∀k)(x^{(3)} ≰ (x ∨ 0^{(k)})^{(2)}} (Definitions 2.5 and 2.6). This class is defined within D by an analysis of the finitely generated partial lattices of a specified form that can be embedded below a degree x. (These lattices are ones whose complexity we can limit and control. They were first introduced and exploited for the analysis of the degrees below 0′ in Shore [1981].) The crucial additional ingredient from the literature is Slaman and Woodin’s [1986] coding of countable sets of pairwise incomparable degrees by finitely many parameters. We also need two new technical lemmas. One, Theorem 4.1, embeds certain Σ_{3}^{X} partial lattices below any ANR degree x. (A degree a is ANR if, for any function f ≤_{wtt} 0′, there is a g ≤_{T} a such that there are infinitely many n with g(n) > f(n).) The other, Theorem 5.1, calculates the infimum of the double jumps of degrees in C that are above any given x to be x′′. Together these allow us to go from a definition of C (or C̃) to one of the double jump and thence to one of the jump.

In addition to avoiding the set theoretic and metamathematical techniques of Slaman and Woodin, our approach provides definitions that define the double jump and jump inside any jump ideal of D that contains 0^{(ω)} (Theorem 6.1). (A jump ideal is a subset of D closed downward and under join and jump.) Because of the global nature of the arguments of Slaman and Woodin [2008], their methods give no hint as to how to define these operators in small substructures of D. Even within all of D, our definitions seem significantly simpler both conceptually and in terms of quantifier complexity. (We give specific quantifier complexity bounds for our definitions in Theorems 6.2 and 6.15. In the language with ∨ and ∧, L_{2}(y) = {x ≥ y|x′′ = y′′} has a Π_{5} definition as do x′′≤ y′′and x′′ = y′′ in any jump ideal containing 0^{(ω)}. There are ones for w = x′′ and w = x′ that are Σ_{6}&Π_{6} and Π_{8}, respectively. In the language without ∨ and ∧ the definitions are one level higher up.) As a beginning of the investigation of lower bounds for the complexity of such definitions, we show in Proposition 7.6 that there is no definition of L_{2} or L_{2}(y) which is either Π_{2} or Σ_{2} in the language with just ≤.

Once we have an independent definition of the (double) jump we can also directly and simply derive the results of Slaman and Woodin [2008] on fixed points of automorphisms and definability (Theorem 2.10) and extend them to all jump ideals containing 0^{(ω)}: If I is any jump ideal with 0^{(ω)} ∈ I and φ is any automorphism of I then φ(x) = x for every x ≥ 0′′. Moreover, any relation on I invariant under the double jump or under joining with 0′′ is definable over I if and only if it is definable in the structure of second order arithmetic with set quantification ranging over sets with degrees in I. Thus our approach presents the general results on fixed points and definability for sufficiently large degrees as direct consequences of a proof of the definability of natural classes and the jump operator.

In the next section, we make explicit the few properties of our coding/embedding results that are needed and present an overview of our proof that relies only on those properties. Section 3 is devoted to making these notions explicit. In §4 we provide the technical result needed about embedding partial lattices below ANR degrees. Section 5 contains the proof that the infimum of the double jumps of degrees y ∈C or C̃ with y ≥ x is x′′. Section 6 further analyses all the previous constructions to see that we have definitions that work in any jump ideal containing 0^{(ω)} and calculates the quantifier complexity of these definitions. The final section suggests some open questions as well as indicating possible routes to partial progress on some of them.

2 Overview of the Proof

In this section we will give an overview of a general plan to define the jump operator from classes C of degrees and the properties required of C to be able to carry out this plan. Our penultimate goal is to define the relation x′′ ≤ y′′ from C. Let L_{2}(x) = {y ≥ x|y′′ ≤ x′′}. By Selman [1972], x′′ = ∨L_{2}(x) and indeed there are y_{1}, y_{2} ∈ L_{2}(x) such that y_{1}∨y_{2}= x′′. Thus a definition of the relation x′′ ≤ y′′ and so of x ∈ L_{2}(y) would suffice to define the double jump operator from C. We then appeal to the direct definition of the jump from the double jump (Slaman and Shore [1999]): x′ = max{z ≥_{T} x|(∀g ≥_{T} x)(z ∨ g ≠ g′′)}.

In fact, what is shown there is that if w ≰ x′ then there is a g ≥ x such that w ∨ z = g′′. Thus x′ = max{z ≥_{T} x|(∀g ≥_{T} x)(z ∨ g ≱ g′′)} as obviously z ∨ g ≱ g′′ for any z ≤ x′ and g ≥ x.

To begin, we note that x′′ is determined by the collection of sets Δ_{3}^{X} which is, of course, independent of the choice of X ∈ x. We thus want to provide a definable (in C) coding procedure (with free variable x and additional parameters) that (as the parameters vary) codes precisely the sets Δ_{3}^{X}. Given such a coding procedure, we then want to have a definable comparison relation (with free variables just x and y) which allows us to say that the sets coded by the specified procedure with x as the special parameter are also coded with y as the special parameter. This will then say that Δ_{3}^{X} ⊆ Δ_{3}^{Y} and so x′′ ≤ y′′ as desired.

There are two main tools needed to carry out this plan. The first is the coding of sets in effective successor models of ℕ introduced in Shore [1981] with the use of initial segments to analyze the theory of the degrees below 0′. Variations of this coding mechanism have since been used in a number of other settings and especially in Nies, Shore and Slaman [1998]. In each one, the crucial idea is to make the procedure used to recover the coded set from the parameters as simple as possible: positively Σ_{1} in the ordering relation and join operator on the degrees involved. By positively we mean that ≤, = and ∨ can be used but not ≰ or ≠ (or ∧) so that, in the setting of the Turing degrees below x, the set coded must be Σ_{3}^{X} as ≤_{T} restricted to the (indices of) degrees below x is itself Σ_{3}^{X} and join operates recursively on the indices. The previous version of this coding procedure most closely resembling the one we use in this paper is that used in Shore [2008] to prove the rigidity of the hyperdegrees and their biinterpretability with true second order arithmetic. We spell out the precise procedure we need that defines our notion of a set S being coded below a degree x in §3. For now, all we need to know is that any set S coded (by parameters) below x is Σ_{3}^{X}. Thus, if both S and its complement, S̄, are coded below x, then S ∈ Δ_{3}^{X}, i.e. S ≤_{T} x′′.

The second tool that we need is the method of coding countable sets and relations on D by finitely many parameters uniformly definably as given by Slaman and Woodin [1986]. (The uniformity here means that there is, for each n, a single formula ϕ(x_{1}, …, x_{n}, p⃗) such that, as the parameters p⃗ vary, the formula defines all countable n-ary relations on D.) Given such a way of coding arbitrary countable relations on D and so quantifying over them, it is clear that, in principle, we will be able to define the needed comparison relations between parameters below x and ones below y that say that they code the same set. The details are again provided in §3. In particular, as Slaman and Woodin describe in general, and we will illustrate in the detailed analysis of our specific case, one really needs only the simplest instance of their results, the coding of countable sets of pairwise incomparable degrees.

Given these two ingredients of (effective) coding and comparison, our plan is to (definably in C) capture Δ_{3}^{X} as follows:

Δ_{3}^{X} = S(x) ≡{S|S and S̄ are coded below every z ∈ C with x ≤_{T} z}.

In order for this description to actually capture the sets Δ_{3}^{X}, we want the class C to have two properties:

• Property 1: x ∈ C ⇒ Every S ∈ Δ_{3}^{X} is coded below x.

• Property 2: ∀x(∧{z′′|z ∈ C & x ≤_{T} z} = x′′).

Property 1 insures that Δ_{3}^{X} ⊆ S(x). In our applications we will typically show that every S ∈ Σ_{3}^{X} is coded below x. On the other hand, as any set S such that S and S̄ are coded below every z ∈ C with x ≤_{T} z is Δ_{3}^{Z} for every such Z, Property 2 guarantees that S ≤_{T} x′′. Thus S(x) ⊆ Δ_{3}^{X} and we have that Δ_{3}^{X} = S(x) as required.

Remark 2.1. Note that Property 1 is obviously closed downward, i.e. if C ⊇ B and C has Property 1 then so does B. Similarly, Property 2 is closed upward.

We now describe some well known degree classes that have one or the other of these Properties. The first is ANR, the array nonrecursive degrees first introduced and studied in the setting of D by Downey, Jockusch and Stob [1990]: a ∈ ANR ⇔ no f ≤_{wtt} 0′ dominates every g ≤_{T} A, i.e. if a function f is wtt reducible to 0′ then there is a function g recursive in a such that there are infinitely many n with g(n) > f(n). In §4, we prove the following:

Theorem 2.2. ANR has Property 1. In fact, every S ∈ Σ_{3}^{X} is coded below x for every x ∈ ANR.

As our final definable classes C and C̃ will be contained in ANR, they too will have this Property. Similarly, any other class contained in ANR such as \overline{GL}_{2} has Property 1 as well. (Recall that a ∈\overline{GL}_{2} ⇔ a′′ ≠ (a ∨ 0′)′ ⇔ a′′ > (a ∨ 0′)′. By Downey, Jockusch and Stob [1990], \overline{GL}_{2} ⊆ ANR.)

As an initial attempt at the other direction of our plan to capture the sets Δ_{3}^{X}, we show that many familiar degree classes have Property 2.

Theorem 2.3. GH_{3} = {x|x^{(3)} = (x ∨ 0′)^{(3)}} = {x|x^{(3)} ≥ (x ∨ 0′)^{(3)}} has Property 2.

Proof. Consider any degree x. By Lachlan [1966] there is a minimal pair c_{0} and c_{1} of high r.e. degrees relative to x′′, i.e. c_{0} ∧ c_{1} = x′′, c′_{i} = x^{(4)} and the c_{i} are REA in (recursively enumerable in and above) x′′. Apply the Sacks jump inversion theorem (Sacks [1963]) twice to c_{i} to get y_{i} REA in x with y′′_{i} = c_{i}. Thus y′′_{0} ∧ y′′_{1} = x′′ as required for Property 2.

To see that y_{i}∈ GH_{3} note that y′′′_{i} = c′_{i} = x^{(4)}. As y_{i} is REA in x, y_{i}∨0′ ≤_{T} x′ and so (y_{i}∨0′)′′′ ≤_{T} x^{(4)} = y′′′_{i} as required.

Thus the Turing jump is directly definable from every jump class from GL_{2} to GH_{3} as well as from ANR. However, it is an open question if there are natural or even simple direct definitions (not using a definition of the Turing jump) of any of these jump classes or any definition at all of ANR. We want a class that is directly definable and also has Properties 1 and 2. Our desired classes C and C̃ were suggested by the following argument that directly defines the jump operator from a single instance.

Proposition 2.4. The jump operator can be directly defined from the single degree 0′.

Proof. We define \overline{GL}_{3} from 0′ and apply the previous results. We claim that x ∈\overline{GL}_{3} ⇔ (∃S)(S is coded below x but not both S and S̄ are coded below x ∨ 0′}.

For one direction, note that if x ∈\overline{GL}_{3}, S = x^{(3)} is coded below x by Theorem 2.2 but if S and S̄ are coded below x ∨ 0′ then S = x^{(3)} ≤_{T} (x ∨ 0′)′′ for a contradiction. For the other containment, consider any S coded below x. By the effectiveness of our coding apparatus, S ∈ Σ_{3}^{X}. If not both S and S̄ are coded below x ∨ 0′ then S ∉ Δ_{3}^{X∨0′} as every set Σ_{3}^{X∨0′} is coded below x ∨ 0′ by Theorem 2.2 since 0′ ∈ ANR and ANR is closed upward. (Both of these facts are immediate from the definition of ANR.)

Now we do not have a direct definition of even the single degree 0′ but we do have a natural definition of the arithmetic degrees and we can use them instead to define a more generalized jump class C that will still have Properties 1 and 2. The membership of a degree x in the standard (generalized) jump classes GL_{n} and GH_{n} is defined by the lowness or highness, respectively, of the n^{th} jump relative to the appropriate jump of x ∨ 0′. If we replace 0′ by 0^{(k)} we get a more generalized notion.

Definition 2.5. GL_{n,k} = {x|x^{(n)} ≤ (x ∨ 0^{(k)})^{(n−1)}}. GH_{n,k} = {x|x^{(n)} ≥ (x ∨ 0^{(k)})^{(n)}}.

Of course, GL_{n} = GL_{n,1} and GH_{n,1} = GH_{n}. The first class we want is the complement of the union of the GL_{3,k}.

Definition 2.6. C = {x|(∀k)(x^{(3)} ≰ (x ∨ 0^{(k)})^{(2)}}. C̃ is the upward closure of C, i.e. C̃ = {x|(∃z ∈ C)(x ≥ z)}.

By considering just the case that k = 1 in the definition of C it is clear that C ⊆ \overline{GL}_{3} and so C ⊆ ANR and has Property 1. As ANR is closed upward it also contains C̃. We prove in §5 that both C and C̃ have Property 2. Thus the Turing jump is definable from C or C̃. On one hand, the definition of C seems to be simpler than that of C̃. On the other hand, the definition in terms of C̃ will work in any jump ideal containing 0^{(ω)} while that using C requires closure under the ω-jump.

To get our direct definition of the jump operator we need to give one of C. We do so in terms of the class C_{ω} = {x|(∀z)(z ∨ x is not a minimal cover of z}. (We say that m is a minimal cover of z if m < z and there is no degree strictly between m and z.) Jockusch and Soare [1970] show that 0^{(n)} ∈ C_{ω} for every n while Jockusch and Shore [1984] prove that C_{ω} ⊆ A = {x|∃n(x ≤ 0^{(n)})}. (So Jockusch and Shore [1984] provide a natural definition of A, the degrees of the arithmetic sets, as the downward closure of C_{ω}.) We use C_{ω} and our coding and comparison procedures to give a direct definition of C and so of C̃ as well.

Theorem 2.7. C = {x|(∃S)(S is coded below x but not both S and S̄ are coded below x ∨ z for any z ∈ C_{ω}}.

Proof. For one direction suppose x ∈ C. Thus in particular x ∈\overline{GL}_{3} ⊆ ANR and so by Theorem 2.2 the set S = X^{(3)} is coded below x. If S and S̄ were both coded below some x ∨ z with z ∈ C_{ω}, then by taking n such that z ≤ 0^{(n)} we see that both are coded below x ∨ 0^{(n)} and so both are Σ_{3}^{X∨0^{(n)}}, i.e. X^{(3)} ∈ Δ_{3}^{X∨0^{(n)}} contrary to the definition of C.

For the other direction, suppose we have an S coded below x such that not both S and S̄ are coded below x ∨ z for any z ∈ C_{ω}. As 0^{(n)} ∈ C for every n, they are not both coded below x ∨ 0^{(n)} for any n. As each of these degrees is in ANR (by being above 0′), the sets T such that both T and T̄ are coded below them are (by Theorem 2.2 and the effectiveness of our coding) precisely the sets Δ_{3}^{X∨0^{(n)}} for some n. Thus S = X^{(3)} is not Δ_{3}^{X∨0^{(n)}} for any n, i.e. (∀n)(x^{(3)} ≰ (x ∨ 0^{(n)})^{(2)} as required.

To summarize our discussion so far, we give the crucial definitions in terms of our as yet unspecified but definable coding and comparison procedures.

Theorem 2.8. x′′ ≤ y′′ ⇔ every set S coded below every z such that x ≤ z and z ∈ C is coded below every w such that y ≤ w and w ∈C. Of course, x′′ = y′′ ⇔ x′′ ≤ y′′ & y′′ ≤ x′′. And so we have our direct definition of the jump: x′ = w ⇔ w = max{z ≥_{T} x|(∀g ≥_{T} x)(z ∨ g ≱ g′′)}.

The formal versions of these definitions are given in Theorem 3.6. We will also see in §6 that a finer analysis using C̃ in place of C provides local version of this theorem, i.e. a single formula ϕ(x, w) such that for any jump ideal I (i.e. I is a subset of D closed downward and under jump and join) that contains the degree 0^{(ω)}, ϕ defines the jump operator.

Theorem 2.9. If I is any jump ideal with 0^{(ω)} ∈ I and x, y ∈ I then x′′ ≤ y′′ if and only if I satisfies the formula of degree theory expressing, as above, that every set S coded below z for every z ∈ C̃ with z ≥ x is coded below w for every w ∈ C̃ with w ≥ y. Thus for x, w∈ I, x′ = w ⇔ I ⊧ w = max{z ≥_{T} x|(∀g ≥_{T} x)(z ∨ g ≱ g′′)} where we understand the double jump relation to be defined as just specified.

The rest of the paper is devoted to the explication and proofs of the required notions and theorems. We close this section by noting that the local definition of the jump operator allows us to prove local results about automorphisms of jump ideals containing 0^{(ω)} and definability in such ideals.

Theorem 2.10. If I is any jump ideal with 0^{(ω)} ∈ I and φ is any automorphism of I then φ(x) = x for every x ≥ 0′′. Moreover, any relation on I invariant under the double jump or under joining with 0′′ is definable over I if and only if it is definable in the structure of second order arithmetic with set quantification ranging over sets with degrees in I.

Proof. These consequences are pretty standard once one has the information about automorphisms being fixed on the jump or even on particular instances. The ideas go back to Jockusch and Solovay [1977] who show that all degrees above 0^{(4)} are fixed under all automorphisms of D that preserve the jump operator. Transferring such fixed point theorems to definability ones have roots at least as far back as Simpson [1977]. Since these proofs, there have been many versions and improvements along with various new methods of coding. In our setting, for the first claim about fixed points, we can simply point out that if x ≥ 0′′ then x is uniquely determined as the degree z above 0′′ such that there is a w ≤ z with w′′ = z with X, X̄ coded below w and such that every set S with S and S̄ coded below any y with y′′ = z is recursive in X.

The first condition guarantees that z = w′′ ≥ x for this w. It is satisfied by x because there is an ANR degree w with w′′ = x. (We can easily construct such a degree directly or appeal to Downey, Jockusch and Stob [1990] who show that there is a low degree in ANR and relativize this to a degree with double jump x.)

The second condition then guarantees that z ≤ x as W′′ and \overline{W′′} are coded below a degree which is ANR and low relative to a w with w′′ = z.

For the second claim about definability, we note that, as usual, using the coding of Slaman and Woodin [1986] we can, in I, definably pick out standard models of arithmetic and quantify over all subsets with degrees in I. (The point to make here is that, as Slaman and Woodin [1986] show, their coding for a set X in such a model is done well within the jump ideal containing x. In the other direction, any reasonably effective procedure for coding sets in models of arithmetic by their methods codes only sets arithmetic in the parameters used. So within I, only sets with degrees in I are coded and all such are, in fact, coded.) The comparison machinery discussed above then allows us to definably move from a set X ≥_{T} 0′′ coded in such a model to the degree x ≥ 0′′ satisfying the property described in the first paragraph of this proof for the specified X. Given such a map between coded sets and their degrees, we can translate any property definable in second order arithmetic with set quantification over the sets with degrees in I which is invariant under double jump or joining with 0′′ to one definable in I.

3 Coding and Comparison

Our effective coding of a set S is given by an embedding of a particular partial lattice with 0 in D. (A partial lattice is a partial ordering on which the operations ∨ and ∧ may be only partial but, when defined, they obey the usual definitions in terms of the ordering.) The crucial backbone of the partial lattices we want to consider is an ωsequence of pairwise incomparable elements d_{n} generated by five elements d_{0}, e_{0}, e_{1}, f_{0} and f_{1} satisfying the the following recursion relations for n ≥ 0:

(∗) (d_{2n} ∨ e_{0}) ∧ f_{1} = d_{2n+1} and

(∗∗) (d_{2n+1} ∨ e_{1}) ∧ f_{0} = d_{2n+2}.

These conditions clearly guarantee that we can enumerate the d_{n} recursively in the lattice structure and write a recursive list of quantifier free formulas in this language which define each of them. Following Shore [2008], we wish to convert this procedure and these formulas into ones that are positive in the language with just ≤ and ∨ at least to the extent that we can use them to code S (with the aid of other parameters g_{0} and g_{1}). One crucial ingredient is being able to say that the (indices generated as candidates for being some) d_{n} are strictly above 0. We do this by adding two other parameters p and q and require of our lattice that p ≱ q and p ∨ d_{n} ≥ q for each n. We can now recursively generate positive existential formulas ϕ_{n}(x) using just ≤ , ∨ and parameters for the named elements such that, in any lattice L_{X} with elements d_{0}, e_{0}, e_{1,}f_{0}, f_{1}, p and q as described, ϕ_{n}(x) holds of x if and only 0 < x ≤ d_{n} and the same will be true in D of any degree x when the parameters are interpreted as their images under any (partial) lattice embedding of L into D:

We begin with x = d_{0} as ϕ_{0}. Recursively, we let ϕ_{2n+1}(x) be ∃z(ϕ_{2n}(z) & x ≤ z ∨e_{0}, f_{1} & q ≤ x∨p) and ϕ_{2n+2}(x) be ∃z(ϕ_{2n+1}(z) & x ≤ z ∨e_{1}, f_{0} & q ≤ x∨p). Consider any x such that ϕ_{2n+1}(x) holds. We then have a z as described such that, by induction, 0 < z ≤ d_{2n}. Thus z ∨ e_{0} ≤ d_{2n} ∨ e_{0} and so x ≤ d_{2n} ∨ e_{0}, f_{1}. As d_{2n+1} = (d_{2n} ∨ e_{0}) ∧ f_{1}, x ≤ d_{2n+1} as required. Of course, q ≤ x ∨ p guarantees that x > 0 as well. The argument for ϕ_{2n+2} is essentially the same.

We will use exact pairs for ideals to code our given set S as in Shore [1981]. The idea is to have g_{0} and g_{1} such that S = {n|d_{n} ≤ g_{0}, g_{1}} as opposed to simply upper bounds on the d_{n} with n ∈ S and the d_{n} with n ∉ S as in Shore [2008]. (Recall that g_{0} and g_{1} form an exact pair for the ideal generated by the degrees d_{n} for n ∈ S if x ≤ g_{0}, g_{1} ⇔ x ≤ d_{i_{0}} ∨ ⋯ ∨ d_{i_{m}} for some d_{i_{0}}, … d_{i_{m}} with i_{0}, …, i_{m} ∈ S.) The reason for this choice is to keep the ability to make S, and not S̄, positively Σ_{1} in the ordering and join. The next point is, as we will only generate (indices for) elements x ∈ (0, d_{n}) that are below both g_{0} and g_{1}, we need to make sure that if we have such an x it can only be associated with a single d_{n}. We thus wish to ensure that if there is a nonzero x below some d_{n}, g_{0} and g_{1} then d_{n} is itself below g_{0} and g_{1}. This suggests that we also require of our lattice that, for n ≠ m, d_{n} ∧ d_{m} = 0. Because, however, we are only determining the ideal generated by the d_{n} with n ∈ S by our codes g_{0} and g_{1}, we must also guarantee that no nonzero x ≤ d_{m} with m ∉ S is in this ideal. The easiest way to guarantee this in general is to assure that the d_{n} form an independent set by, for example, requiring that there be an element d̃_{n} of our lattice that is above all d_{m} for m ≠ n such that d_{n} ∧ d̃_{n} = 0. (This then also implies the previous requirement that the d_{n} pairwise inf to 0 as well as the basic desideratum that ∃x(0 < x ≤ d_{n}, g_{0}, g_{1}) → d_{n} ≤ g_{0}, g_{1}.)

If we have a partial lattice L with all these properties and an embedding of the lattice into the degrees below x it is not hard to see that the set S = {n|d_{n} ≤ g_{0}, g_{1}} coded by this lattice or, as we shall say by the degrees d_{0}, e_{0}, e_{1}, f_{0}, f_{1}, p, q, g_{0}, g_{1} below x which are the images of the corresponding elements of L, is Σ_{3}^{X}: n ∈ S ⇔ ∃x(ϕ_{n}(x) & x ≤ g_{0}, g_{1}). (We boldface the variables and formulas to indicate that we are interpreting them in D about the images of elements of L.) As the formulas ϕ_{n} are all positive Σ_{1} formulas in ≤ and ∨ which are Σ_{3}^{X} on the indices for sets recursive in X, the claimed equivalent definition of S is clearly Σ_{3}^{X}. As ϕ_{n}(d_{n}) holds, the claimed equivalent definition holds for every n ∈ S. For the other direction we rely on the prescribed properties of L. We already know that if ϕ_{n}(x) holds then 0 < x ≤ d_{n}. Our assumptions then imply that d_{n} ≤ g_{0}, g_{1} as required. In fact, as the g_{0} and g_{1} form an exact pair for the ideal generated by the d_{n} with n ∈ S, if x ≤ d_{n}, g_{0}, g_{1} and n ∉ S, then x = 0. The point here is that x ≤ d_{i_{0}} ∨ ⋯ ∨ d_{i_{m}} with i_{0}, …, i_{m} ∈ S and so x ≤ d_{i_{0}} ∨ ⋯ ∨ d_{i_{m}} ≤ d̃_{n} while d_{n} ∧ d̃_{n} = 0. The crucial property needed here is that if ∃x(0 < x ≤ d_{n}, g_{0}, g_{1}) then d_{n}≤ g_{0}, g_{1}. Thus, for an exact pair g_{0}, g_{1} for the ideal generated by d_{n} for n ∈ S, S = {n|∃x(ϕ_{n}(x) & x ≤ g_{0}, g_{1})}.

We note that any sequence of degrees d_{0}, e_{0}, e_{1}, f_{0}, f_{1}, p, q, g_{0}, g_{1} ≤ x can be viewed as coding the set S = {n|∃x(ϕ_{n}(x) & x ≤ g_{0}, g_{1})} which is always Σ_{3}^{X}. When we want to claim that (for certain degrees x) every Σ_{3}^{X} set is coded by such a sequence, we have to guarantee all these properties of the required (embedding of) L. We do this in Theorem 4.1 for x ∈ ANR. What remains for us to do now is to explain how we can assert, in a first order way in D, that two such sequences code the same set or complementary sets. For this we need to guarantee some of the structural properties of L already discussed as well as a comparison procedure. The crucial ingredient is the coding of Slaman and Woodin [1986]:

Theorem 3.1. (Slaman and Woodin [1986]): For any set {c_{n}} of pairwise incomparable degrees uniformly recursive in u there are degrees h_{0} and h_{1} below u′′ such that y ∈ {c_{n}} ⇔ y ≤ u & ∃w(w ≤ h_{0}∨y, h_{1}∨y & w ≰ y) & (∀u < y)¬∃w(w ≤ h_{0}∨u, h_{1}∨ u & w ≰ u). We will denote this relation by y ∈Kd(u, h_{0}, h_{1}) and the set of such y by Kd(u, h_{0}, h_{1}).

Notation 3.2. For notational convenience we will use a to stand for the sequence d_{0}, e_{0}, e_{1}, f_{0}, f_{1}, p, q, g_{0}, g_{1} (to code one set) and decorated variants such as â for the correspondingly decorated sequence. We thus write, for example, a ≤ x to mean d_{0}, e_{0}, e_{1}, f_{0}, f_{1}, p, q, g_{0}, g_{1} ≤ x. We use b and its decorated variants to stand for an additional pair of degrees g_{2}, g_{3} which we add on to a to code a second set in the obvious way. We use c and its variants to stand for sequences of the form u, h_{0}, h_{1} as used in Theorem 3.1 and so, for example, write y ∈Kd(c) for y ∈Kd(u, h_{0}, h_{1}).

We now give the formal definition in D of various degrees coding a set below x. For ease of reading (to the extent possible) we expand our language by adding on the definable (partial) operations ∨ and ∧ as well as a constant symbol for 0. Our intention is that whenever a term of the form x ∧ y occurs we intend to assert the existence of an infimum for x and y. The formal version for the sentences that we use will be made precise near the end of §6 where we explain how to eliminate these symbols.

Definition 3.3. Two sequences of degrees a and c code a set below x if the following conditions hold:

1. a ≤ x.

2. q ≰ p.

3. d_{0} ∈ Kd(c).

4. ∀d(d ∈Kd(c) → (d ∨ e_{0}) ∧ f_{1} ∈ Kd(c) & (d ∨ e_{1}) ∧ f_{0} ∈ Kd(c)).

5. ∀d, d̂(d ≠ d̂ & d, d̂ ∈Kd(c) → d ∧ d̂ = 0 & q ≤ d ∨ p & ∃x(0 < x ≤ d, g_{0}, g_{1}) → d ≤ g_{0}, g_{1}).

We denote the conjunction of these properties by Cd(x, a, c) and, if we omit (1) and so x, by Cd(a, c) . We then say that the set S coded by the degrees a and c is {n|d_{n} ≤ g_{0}, g_{1}} where the d_{n} are defined by the recursions (∗) and (∗∗) at the beginning of this section. Similarly, we use Cd(x, a, b, c) to say that, in addition to Cd(x, a, c) we have coded a second set S′ = {n|d_{n} ≤ g_{2}, g_{3}} with the additional parameters g_{2}, g_{3}. As written, this definition only guarantees that each d_{n} ∈ Kd(c). We can require that the set Kd(c) consists precisely of the d_{n} which we designate as P rCd by adding on the condition

6 Kd(c) is the smallest set satisfying (3) and (4), i.e. ∀ĉ([d_{0} ∈ Kd(ĉ) & ∀d(d ∈Kd(ĉ) → (d ∨ e_{0})∧f_{1} ∈ Kd(ĉ) & (d ∨ e_{1})∧f_{0} ∈ Kd(ĉ))] → ∀d(d ∈Kd(c) → d ∈Kd(ĉ))).

It may be easier to see that our definitions have the desired properties with the precise coding clause but it will not be really necessary to include it. Even without it, we have specified enough properties of the partial lattice involving a to guarantee that S = {n|∃x(ϕ_{n}(x) & x ≤ g_{0}, g_{1})} and so S is Σ_{3}^{X} (and so also for S′). We can then guarantee that S̄ = S′ by saying, in addition to Cd(x, a, b, c), that (∀d ∈Kd(c))(d ≤ g_{0}, g_{1} ↔ d ≰g_{2}, g_{3}). We denote this relation by Compl(x, a, b, c). To compare the sets S and S̃ coded by a, c and ã, c̃, respectively, we need to know a bit more about Slaman-Woodin coding.

Given any two sets such as {d_{n}} and {d̃_{n}} each consisting of pairwise incomparable degrees with Kd(c) = {d_{n}} and Kd(c̃) = {d̃_{n}} there are č, ċ, c̈ and ĉ such that, for any z ∈Kd(c) and z̃ ∈Kd(c̃), (∃w, w̃ ∈Kd(č))(z ∨ w ∈Kd(ċ) & z̃ ∨ w̃ ∈Kd(c̈) & (z ∨ w ∨ z̃ ∨ w̃) ∈Kd(ĉ)) ↔ (∃n)(z = d_{n} & z̃ = d̃_{n}). As pointed out in Slaman and Woodin [1986], one can see this directly from Theorem 3.1 by taking a set h_{i} of mutually 1-generic degrees relative to any degree above all the d_{n} and d̃_{n} and let č code {h_{i}}. Next let ċ code the set {d_{n} ∨ h_{2n}} of pairwise incomparable degrees and c̈ code {d̃_{n} ∨ h_{2n+1}}. Finally let ĉ code {d_{n} ∨ h_{2n} ∨ d̃_{n} ∨ h_{2n+1}} which is also pairwise incomparable. We abbreviate (∃w, w̃ ∈Kd(č))(z ∨ w ∈Kd(ċ) & z̃ ∨ w̃ ∈Kd(c̈) & (z ∨ w ∨ z̃ ∨ w̃) ∈Kd(ĉ)) as Mp(č, ċ, c̈, ĉ, z, z̃). We can now definably say that the sets S and S̃ coded by a, c and ã, c̃, respectively, are the same.

Proposition 3.4. If a, c and ã, c̃ code the sets S and S̃, respectively, then S = S̃ if and only if (∃č, ċ, c̈, ĉ)[(∀x, y, z)(Mp(č, ċ, c̈, ĉ, x, y) &Mp(č, ċ, c̈, ĉ, x, z) → y = z) & Mp(č, ċ, c̈, ĉ, d_{0}, d̃_{0}) & (∀d ∈Kd(c))(∀d̃ ∈Kd(c̃))(Mp(č, ċ, c̈, ĉ, d, d̃) → Mp(č, ċ, c̈, ĉ, (d∨ e_{0})∧f_{1}, (d̃∨ẽ_{0})∧f̃_{1}) & Mp(č, ċ, c̈, ĉ, (d∨e_{1})∧f_{0}, (d̃∨ẽ_{1})∧f̃_{0}) & (d ≤ g_{0}, g_{1} ↔ d̃ ≤ g̃_{0}, g̃_{1})]. We denote this relation by Eq(a, c, ã, c̃).

Proof. The formula given says that Mp defines a one-one relation that takes d_{0} to d̃_{0} and, by induction, d_{n} to d̃_{n}. It then guarantees that d_{n}≤ g_{0}, g_{1}, i.e. n ∈ S, if and only if d̃_{n}≤ g̃_{0}, g̃_{1}, i.e. n ∈ S̃. (Note that for d = d_{n} one of (d ∨ e_{0}) ∧ f_{1} and (d ∨ e_{1}) ∧ f_{0} is d_{n+1} and the other is d_{n}.) We also point out that even without the added condition for precisely coding sets, this relation has the correct meaning since if S = S̃ we can choose the parameters to define Mp only on the degrees d_{n}.

We now have our formal version of the definition of C in D given in Theorem 2.7. In our current style of abbreviations we use z ∈ C_{ω} to abbreviate the formula ∀z(z ≤ x or ∃w(x < w < x ∨ z).

Theorem 3.5. C = {x|∃a, c(Cd(x, a, c) & (∀ã, b̃, c̃, z)(z ∈ C_{ω} & Compl(x ∨ z, ã, b̃, c̃) → ¬Eq(a, c, ã, c̃))}.

Using the notation x ∈ C in the obvious way, we now have our formal analog of the definition of x′′ ≤ y′′ given in Theorem 2.8 and so of jump operation.

Theorem 3.6. 1. x′′ ≤ y′′ ⇔ (∀a, c)[Cd(a, c) & (∀z)(z ∈ C & x ≤ z →

(∃ã, c̃)(Cd(z, ã, c̃) & Eq(a, c, ã, c̃)) → (∀w)(w ∈C & y ≤ w →

(∃â, ĉ)(Cd(w,â, ĉ) & Eq(a, c, â, ĉ))].

2. x′ = w ⇔ w = max{z ≥_{T}x|(∀g ≥_{T}x)(z ∨ g ≱ g′′) ⇔ ∀g(g ≥ x → (w ∨ g) ≠ g′′) & ∀v(∀g(g ≥ x → (v ∨ g) ≠ g′′→ v ≤ w).

To see that these definitions have the intended meaning, we must prove Theorems 2.2 and 5.1. After we prove these theorems we will be able to see in §6 (Theorem 6.1) that the same definitions using C̃ in place of C have their intended meaning in every jump ideal containing 0^{(ω)}:

Theorem 3.7. The equivalences for x′′ ≤ y′′ and x′ = w given in Theorem 3.6 are valid in every jump ideal containing 0^{(ω)} if we replace C by C̃.

4 Coding Below an ANR Degree

In this section we prove that ANR and so C and C̃ have Property 1. There is clearly a recursive (partial) lattice L with the properties described in §3: There are elements d_{0}, e_{0}, e_{1}, f_{0} and f_{1} that generate a ω-sequence of pairwise incomparable elements d_{n} by the recursion formulas (∗) and (∗∗) of §3. There are elements p ≱ q such that p ∨ d_{n} ≥ q for each n. For every d_{n} there is an element d̃_{n} such that d̃_{n} ≥ d_{m} for m ≠ n and d_{n} ∧ d̃_{n} = 0. Let us fix such a (partial) lattice L. Given any x ∈ ANR and any S ∈ Σ_{3}^{X} it clearly suffices to embed L in the degrees below x and to simultaneously construct degrees g_{0}, g_{1} ≤_{T} x such that g_{0} and g_{1} are a minimal pair for the ideal generated by {d_{n}|n ∈ S}. We prove a more general result.

Theorem 4.1. If L is a recursive (partial) lattice with a recursive list d_{i} of elements forming an independent set (no join of a finite subset is above any one not in the given finite set), X ∈ x ∈ ANR and S is Σ_{3}^{X}, then there is an embedding of L into the degrees below x (taking d_{i} to d_{i}) and degrees g_{0}, g_{1} ≤_{T} x such that g_{0} and g_{1} are a minimal pair for the ideal generated by {d_{n}|n ∈ S}. Indeed, given another S̃ ∈ Σ_{3}^{X} we can also simultaneously get g_{2}, g_{2} ≤_{T} x that form a minimal pair for the ideal generated by {d_{n}|n ∈ S̃}.

The basis for our construction is the method of embedding (partial) lattices in D by Cohen type forcing (i.e. finite conditions) introduced in Shore [1982]. It begins with standard lattice representation results (originally from Jonsson [1953] but translated into the language of Lerman [1971] or [1983]:

Theorem 4.2. Let L be a recursively presentable partial lattice with 0 its least element. There is a uniformly recursive array Θ of functions α_{n} : L → ω such that for all p, q, r ∈ L and n, m ∈ ω:

0. α_{n}(0) = 0,

1. p ≤ q ⇒ α_{n}(q) = α_{m}(q) → α_{n}(p) = α_{m}(p) and p ≰ q ⇒ ∃k, l(α_{k}(q) = α_{l}(q) & α_{k}(p) ≠ α_{l}(p)),

2. p ∨ q = r ⇒ [α_{n}(p) = α_{m}(p) & α_{n}(q) = α_{m}(q) → α_{n}(r) = α_{m}(r)],

3. p ∧ q = r & α_{n}(r) = α_{m}(r) ⇒ ∃n_{1}, n_{2}, n_{3}[α_{n}(p) = α_{n_{1}}(p) & α_{n_{1}}(q) = α_{n_{2}}(q)

& α_{n_{2}}(p) = α_{n_{3}}(p) & α_{n_{3}}(q) = α_{m}(q)]. The α_{n_{i}} here are called interpolants for (or between) α_{n} and α_{m}.

(A simple proof without the requirement for 0 is in Shore [1982]. Adding the requirement that the value of each function in the representation is 0 at 0 at the beginning presents no difficulties. A proof in this case (even with the additional assumption that the lattice has a greatest element as well as a least) can be found in Greenberg and Montalbán [2004].)

Standard arguments as in Shore [1982] show that we can define an embedding of P into D from any sufficiently generic function h : ℕ →Θ by letting the image of p ∈ L be the degree of the function h_{p} defined by h_{p}(n) = h(n)(p). In our setting, we proceed more cautiously so as to be able to do the embedding and simultaneously build the desired g_{i} all below x when x ∈ ANR. We consider the case with only one set S as a second set simply adds extra notation with no change in the types of requirements or strategies.

Let S be defined by n ∈ S ⇔ ∃u∀v∃wR(n, u, v, w, X) where R is recursive (in X). Let Θ = {α_{i}|i ∈ ℕ} be a recursive (partial) lattice table representation for L in the sense of Theorem 4.2. We will build a function h : ℕ →Θ recursively in X by a sequence of finite approximations h_{s} which will be initial segments of h. Our embedding of L into the degrees below x will then be given as usual by p ↦ deg(h_{p}) = h_{p} where h_{p}(n) = (h(n))(p) for p ∈ L. For notational convenience we let D_{n} = h_{d_{n}} ∈ d_{n}. By the definition of a lattice table, p ≤_{L} q → h_{p} ≤_{T} h_{q} and p ∨ q = r → h_{p} ⊕ h_{q} ≡_{T} h_{r}. In our construction we must act to satisfy the requirements for nonorder and infimum:

N_{e,p,q} for p ≰ q: {e}^{h_{p}} ≠ h_{q}.

P_{e,p,q,r} for p ∧ q = r: If {e}^{h_{p}} = {e}^{h_{q}} = C then C ≤_{T} h_{r}. In addition, we have the requirements for the sets G_{i} that we are constructing simultaneously via initial segment approximations g_{i,s} to represent the desired degrees g_{i}:

Q_{e}: If {e}^{G_{0}} = D = {e}^{G_{1}}, then D ≤_{T} ⊕{D_{i}|i ≤ s & i ∈ S} for some s.

R_{n}: If n ∈ S then D_{n} ≤_{T} G_{0}, G_{1}.

Our mechanism to satisfy the requirements R_{n} will proceed by coding D_{n} into G_{i}^{[⟨n,u⟩]} = {x| ⟨n, u, x⟩ ∈ G_{i}} if ∀v∃wR(n, u, v, w, X). The overriding rule that will be observed for every ⟨n, u⟩ is that for each t,m and i ∈ {0, 1}, there will be at most one ⟨n, u, t, m, k⟩ ∈ G_{i}. We divide the requirement R_{n} into subrequirements R_{n,u,m}.

R_{n,u,m}: At stage s these requirements will ask that ⟨n, u, t, m, D_{n,s}(m)⟩ ∈ G_{i} for some t (actually the least t allowed) if ∀v ≤ m∃w ≤ sR(n, u, v, w, X). Thus if n ∈ S and u is its witness then for each m there will be a stage s(m) after which we will always try to code D_{n}(m) into G_{i}^{[⟨n,u⟩]} in this way. Our decoding procedure is to calculate D_{n}(m) from G_{i}^{[⟨n,u⟩]} by searching for a ⟨t, m, k⟩ such that ⟨t, m, k⟩ ∈ G_{i}^{[⟨n,u⟩]} and declaring that D_{n}(m) = k. Our overriding rule will guarantee that we find at most one answer and we must argue that for almost all m we eventually insert the correct answer into G_{i}.

We put all the requirements N_{e,p,q}, P_{e,p,q,r}, Q_{e} and R_{n,u,m} into a single priority list S_{e}. The requirements N_{e,p,q} and P_{e,p,q,r} are handled in a fairly standard way if they do

not appear satisfied (as will be defined in the construction).

N_{e,p,q} at stage s: We look for an x and an extension h̃ of h_{s} such that {e}h̃_{p}(x) ↓≠ h̃_{q}(x). Making such an extension would, of course, satisfy the requirement. We will argue that if we never get to make such an extension, then {e}^{h_{p}} is not total.

P_{e,p,q,r} at stage s: Here we have a multistep procedure. We first look for an x and extensions h^{0}, h^{4} of h_{s} of the same length such that {e}^{h_{p}^{0}}(x) ↓≠ {e}^{h_{q}^{4}}(x) ↓ and h^{0}(m)(r) = h^{4}(m)(r) for m ∉ dom h_{s}. If we find such, we choose interpolants ρ_{1,m}, ρ_{2,m} and ρ_{3,m} between h^{0}(m) and h^{4}(m) for m ∈ dom h^{0} − dom h_{s} as in Theorem 4.2(3). Let h^{j} (j = 1, 2, 3) extend h_{s} by making h^{j}(m) = ρ_{j,m} for m ∈ dom h^{0} − dom h_{s}. Now look in turn (for j = 1, 2, 3) for extensions ĥ^{j} of h^{j} such that {e}ĥ_{p}^{j}(x) ↓, {e}ĥ_{q}^{j}(x) ↓ and ĥ^{j}(m) = ĥ^{j′}(m) for m ∉ dom h^{j} for j, j′ ≤ 4, i.e. first try to extend h^{1} to get the convergences at x and then, if successful, add the new values on to h^{2} and try to extend that to get the convergences. If successful add the new values onto h^{3} and try to extend that to get the convergences. If successful, extend h^{0}, h^{4} and the ĥ^{j} (1 ≤ j ≤ 3) to h̃^{j} (j ≤ 4) so that they have the same length and the same values on all numbers at which they are not yet defined. If we have been successful all the way to the end, then by the properties of the interpolants and the fact that all later extensions of the h^{j} were the same for all new values, we see that there is a j ≤ 4 such that {e}h̃_{p}^{j}(x) ↓≠ {e}h̃_{q}^{j}(x). If we find and choose such an h̃^{j} as h_{s+1} we, of course, satisfy requirement P_{e,p,q,r}. We will argue that if we never choose such an extension and {e}^{h_{p}} = {e}^{h_{q}} = C then C ≤_{T} h_{r} as required.

Q_{e} at stage s: If Q_{e} appears unsatisfied, we will search for an x and h̃ extending h_{s} and g̃_{i} extending g_{i,s} such that {e}g̃_{0}(x) ↓≠ {e}g̃_{1}(x) ↓, the g̃_{i} obey the overriding rule of coding, add no new elements ⟨n, u, t, m, y⟩ to G_{i} if ⟨n, u⟩ < e unless ∀v ≤ e∃w ≤ sR(n, u, v, w, X). If this last condition holds, then such elements may be added to G_{i} by g̃_{i} but only if they are of the right form, i.e. h̃_{d_{n}}(m) = y. Again, if we find and make such an extension, we satisfy Q_{e}. As in the other cases, we must argue that if we never make such an extension and {e}^{G_{0}} = D = {e}^{G_{1}} for some n then D ≤_{T} ⊕{D_{i}|i ≤ s & i ∈ S} for some s.

R_{n,u,m} at stage s: If R_{n,u,m} is not yet satisfied and ∀v ≤ m∃w ≤ sR(n, u, v, w, X) then we look for extensions of g_{i,s} to include ⟨n, u, t, m, D_{n,s}(m)⟩ for some t if this does not violate the overriding rule of coding.

As usual for constructions below an ANR set X, we must define an appropriate function f̂ ≤_{wtt} 0′, choose one f ≤_{T} X not dominated by f̂ and restrict our searches for witnesses and extensions at stage s to ones with codes less than f(s). We now define f̂ by specifying, recursively in advance for each s, a finite list of questions to be asked of 0′ and recursive search procedures that will terminate if 0′ answers the associated question positively. The questions and searches corresponding to the desired actions for each requirement are as follows:

N_{e,p,q}: For each finite function ĥ : ℕ →Θ with code less than s and requirement N_{e,p,q} = S_{t} for t < s ask if there is an x and an extension h̃ of ĥ such that {e}h̃_{p}(x) ↓≠ h̃_{q}(x). If the answer is yes, we include a search for one such extension.

P_{e,p,q,r}: For each finite function ĥ : ℕ →Θ with code less than s and requirement P_{e,p,q,r} = S_{t} for t < s ask if there is an x and extensions h^{0}, h^{4} of ĥ of the same length such that {e}^{h_{p}^{0}}(x) ↓≠ {e}^{h_{q}^{4}}(x) ↓ and h^{0}(m)(r) = h^{4}(m)(r) for m ∉ dom h_{s}. If the answer to this question is yes, we include a search for the first such extensions in a standard search procedure. Also ask if there is an extension ĥ^{1} of the h^{0} of the first pair satisfying the previous search condition extended by the first interpolants between it and h^{4} (the second element of the first pair found) as described above such that {e}ĥ_{p}^{1}(x) ↓ and {e}ĥ_{q}^{1}(x) ↓. If the answer from 0′ is yes, include a search for (the first such) ĥ^{1}. We also ask if there is an extension ĥ^{2} of the finite function that would be produced as h^{2} by the first search and extending first by the associated interpolants and then also by the new values determined by the witness ĥ^{1} just described. If the answer from 0′ is yes, include a search for (the first such) ĥ^{2}. Similarly, we ask if all the searches needed to define ĥ^{3} terminate and if so include that search as well.

Q_{e}: For each requirement Q_{e} = S_{t} for t < s and finite functions ĥ, ĝ_{0}, ĝ_{1} with codes less than s and finite set F of numbers less than e, we ask if there is an x and extensions h̃, g̃_{0}, g̃_{1} of ĥ, ĝ_{0} and ĝ_{1}, respectively, such that {e}g̃_{0}(x) ↓≠ {e}g̃_{1}(x) ↓, the g̃_{i} obey the overriding rule of coding, add no new elements ⟨n, u, t, m, y⟩ to G_{i} if ⟨n, u⟩ < e unless ⟨n, u⟩ ∈ F and, if ⟨n, u⟩ ∈ F, they add such elements only if h̃_{d_{n}}(m) = y. If the answer is yes, we include a search for such extensions.

R_{n,u,m}: For each requirement R_{n,u,m} = S_{t} for t < s and finite functions ĥ, ĝ_{0}, ĝ_{1} with codes less than s find (recursively including answering the question if they exist) the least t such that ⟨n, u, t, m, ĥ_{d_{n}}(m)⟩ can be added to G_{i} without violating the overriding coding rule and the codes for the corresponding extensions of ĝ_{i}.

We let f̂(s) be the max of s and the codes of all finite functions and witnesses found by all of the search procedures that 0′ says will terminate. Note that f̂ is nondecreasing and wtt below 0′. We let f ≤_{wtt} X be such that f is nondecreasing and not dominated by f̂, i.e. ∃^{∞}s(f̂(s) < f(s)).

Construction: We begin at stage 0 with h_{0}, g_{i,0} = ∅. At stage s + 1 we have h_{s} and g_{i,s} with codes less than s + 1 and act to define h_{s+1}, g_{i,s+1} with codes less than s + 2. For each requirement S_{e} with e < s that does not now appear to be satisfied we search for extensions (and witness x if needed) with codes less than f(s) as requested in the initial descriptions above of the requirements. If we find any such, we act for the one found of highest priority by choosing as h_{s+1} and g_{i,s+1} the longest possible extensions of h_{s} and g_{i,s}, respectively, contained in the first found extensions which have codes less than s + 2 (these are the targets for this requirement at stage s). If there are no such extensions for any requirement less than s then h_{s+1} = h_{s} and g_{i,s+1} = g_{i,s}.

This description is unambiguous for requirements of the form N_{e,p,q}, Q_{e} and R_{n,u,m}. If, by our action in these cases, we reach the desired target extensions for the requirement of highest priority for which we found desired extensions, we declare this requirement satisfied and it will remain satisfied forever. The procedure for requirements P_{e,p.q,r} needs further elaboration.

For each currently unsatisfied P_{e,p.q,r} = S_{k} for k < s, we mimic the search procedure as described in the initial account of this requirement but bounding our searches by f(s). If we reach the end of the procedure with an h̃^{j} as described then that is our target for this requirement. If we reach this target at stage s, P_{e,p.q,r} is declared satisfied and remains so forever. If there is no such h̃^{j} as a target, we see where the search procedure for P_{e,p.q,r} failed.

If the search failed at the first step, i.e. we found no extensions h^{0}, h^{4} of h_{s} of the same length such that {e}^{h_{p}^{0}}(x) ↓≠ {e}^{h_{q}^{4}}(x) ↓ and h^{0}(m)(r) = h^{4}(m)(r) for m ∉ dom h_{s}, we let h_{s} and g_{i,s} be the targets for P_{e,p.q,r}. If we act for no requirement of higher priority, we act for P_{e,p.q,r} by setting h_{s+1} = h_{s}, g_{i,s+1} = g_{i,s} and declare P_{e,p.q,r} to be satisfied. If at the beginning of any later stage t we see that there are extensions h^{0}, h^{4} of h_{s} with codes below f(t) as were desired at stage s, then P_{e,p.q,r} becomes unsatisfied.

If we found extensions h^{0}, h^{4} of h_{s} as desired below f(s), we take the first ones found in our standard search and define h^{j} for j = 1, 2, 3 as above. We now search (below f(s)) in turn for j = 1, 2, 3 for ĥ^{j} as described. If we find them all then we would have an h̃^{j} as required and so by our case assumption, one of the searches fails. Say the first to fail is for ĥ^{j}. It failed because we had found an extension h̄^{j} of h^{j} as described so far but no extension h̃ of h̄^{j} such that {e}h̃_{p}(x) ↓ and {e}h̃_{q}(x) ↓. In this case, we set our target for P_{e,p.q,r} to be this h̄^{j} (and no changes for g_{i,s}). If we reach this target at stage s we declare P_{e,p.q,r} to be satisfied. However, if at the beginning of any later stage t we see (by a search below f(t)) that there is an extension h̃ of h̄^{j} such that {e}h̃_{p}(x) ↓ and {e}h̃_{q}(x) ↓, P_{e,p.q,r} becomes unsatisfied.

Verifications: We wish to show that we stop acting for each requirement and that each of their goals is met.

Lemma 4.3. For each requirement S_{t} there is a stage s(t) after which S_{t} is never the requirement supplying the target chosen at stage s.

Proof. We proceed by induction on t and by cases dictated by the type of requirement.

S_{t} = N_{e,p,q}, Q_{e} or R_{n,u,m}: If there is any stage s > s(t − 1) at which S_{t} supplies a target then, by the rules of the construction and the assumption that s > s(t − 1), that target remains the one of highest priority available until we reach it. At that point S_{t} is satisfied and remains so forever. It therefore never supplies a target again.

S_{t} = P_{e,p.q,r}: Choose an s > s(t − 1) such that f(s) > f̂(s). If P_{e,p.q,r} entered this stage apparently satisfied and is not declared unsatisfied by our check below f(s) at the beginning of this stage then there will be no later stage at which it becomes unsatisfied. The point is that any extension that we are looking for has code less than f̂(s) if one exists at all by definition and so less than f(s) by our choice of s. Thus we may assume that P_{e,p.q,r} appears unsatisfied. By construction it always has a target and as s > s(t−1) it is the one of highest priority. Thus we head toward this target, eventually reach it and declare P_{e,p.q,r} satisfied. Again, as this target was chosen when f(s) > f̂(s), we will never discover that there was some desired extension not found at stage s. Thus P_{e,p.q,r} will remain satisfied forever and never supply a target again.

Lemma 4.4. All the requirements are satisfied.

Proof. S_{t} = N_{e,p,q}: If we ever declare N_{e,p,q} satisfied at t then {e}^{h_{p,t}}(x) ↓≠ h_{q,t}(x) and so {e}^{h_{p}} ≠ h_{q} as required. If not, consider an s > s(t) such that f(s) > f̂(s). As there are no targets found for N_{e,p,q} at s then as f(s) > f̂(s) there is no x with an extension h̃ of h_{s} such that {e}h̃_{p}(x) ↓≠ h̃_{q}(x). If, however, {e}^{h_{p}}(x) ↓ for some x ∉ dom h_{q,s} then there would be an ŝ > s such that {e}^{h_{p}}(x) ↓= {e}^{h_{p,ŝ}}(x) ↓. By the properties of the lattice table there would then be an h̃ such that h̃_{p} = h_{p,ŝ} and h̃_{q}(x) ≠ h_{q,ŝ}(x). Clearly one of h̃ and hŝ would be an extension of h_{s} satisfying the desired property for a contradiction to our case assumption. Thus, in this case, {e}^{h_{p}} is not total.

S_{t} = P_{e,p,q,r}: By the proof of the previous Lemma there is a stage s at which we declare P_{e,p,q,r} satisfied and it never becomes unsatisfied again. If the declaration was based on making an extension such that {e}h̃_{p}^{j}(x) ↓≠ {e}h̃_{q}^{j}(x) ↓ then {e}^{h_{p}}(x) ↓≠ {e}^{h_{q}}(x) ↓ and we satisfy P_{e,p,q,r}. Otherwise, our search procedure terminated at an intermediate step because of our failure to find certain extensions with specified properties. As we never declare P_{e,p,q,r} to be unsatisfied a later stage, there are, in fact, no such extensions.

If the failure occurred at the first step, there are no extensions h^{0} and h^{4} of h_{s} such that {e}^{h_{p}^{0}}(x) ↓≠ {e}^{h_{q}^{4}}(x) ↓ and h^{0}(m)(r) = h^{4}(m)(r) for m ∉ dom h_{s}. In this case, if {e}^{h_{p}} = C = {e}^{h_{q}} we claim that C ≤_{T} h_{r}. To compute C(x) find any ĥ extending h_{s} such that ĥ(m)(r) = h(m)(r) for m ∈ dom h with {e}ĥ_{p}(x) ↓. Such an ĥ exists since h ↾ u is one where u is sufficiently large so that {e}^{(h↾u)_{p}}(x) ↓ and {e}^{(h↾u)_{q}}(x) ↓. If {e}ĥ_{p}(x) ↓≠ C(x) then the pair ĥ and h ↾ u would supply a pair as desired and not found at stage s (by possibly extending one of them to make them of the same length) contradicting our case assumption. Thus, in this case, we satisfy P_{e,p,q,r} by computing C from h_{r} if {e}^{h_{p}} = C = {e}^{h_{q}}.

If the failure occurred later, we had an h̄^{j} with no extension ĥ of h̄^{j} such that {e}ĥ_{p}(x) ↓ and {e}ĥ_{q}(x) ↓. In this case we set this h̄^{j} to be our target and eventually realized it as an initial segment of our final h. Thus not both {e}^{h_{p}}(x) and {e}^{h_{q}}(x) are convergent and we satisfy P_{e,p,q,r} in this way.

S_{t} = Q_{e}: If we satisfy Q_{e} at some stage s then {e}^{g_{0,s}}(x) ↓≠ {e}^{g_{1,s}}(x) ↓ and so {e}^{g_{0}} ≠ {e}^{g_{1}} as required. Otherwise, consider an s > s(t − 1) such that f(s) > f̂(s) and, for every ⟨n, u⟩ < e, ∀v ≤ e∃wR(n, u, v, w, X) → ∀v ≤ e∃w ≤ sR(n, u, v, w, X). We also require that if ⟨n, u⟩ < e and ∃v∀w¬R(n, u, v, w, X) with v(n, u) being the least such v then R_{n,u,m} never supplies a target after stage s for m ≤ v(n, u). If there are no targets found for Q_{e} at s then, as f(s) > f̂(s), there is no x with extensions ĝ_{i} of g_{i,s} such that {e}ĝ_{0}(x) ↓≠ {e}ĝ_{1}(x) ↓ also satisfying the other conditions required for them. We claim that for every v ≥ s, the h_{v} and g_{i,v} satisfy these extra conditions. As we always obey the overriding rule of coding, it is satisfied by every g_{i,v}. If it is not the case that ∀v ≤ e∃w ≤ sR(n, u, v, w, X) for some ⟨n, u⟩ < e then this situation remains true at every v > s by our choice of s. Thus no Q_{i} with i > e can add an element ⟨n, u, t, m, y⟩ with such ⟨n, u⟩ < e to G_{i}. The only other requirements that can add elements ⟨n, u, t, m, y⟩ with ⟨n, u⟩ < e to G_{i} are the R_{n,u,m}. Our final condition on the size of s, however, guarantees that none of these for which ∃v∀w ≤ s¬R(n, u, v, w, X) will ever act after stage s. The other R_{n,u,m′} will put numbers into G_{i} at a stage v > s only if y = h_{d_{n},v}(m′). Thus in every case we maintain the fact that h_{v}, g_{i,v} satisfy the extra conditions required for the extensions desired at stage s. Now suppose {e}^{g_{0}}(x) ↓= {e}^{g_{1}}(x) ↓= z. We can calculate z by finding any ĥ, ĝ_{i} extending h_{s} and g_{i,s}, respectively and obeying the extra conditions on ĝ_{i} such that {e}ĝ_{0}(x) ↓= {e}ĝ_{1}(x) ↓ and such that ĥ_{d_{n}}(m′) = h_{d_{n}}(m′) for every m′ ∈ dom ĥ_{d_{n}}, n < e and n ∈ S. Such exist by our assumption. If one had {e}ĝ_{0}(x) ↓≠ z then h_{v}, ĝ_{0} and g_{1,v} would be extensions of h_{s} and g_{i,s} as desired in our original search at stage s contradicting our case assumption. Clearly, we can find such ĥ, ĝ_{i} and so z recursively in ⊕{D_{n}|n < e & n ∈ S}. Thus if {e}^{g_{0}}(x) = D = {e}^{g_{1}}(x), then D ≤_{T} ⊕{D_{n}|n < e & n ∈ S} as required.

R_{n}: Suppose that n ∈ S and u is a witness, i.e. ∀v∃wR(n, u, v, w, X). By our overriding coding condition, there is, for each m, at most one k such that ⟨n, u, t, m, k⟩ ∈ G_{i} for each i ∈ {0, 1}. We wish to show that, for each i ∈ {0, 1} and almost every m, ⟨n, u, t, m, D_{n}(m)⟩ ∈ G_{i} for some t. This will suffice to show that D_{n} ≤_{T} G_{i} as we can then correctly calculate D_{n}(m) at almost every m by searching for a ⟨n, u, t, m, k⟩ ∈ G_{i} and, upon finding one, declaring that k = D_{n}(m). Let s_{0} be such that no Q_{e} with e ≤ ⟨n, u⟩ ever supplies a target after stage s_{0}. The only actions that put a number ⟨n, u, t, m, k⟩ into G_{i} at s > s_{0} are ones (by other Q_{e′} and R_{n,u.m}) that do so only if k = h_{d_{n},s}(m) = D_{n}(m). Thus there at most finitely many incorrect values coded into G_{i}. Consider any m larger than all of these values, the requirement R_{n,u,m} and any stage s after s_{0} and t(j) where S_{j} = R_{n,u,m} such that ∀v ≤ m∃w ≤ sR(n, u, v, w, X) and h_{d_{n},s}(m) ↓. If no ⟨n, u, t, m, k⟩ ∈ g_{i,s}, then an extension putting ⟨n, u, t, m, h_{d_{n},s}(m)⟩ in is declared a target and it is the one of highest priority not yet satisfied. Thus we will eventually put such an element into g_{i} as required.

This concludes the proof of Theorem 4.1.

Corollary 4.5. ANR and hence C and C̃ have Property 1.

5 Forcing argument

In this section prove that C and C̃ have Property 2.

Theorem 5.1. For every degree x, there are a_{0}, a_{1} ≤ x^{(ω)} (indeed recursive in ⊕{(x ∨ 0^{(n)})′′′| n ∈ ℕ}) such that a_{0}, a_{1} ≥ x, a′′_{0} ∧ a′′_{1} = x′′ and (∀i ∈ {0, 1})(∀n)(a′′′_{i} ≰ (a_{i} ∨ 0^{(n)})′′, i.e. a_{i} ∈ C. Moreover, there are b_{0}, b_{1} ≤ (x ∨ 0^{(ω)})′′′ such that (x ∨ b_{0})′′ ∧ (x ∨ b_{1})′′ = x′′ and (∀i ∈ {0, 1})(∀n)(b′′′_{i} ≰ (b_{i} ∨ 0^{(n)})′′ and so (x ∨ b_{i}) ∈ C̃.

Working towards our proof, we first describe a forcing language and a specific notion of forcing. After analyzing the forcing relation for two quantifier sentences, we construct a sequence of forcing conditions that decide all two quantifier sentences in our language.

We also act along the way to satisfy requirements corresponding to the conditions on the degrees in the theorem.

Our forcing language is that of first order arithmetic with a unary predicate G for the generic set as usual plus additional unary predicates for a fixed X ∈ x and the sets 0^{(n)}. Our notion of forcing consists of triples ⟨σ, F, I⟩. Here σ ∈ 2^{<ω} is thought of as a finite initial segment of the characteristic function for the generic G, so if we have a sequence p_{s} = ⟨σ_{p_{s}}, F_{p_{s}}, I_{p_{s}}⟩ of conditions the corresponding generic set is G = ∪σ_{s}. F and I are disjoint finite subsets of ω. We say that p′ = ⟨σ′, F′, I′⟩ extends p = ⟨σ, F, I⟩, p′ ≤ p, if

• σ′ ⊇ σ, F′ ⊇ F, I′ ⊇ I and

• (∀j ∈ F)(∀x ∈ dom σ′ − dom σ)(x ∈ ω^{[j]} → σ′(x) = 0).

The intuition here is that once j ∈ F_{p} no more numbers in column j can be put into G and so G^{[j]} = {x| ⟨j, x⟩ ∈ G} will be finite. On the other hand, once j ∈ I_{p}, j can never be put into F_{q} for any q ≤ p and so if G is even slightly generic, G^{[j]} will be infinite.

We say that p ⊩ θ(x̄, G, X, 0^{(n)}) for θ with only bounded quantifiers if ℕ ⊨ θ(x̄, σ_{p}, X, 0^{(n)}), in the usual sense of σ_{p} having enough information to verify the statement which depends only on an initial segment of the predicate G. Thus p ⊩ θ(x̄, G, X, 0^{(n)}) ⇔ (σ_{p}, ∅, ∅) ⊩ θ(x̄, G, X, 0^{(n)}). Note that this relation is uniformly recursive in X ⊕ 0^{(n)} (or in X(0^{(n)}) if 0^{(n)}(X) does not appear in θ. The forcing relation on more complicated sentences is then defined in the usual inductive fashion.

Lemma 5.2. The relations p ⊩ ∃x̄∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) and p ⊩ ∀x̄∃ȳθ(x̄, ȳ, G, X, 0^{(n)}) for θ with only bounded quantifiers are uniformly Σ_{2} and Π_{2} in X ⊕ 0^{(n)}, respectively, or in X(0^{(n)}) alone if 0^{(n)}(X) does not appear in θ. Moreover, given any condition p and sentence ∃x̄∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) either there is a q ≤ p and x̄ such that q ⊩ ∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) and I_{q} = I_{p} or p ⊩ ∀x̄∃ȳ¬θ(x̄, ȳ, G, X, 0^{(n)}). In either, case we see that there is a q ≤ p deciding ∃x̄∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) with I_{q} = I_{p}.

Proof. To fix our notation we carry along both X and 0^{(n)} in θ and the full analysis. Omitting either one is purely a notational change. As usual, p ⊩ ∃x̄θ(x̄, G, X, 0^{(n)}) ⇔ ∃x̄p ⊩ θ(x̄, G, X, 0^{(n)}) for θ with only bounded quantifiers and so p ⊩ ∃x̄θ(x̄, G, X, 0^{(n)}) ⇔ (σ_{p}, ∅, ∅) ⊩ ∃x̄θ(x̄, G, X, 0^{(n)}). Thus if, for any given p, there is a q ≤ p such that q ⊩ ∃x̄θ(x̄, G, X, 0^{(n)}) then there is one q′ with F_{q′} = F_{p} and I_{q′} = I_{p}. (Just let q′ = (σ_{q}, F_{p}, I_{p}).) For Π_{1} sentences we have by definition p ⊩ ∀x̄θ(x̄, G, X, 0^{(n)}) ⇔ ∀q ≤ p(q ⊮ ∃x̄¬θ(x̄, G, X, 0^{(n)}). Thus these relations are uniformly Σ_{1} and Π_{1} in X ⊕0^{(n)}. We also see that p ⊩ ∀x̄θ(x̄, G, X, 0^{(n)}) ⇔ ∀q ≤ p(F_{q} = F_{p} & I_{q} = I_{p} → q ⊮ ∃x̄¬θ(x̄, G, X, 0^{(n)})). So p ⊩ ∀x̄θ(x̄, G, X, 0^{(n)}) ⇔ (σ_{p}, F_{p}, ∅) ⊩ ∀x̄θ(x̄, G, X, 0^{(n)}). (For the right to left direction suppose, for the sake of a contradiction that (σ_{p}, F_{p}, ∅) ⊮ ∀x̄θ(x̄, G, X, 0^{(n)}). So we have a q ≤ (σ_{p}, F_{p}, ∅) such that q ⊩ ∃x̄¬θ(x̄, G, X, 0^{(n)}) and so by the analysis of forcing for existential sentences, (σ_{q}, ∅, ∅) ⊩ ∃x̄¬θ(x̄, G, X, 0^{(n)}) and so (σ_{q}, F_{p}, I_{p})∃x̄¬θ(x̄, G, X, 0^{(n)}) and extends p for the required contradiction.)

At the two quantifier level, p ⊩ ∃x̄∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) ⇔ ∃x̄p ⊩ ∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) and p ⊩ ∀x̄∃ȳθ(x̄, ȳ, G, X, 0^{(n)}) ⇔ ∀x̄∀q ≤ p∃ȳ∃r ≤ q(r ⊩ θ(x̄, ȳ, G, X, 0^{(n)}) and so these relations are uniformly Σ_{2} and Π_{2} in X ⊕ 0^{(n)}, respectively. Moreover, given any p if there is any x and q ≤ p such that q ⊩ ∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) then, by the fact above about forcing Π_{1} sentences, (σ_{q}, F_{q}, ∅) ⊩ ∀ȳθ(x̄, ȳ, G, X, 0^{(n)}) and so does (σ_{q}, F_{q}, I_{p}) which is an extension q′ of p with I_{p} = I_{q′}. On the other hand, if there is no x and no q ≤ p with I_{p} = I_{q} that forces ∀ȳθ(x̄, ȳ, G, X, 0^{(n)}), then p ⊩ ∀x̄∃ȳ¬θ(x̄, ȳ, G, X, 0^{(n)}).

We now show how to construct the degrees a_{i} required in the Theorem. Minor modifications will then suffice to construct the desired b_{i}. Our plan is to construct sequences p_{s}^{i} of forcing conditions for i ∈ {0, 1} with p_{s+1}^{i} ≤ p_{s}^{i}. We let G_{i} = ∪σ_{p_{s}^{i}} and A_{i} be X ⊕ G_{i} which for notational convenience we take to be {0} × X ∪ {1} × G_{i}. We make a list θ_{j,n}(x̄, ȳ, G, X, 0^{(n)}) of the formulas with only bounded quantifiers and so of the Σ_{2} sentences of our language: φ_{j,n} = ∃x̄∀ȳθ_{j,n}(x̄, ȳ, G, X, 0^{(n)}). Deciding these sentences in our construction will be requirements S_{j,n}. We also deal with the requirements N_{e} : {e}^{A′′_{0}} = C = {e}^{A′′_{1}} ⇒ C ≤_{T} X′′ and D_{i,e,n} : A′′′_{i} ≠ {e}^{(A_{i}⊕0^{(n)})′′}. We let R_{s} list all these requirements. To handle the diagonalization requirements, we choose a recursive function f such that (∀A, s, t)(f(s, t) ∉ A′′′ ⇔ (∀w ≥ t)(A^{[⟨1,s,t⟩]} is finite).

Construction: We begin with p_{0}^{i} = (∅, ∅, ∅). At the beginning of stage s + 1 we will have forcing conditions p_{s}^{i}. We act at stage s + 1 according to the following cases:

R_{s} = S_{j,n}: For each i ∈ {0, 1}, ask if ∃x̄∃q^{i} ≤ p_{s}^{i} such that q^{i} ⊩ ∀ȳθ_{j,n}(x̄, ȳ, G, X, 0^{(n)}). If so, we can choose such q^{i} with I_{q^{i}} = I_{p_{s}^{i}} by Lemma 5.2. We then set p_{s+1}^{i} = q^{i}. If there is no such q^{i}, we set p_{s+1}^{i} = p_{s}^{i}. Note that in either case p_{s+1}^{i} decides φ_{j,n} and I_{p_{s+1}^{i}} = I_{p_{s}^{i}}. By Lemma 5.2, this procedure is uniformly recursive in (x ∨ 0^{(n)})′′.

R_{s} = D_{i,e,n}: Let t = max I_{p_{s}^{i}} + 1 and ask if there is a τ such that {e}^{τ}(f(s, t)) = 0 and a q ≤ p_{s}^{i} that forces the Σ_{2} and Π_{2} facts about G, X, 0^{(n)} needed to make τ an initial segment of (X ⊕ G_{i} ⊕ 0^{(n)})′′ such that there is no ⟨k, v⟩ ∈ I_{q} − I_{p_{s}^{i}} with k ≤ s. If so, let w = max F_{q} + t + 1 and p_{s+1}^{i} = (σ_{q}, F_{q}, I_{q} ∪ {⟨s, w⟩}). (The condition p_{s+1}^{i} guarantees that at the end of the construction {e}^{(A_{i}⊕0^{(n)})′′}(f(s, t)) = 0. On the other hand, it also guarantees that A_{i}^{[⟨1,s,w⟩]} is infinite and so that f(s, t) ∈ A′′′_{i} for the desired diagonalization.) If there is no such q then let p_{s+1}^{i} = p_{s}^{i}. (In this case we will argue that every A_{i}^{[⟨1,s,t′⟩]} is finite for t′ ≥ t but {e}^{(A_{i}⊕0^{(n)})′′}(f(s, t)) ≠ 0 and so we also diagonalized.) Again by Lemma 5.2 this procedure is recursive in (x ∨ 0^{(n)})′′′.

R_{s} = N_{e}: Ask if there are τ^{i} and x such that {e}^{τ^{0}}(x) ↓≠ {e}^{τ^{1}}(x) ↓ and q^{i} ≤ p_{s}^{i} such that there is no ⟨k, v⟩ ∈ I_{q} − I_{p_{s}^{i}} with k ≤ s and q^{i} forces all the Σ_{2} and Π_{2} facts needed to make τ^{i} an initial segment of (X ⊕ G_{i})′′. If so, let p_{s+1}^{i} = q^{i}. (Clearly in this case we have guaranteed that {e}^{A′′_{0}} ≠ {e}^{A′′_{1}}.) Otherwise, we let p_{s+1}^{i} = p_{s}^{i}. (In this case, we will argue that we also satisfy the requirement N_{e}.) Again by Lemma 5.2 this procedure is recursive in x′′′.

Verification: We argue that at stage s + 1 we satisfy requirement R_{s}. For R_{s} = S_{j,n} this is immediate and so, as usual, every Σ_{2}(Π_{2}) sentence about G_{i}, X and any 0^{(n)} (and so also the appropriate “translations” of such sentences about A_{i} and 0^{(n)}) is true if and only if it is forced. For the other requirements, we first note that, by construction, no ⟨k, v⟩ with k ≤ s is ever added to I_{p_{t+1}^{i}} for t > s.

R_{s} = D_{i,e,n}: Clearly if we extended p_{s}^{i} to a q as desired in the construction, we have {e}^{(A_{i}⊕0^{(n)})′′}(f(s, t)) = 0. We also put some ⟨s, w⟩ into I_{p_{s+1}^{i}} and so it never enters F_{p_{r}^{i}} for any r. Thus when we reach any stage r > s with R_{r} devoted to a sentence that says that ∃x > v(⟨s, x⟩ ∈ G_{i}) then we choose an extension that forces it to be true and so A_{i}^{[⟨1,s,t⟩]} is infinite and f(s, t) ∈ A′′′_{i} for the desired diagonalization. On the other hand, if there is no q ≤ p_{s}^{i} as desired in the construction, then no number ⟨s, v⟩ with v ≥ t is ever put into I_{p_{r}^{i}} for any r. Thus when we reach any stage r with R_{r} devoted to a sentence that says that ∃w∀u > w(u ∉ G_{i}^{[⟨s,v⟩]}) for any v ≥ t, we will choose an extension which forces it to be true by putting ⟨s, v⟩ into F_{p_{r}^{i}}. Thus G_{i}^{[⟨s,v⟩]} and so A_{i}^{[⟨1,s,v⟩]} is finite for every v ≥ t and f(s, t) ∉ A′′′. On the other hand, if {e}^{(A_{i}⊕0^{(n)})′′}(f(s, t)) ↓= 0 then there is some oracle information τ about (X ⊕ G_{i} ⊕ 0^{(n)})′′ that gives the correct computation. Each Σ_{2} or Π_{2} fact about X ⊕ G_{i} ⊕ 0^{(n)} reflected in τ is decided at some stage of the construction and must be decided in accordance with the information in τ. So some p_{y}^{i} forces all the facts needed by τ. By construction, no numbers of the form ⟨s, v⟩ are added to I_{p_{r}^{i}} after stage s and so p_{y}^{i} is an extension of p_{s}^{i} that could have been chosen at stage s contradicting our assumption. So again we have that, if convergent, {e}^{(A_{i}⊕0^{(n)})′′}(f(s, t)) does not equal A′′′(f(s, t)) as required.

R_{s} = N_{e}: Again, if at stage s we found q^{i} as described and extended p_{s}^{i} accordingly, {e}^{A′′_{0}} ≠ {e}^{A′′_{1}}. If not, but {e}^{A′′_{0}} = C = {e}^{A′′_{1}}, then we claim that C ≤_{T} X′′. To compute C(x), find any τ such that {e}^{τ}(x) ↓ and any extension q of p_{s}^{0} such that q forces all the Σ_{2} and Π_{2} facts about X ⊕ G_{0} needed to make τ an initial segment of A′′_{0} and there is no ⟨k, v⟩ ∈ I_{q} − I_{p_{s}^{0}} with k ≤ s. As some p_{y}^{0} forces all the true facts about A_{0} needed to get the correct computation of {e}^{A′′_{0}}(x) and, by construction, there is no ⟨k, v⟩ ∈ I_{p_{y}^{0}} − I_{p_{s}^{0}} with k ≤ s, this search terminates (with some τ and q). As the forcing relation for Σ_{2}(G, X)and Π_{2}(G, X) sentences are Σ_{2}(X) and Π_{2}(X) respectively, the search is recursive in X′′. Finally, we claim that the search terminates with a τ such that {e}^{τ}(x) = {e}^{A_{1}}(x) = C(x) as desired. The point here is that there is some y such that p_{y}^{1} forces all the all the true facts τ^{1} about A′′_{1} needed to get the correct computation of {e}^{A′′_{1}}(x) and, of course, p_{y}^{1} ≤ p_{s}^{1} and there is no ⟨k, v⟩ ∈ I_{p_{y}^{1}} −I_{p_{s}^{1}} with k ≤ s. Thus the pairs τ, τ^{1} and q, p_{y}^{1} would be as desired at stage s of the construction, contrary to our assumption. This concludes the construction of the sets A_{0} and A_{1} and so the desired degrees a_{0} and a_{1}.

To construct the degrees b_{i} required in the theorem repeat the above argument with B_{i} = G_{i} in place of A_{i} omitting X from the requirements D_{i,e,n} making that step of the construction recursive in 0^{(n+3)}. We also adjust the list of formulas θ_{j,n} in S_{j,n} so that they omit either X or 0^{(n)} but still contain all instances of such formulas with at most one of these two parameters. This adjustment makes the corresponding steps of the construction recursive in either x′′′ or 0^{(n+3)}. Thus the B_{i} so constructed will have all the desired properties.

6 Localization and Counting Quantifiers

In this section we will examine our proof of the definability of the jump more carefully to see that it is a correct definition in every sufficiently large jump ideal. The definition with C works in all ideals closed under the ω-jump but that with C̃ works in all jump ideals simply containing the single degree 0^{(ω)}. We will also calculate bounds on the quantifier complexity of these definitions. We begin with the localization issue. Let I be a jump ideal.

We start with the definition C_{ω} = {x|(∀z)(z ∨ x is not a minimal cover of z}. We need to verify that, for each n, I ⊧ 0^{(n)} ∈ C_{ω} and, for every x ∈ I, there is an n ∈ ℕ such that I ⊧ (∀z)(z ∨ x is not a minimal cover of z) → x ≤ 0^{(n)}. Of course, fact that 0^{(n)} ∨z is not a minimal cover of z in D means that it is not one in any ideal containing 0^{(n)} and z. For the second fact, note that Jockusch and Shore [1984, Corollary 3.3] actually prove that if x ≰ 0^{(n)} for every n then there is a z ≤ x ∨ 0^{(ω)} such that z ∨ x is a minimal cover of z. Thus the facts we need about C_{ω} are true in any jump ideal containing 0^{(ω)} as required.

Next, we note that all the procedures connected with Slaman-Woodin coding are arithmetic by the results of Slaman and Woodin [1986]. In particular, any countable set of pairwise incomparable degrees uniformly recursive in x are coded by a c ≤ x′′. Moreover, by definition, the set Kd(c) coded by c is uniformly recursive in just a few jumps of c. Thus it, and all the notions developed in §3 about coding and comparing sets, work in (i.e. are absolute for) I for any sets with degrees in I and any codes inside I for any jump ideal I. The relations absolute to any jump ideal I thus include y ∈Kd(c), Mp(č, ċ, c̈, ĉ, d, d̃), Compl(x, a, b, c) and Eq(a, c, ã, c̃).

This brings us to the definitions of C and C̃ in Theorem 3.5. We must verify that the classes so defined when interpreted in I still have Properties 1 and 2 in I. The lattice coding needed for Property 1 is done in Theorem 2.2 by degrees below the given x and so is available in any ideal containing x. The Slaman-Woodin coding needed in the formal definition of sets being coded below x work, as we just remarked, in every jump ideal containing x as they do in D. In particular, in the definition of Cd(x, a, c), a c needed for any a < x exists in the degrees arithmetic in x as the set {d_{n}} being coded is uniformly recursive in x^{(5)} (to calculate the infimum and other operations on degrees below x). As this set is the minimal one coded anywhere satisfying condition (3) and (4) of Definition 3.3, it is also the minimal one coded in I satisfying these conditions. Thus, for any a ≤ x coding a set, the existence of a c such that Cd(x, a, c) is absolute to any jump ideal so all the desired sets are coded below x by degrees in I. Similarly, the existence of codes needed for any instances of the relations M, Compl and Eq for parameters in I is absolute for any jump ideal. All that remains to check for the absoluteness of our definition of x′′≤ y′′ is Theorem 5.1 that C and C̃ have Property 2.

From the statement of Theorem 5.1, we see that the degrees a_{0}, a_{1} required for C exists below x^{(ω)}. As the properties of these degrees required in the definition are all specified in terms of lattice coding of sets and Slaman-Woodin comparisons, the degrees constructed have the desired properties inside any jump ideal containing them. Thus the definition of x′′≤ y′′ from C works in any ideal closed under the ω-jump as desired. For the definition in terms of C̃, we need the degrees b_{0}, b_{1} of Theorem 5.1. Again the statement of the theorem assures us that they are computable in (x ∨ 0^{(ω)})′′′ and so exist in any jump ideal containing 0^{(ω)}.

All that remains now is to verify the absoluteness of the definition of the jump from the relation x′′ ≤ y′′. Here we note that Shore and Slaman [1999, Theorem 2.3 n = 2 relativized to x] prove that if w ≰ x′ then there is a g ≤ w ∨ x′′ such that w ∨ g = g′′. As argued there, this suffices to show that x′ is the maximal w such that ∀g(g ≥ x → (w ∨ g) ≠ g′′ as required in the definition of x′ from the relation x′′ ≤ y′′: Clearly no degree less than or equal to x′ can join any g ≥ x to g′′. For the other direction, the cited theorem provides, for every w ≰ x′, a g ≤ w ∨ x′′, and so one in any jump ideal containing x and w, such that w ∨ g = g′′.

We have thus proven Theorem 3.7 and a version for the definition with C̃ as well.

Theorem 6.1. The definitions of x′′ ≤ y′′ and x′ = w in terms of C are absolute to every ideal I closed under the ω-jump, i.e. for x, y, w ∈I,

1. x′′ ≤ y′′ ⇔ I ⊧ (∀a, c)[Cd(a, c) & (∀z)(z ∈ C & x ≤ z → (∃ã, c̃)(Cd(z, ã, c̃) & Eq(a, c, ã, c̃)) → (∀w)(w ∈C & y ≤ w →(∃â, ĉ)(Cd(w,â, ĉ) & Eq(a, c, â, ĉ))].

2. x′ = w ⇔ I ⊧ ∀g(g ≥ x → (w ∨ g) ≠ g′′) & ∀v(∀g(g ≥ x → (v ∨ g) ≠ g′′→ v ≤ w).

When given in terms of C̃ they are absolute for every jump ideal I containing 0^{(ω)}, i.e. for x, y, w ∈I,

1. x′′ ≤ y′′ ⇔ I ⊧ (∀a, c)[Cd(a, c) & (∀z)(z ∈ C̃ & x ≤ z → (∃ã, c̃)(Cd(z, ã, c̃) & Eq(a, c, ã, c̃)) → (∀w)(w ∈C̃ & y ≤ w →(∃â, ĉ)(Cd(w,â, ĉ) & Eq(a, c, â, ĉ))].

2. x′ = w ⇔ I ⊧ ∀g(g ≥ x → (w ∨ g) ≠ g′′) & ∀v(∀g(g ≥ x → (v ∨ g) ≠ g′′→ v ≤ w).

We now provide an analysis of these definitions to calculate their quantifier complexity. We follow the process of definition in §3 and work first in the language with ∨, ∧ and 0.

Theorem 6.2. There are Π_{5} formulas of D in the language with ≤, ∨ and ∧ that define the relations x′′≤ y′′, x ∈ L_{2}(y) and x′′ = y′′in any jump ideal containing 0^{(ω)}, a Σ_{6}&Π_{6} one that defines w = x′′ and a Π_{8} one that defines the relation w = x′ in any such ideal.

Lemma 6.3. The relation y ∈Kd(c) is ∃&∀.

Proof. By definition (Theorem 3.1) y ∈Kd(c) ⇔ y ≤ u & ∃w(w ≤ h_{0}∨y, h_{1}∨y & w ≰ y) & (∀u < y)¬∃w(w ≤ h_{0} ∨ u, h_{1} ∨ u & w ≰ u).

Lemma 6.4. The relations Cd(x, a, c), Cd(a, c) and Cd(x, a, b, c) are ∀∃. The precise versions are ∀∃∀.

Proof. Consider the clauses of Definition 3.3. Clauses (1) and (2) are quantifier free. Clause (3) is ∃&∀ by the previous Lemma. Similarly, clause (4) is ∀(∃&∀ → ∃&∀&∃&∀) and so ∀∃. Clause (5) is ∀(∃&∀ → ∀). Using this analysis of (4), clause (6) is ∀(∀∃ → ∀(∃&∀ → ∃&∀)) and so ∀∃∀.

Lemma 6.5. The relation Compl(x, a, b, c) is ∀∃.

Proof. Compl(x, a, b, c) ⇔ Cd(x, a, b, c) & (∀d ∈Kd(c))(d ≤ g_{0}, g_{1} ↔ d ≰g_{2}, g_{3}). By the previous Lemmas this relation is ∀∃.

Lemma 6.6. The relation Mp(č, ċ, c̈, ĉ, z, z̃) is ∃∀.

Proof. Mp(č, ċ, c̈, ĉ, z, z̃) ⇔ (∃w, w̃ ∈Kd(č))(z ∨ w ∈Kd(ċ) & z̃ ∨ w̃ ∈Kd(c̈) & (z ∨ w ∨ z̃ ∨ w̃) ∈Kd(ĉ)). By Lemma 6.3 this is ∃∀.

Lemma 6.7. The relation Eq(a, c, ã, c̃) is ∃∀∃∀, i.e. Σ_{4}.

Proof. Eq(a, c, ã, c̃) ⇔Cd(a, c)&Cd(ã, c̃)&(∃č, ċ, c̈, ĉ){(∀x, y, z)(Mp(č, ċ, c̈, ĉ, x, y) & Mp(č, ċ, c̈, ĉ, x, z) → y = z) & Mp(č, ċ, c̈, ĉ, d_{0}, d̃_{0}) & (∀d)(∀d̃) (Mp(č, ċ, c̈, ĉ, d, d̃) → Mp(č, ċ, c̈, ĉ, (d ∨ e_{0}) ∧ f_{1}, (d̃ ∨ ẽ_{0}) ∧ f̃_{1}) & Mp(č, ċ, c̈, ĉ, (d ∨ e_{1}) ∧ f_{0}, (d̃ ∨ ẽ_{1}) ∧ f̃_{0}) & (d ≤ g_{0}, g_{1} ↔ d̃ ≤ g̃_{0}, g̃_{1})}. Applying the previous Lemmas we have that the relation is ∀∃&∀∃&∃{∀(∃∀&∃∀ →) & ∃∀&∀[(∃∀ → ∃∀&∃∀)]}. Some simplification yields ∀∃ & ∃{∀(∃∀ →) & ∀[(∃∀ → ∃∀]}. One more round gives ∃{∀∃ & ∀∃∀} and so ∃∀∃∀.

We can actually improve this calculation by being more explicit in our definitions of Mp and Eq. Recall that we defined Mp between the sets {d_{n}} and {d̃_{n}} corresponding to two codes a, c and ã, c̃, respectively, by choosing č, ċ, c̈ and ĉ such that, for any z ∈Kd(c) and z̃ ∈Kd(c̃), (∃w, w̃ ∈Kd(č))(z ∨ w ∈Kd(ċ) & z̃ ∨ w̃ ∈Kd(c̈) & (z ∨ w ∨ z̃ ∨ w̃) ∈Kd(ĉ)) ↔ (∃n)(z = d_{n} & z̃ = d̃_{n}). The intention here was that we would have a set h_{i} of mutually 1-generic degrees relative to any degree above all the d_{n} and d̃_{n} and let č code {h_{i}}. Next we let ċ code the set {d_{n} ∨ h_{2n}} of pairwise incomparable degrees and c̈ code {d̃_{n} ∨ h_{2n+1}}. Finally we let ĉ code {d_{n} ∨ h_{2n} ∨ d̃_{n} ∨ h_{2n+1}} which is also pairwise incomparable. We can now add on a new code c̀ for the set {h_{n} ∨ h_{n+2}|n ∈ ω} and so guarantee that (for these codes) if w, w̃ are the witnesses that Mp(č, ċ, c̈, ĉ, d_{n}, d̃_{n}) for n > 1 and w ∨ h, w̃ ∨ h̃, w ∨ j, w̃ ∨ j̃ ∈Kd(c̀) with h ≠ j and h̃ ≠ j̃ then some choice of one each of {h, j} and {h̃, j̃} provides the witnesses that Mp(č, ċ, c̈, ĉ, d_{n+1}, d̃_{n+1}). (The reason we need two candidates here is that for a given h_{n}, n > 1, both h_{n} ∨ h_{n+2} and h_{n} ∨ h_{n−2} are in Kd(c̀).) We can now use the code c̀ to provide a Σ_{3} equivalent for Eq.

Lemma 6.8. There is a Σ_{3} equivalent of Eq.

Proof. We use d_{1} and d̃_{1} as abbreviations for (d∨e_{0})∧f_{1} and ((d̃ ∨ ẽ_{0}) ∧ f̃_{1}), respectively.

Eq(a, c, ã, c̃) ⇔Cd(a, c)&Cd(ã, c̃)&(∃č, ċ, c̈, ĉ, c̀){ (∀x, y, z)(Mp(č, ċ, c̈, ĉ, x, y) & Mp(č, ċ, c̈, ĉ, x, z) → y = z) & Mp(č, ċ, c̈, ĉ, d_{0}, d̃_{0}) & Mp(č, ċ, c̈, ĉ, d_{1}, d̃_{1}) & (∀d ∈Kd(c))(∀d̃ ∈Kd(c̃))(∀h, h̃, j, j̃ ∈Kd(č)[h ≠ j&h̃ ≠ j̃ & (∃w, w̃ ∈Kd(č))(h ∨ w ∈Kd(c̀) & h̃ ∨ w̃ ∈Kd(c̀) & j ∨ w ∈Kd(c̀) & j̃∨ w̃ ∈Kd(c̀)& d ∨ w ∈Kd(ċ) & d̃ ∨ w̃ ∈Kd(c̈) & (d ∨ w ∨ d̃ ∨ w̃) ∈Kd(ĉ)) → ⋁_{k∈{h,j},k̃∈{h̃,j̃}}{

[((d ∨ e_{1}) ∧ f_{0} = d →((d ∨ e_{0}) ∧ f_{1})∨k ∈Kd(ċ) & ((d̃ ∨ ẽ_{0}) ∧ f̃_{1}) ∨ k̃ ∈Kd(c̈) & (((d ∨ e_{0}) ∧ f_{1})∨k ∨ ((d̃ ∨ ẽ_{0}) ∧ f̃_{1}) ∨ k̃) ∈Kd(ĉ))] & [((d ∨ e_{0}) ∧ f_{1} = d →((d ∨ e_{1}) ∧ f_{0})∨k ∈Kd(ċ) & ((d̃ ∨ ẽ_{1}) ∧ f̃_{0}) ∨ k̃ ∈Kd(c̈) & (((d ∨ e_{1}) ∧ f_{0})∨k ∨ ((d̃ ∨ ẽ_{1}) ∧ f̃_{0}) ∨ k̃) ∈Kd(ĉ)]}]}.

This formula is of the form ∀∃&∀∃&∃{∀(∃∀&∃∀ →) & ∃∀ & ∃∀ & ∀∀[∃&∀ & ∃&∀... & ∃(∃&∀ & ∃&∀...) → ⋁{[→ ∃&∀ & ∃&∀ & ∃&∀] & [→ ∃&∀ & ∃&∀ & ∃&∀]}]}. Simpli-

fying we get ∃{∀∃&∃∀ & ∀[∃&∀ & ∃(∃&∀) → ⋁{∃&∀}]} and so ∃{∀[∃∀ → ∃&∀]}, i.e. ∃∀∃.

Lemma 6.9. The relation x ∈C_{ω} is ∀∃.

Proof. x ∈C_{ω} ⇔ (∀z)(z ∨ x is not a minimal cover of z} ⇔ (∀z)(z ∨ x ≤ x or ∃w(x < w < z ∨ x)).

Lemma 6.10. The relation x ∈C is Σ_{4}.

Proof. By Theorem 3.5, x ∈C ⇔ ∃a, c(Cd(x, a, c) & (∀ã, b̃, c̃, z)(z ∈ C_{ω} & Compl(x ∨ z, ã, b̃, c̃) → ¬Eq(a, c, ã, c̃)). By the previous Lemmas this is ∃(∀∃ & ∀(∀∃ & ∀∃ → Π_{3})) and so Σ_{4}.

Lemma 6.11. The relation x ∈C̃ is also Σ_{4}.

Proof. x ∈C̃ ⇔ ∃y(y ∈C & y ≤ x).

Lemma 6.12. The relation x′′≤ y′′ using C or C̃ is Π_{5}.

Proof. By Theorem 3.6, x′′ ≤ y′′ ⇔ (∀a, c)[Cd(a, c) & (∀z)(z ∈ C & x ≤ z → (∃ã, c̃) (Cd(z, ã, c̃) & Eq(a, c, ã, c̃)) → (∀w)(w ∈C & y ≤ w →(∃â, ĉ)(Cd(w,â, ĉ) & Eq(a, c, â, ĉ))]. So this relation is ∀[Π_{2} & ∀(Σ_{4} → ∃(Π_{2} & Σ_{3})) → ∀(Σ_{4} → ∃(Π_{2} & Σ_{3}))]. Simplifying gives ∀[Π_{4} → Π_{4}], i.e. Π_{5}. If we use C̃ in place of C, nothing changes as both are Σ_{4}.

Lemma 6.13. The relation u ≥ x′′ is Π_{6}, u ≤ x′′ is Σ_{6} and so u = x′′ is Σ_{6}&Π_{6}.

Proof. As pointed out at the beginning of §2, x′′ = ∨{y ≥ x|y′′ ≤ x′′} and so u ≥ x′′ ⇔ (∀y ≥ x)(y′′ ≤ x′′→ & u ≥ y) and by the previous Lemma this relation is Π_{6}. As we also noted there, we have y_{1}, y_{2} ≥ x with y′′_{1}, y′′_{2} = x′′ such that y′′_{1}∨y′′_{2}= x′′ so that u ≤ x′′ ⇔ (∃y_{1}, y_{2} ≥ x)(y′′_{1}, y′′_{2} ≤ x′′ & u ≤ y_{1}∨y_{2}). This relation is then Σ_{6}.

Lemma 6.14. The relation x′ = w is Π_{8}.

Proof. By Theorem 3.6, x′ = w ⇔ w = max{z ≥_{T}x|(∀g ≥_{T}x)(z ∨ g ≱ g′′) ⇔ ∀g(g ≥ x → (w ∨ g) ≱ g′′) & ∀v(∀g(g ≥ x → (v ∨ g) ≱ g′′)→ v ≤ w). By the previous Lemmas, this relation is ∀(Σ_{6}) & ∀(∀Σ_{6} →), i.e. Π_{7} & Π_{8}.

We turn now to the issue of eliminating the defined symbols 0, ∨ and ∧. The only use of 0 is in clause (5) of Definition 3.3. We can eliminate it and the uses of ∨ and ∧ there as well without increasing its quantifier complexity by rewriting the clause as

5′ ∀d, d̂(d ≠ d̂ & d, d̂ ∈Kd(c) → ∀u, v(u ≤ d, d̂ → u ≤ v) & ∀u(u ≥ d, p → q ≤ u) & ∃x, y(y < x ≤ d, g_{0}, g_{1}) → d ≤ g_{0}, g_{1}).

Now, in general, we can eliminate ∨ at the expense of increasing the quantifier complexity by at most one. Given a formula Qx⃗φ where φ is quantifier free and includes the symbol ∨, we can find an equivalent without ∨ that has at most one additional alternation of quantifiers as follows: for each term of the form x ∨ y in φ we can add a new variable u and replace φ by ∃u(x, y ≤ u & ∀v(x, y ≤ v → u ≤ v) & φ(u/(x ∨ y))). Similarly, φ can be replaced by ∀u(x, y ≤ u & ∀v(x, y ≤ v → u ≤ v) → φ(u/(x∨y))). Of course, one of these replacements has its initial quantifier the same as the final one of Qx⃗ and so increases the quantifier complexity by exactly one. Clearly, we can iterate and even chain this procedure to eliminate all occurrences of ∨ at the same cost. We could perform the dual procedure for ∧ except for the fact that ∧ is not always defined in D. Checking all our formulas we see that the only remaining occurrences of ∧ are in terms of the form (d ∨ e_{0}) ∧ f_{1} or (d ∨ e_{1}) ∧ f_{0} with d ∈Kd(a, c) and the other elements e_{i} and f_{i} are the standard ones in a. In each such instance, we have also asserted in the formula that Cd(a, c) or we are within the definition of Cd itself. Thus we wish to add a condition that guarantees that all infima of this form exist. We do this by adding the following to clause (3) of Definition 3.3:

(∀d)(d ∈ K̂d(c)) → (∃u_{0}, u_{1,}v_{0}, v_{1})(d, e_{0} ≤ u_{0} & ∀w(d, e_{0} ≤ w → u_{0} ≤ w) & v_{0} ≤ u_{0}, f_{1} & ∀w(w ≤ u_{0}, f_{1} → w ≤ v_{0}) & d, e_{1} ≤ u_{1} & ∀w(d, e_{1} ≤ w → u_{1} ≤ w) & v_{1} ≤ u_{1}, f_{0} & ∀w(w ≤ u_{1}, f_{0} → w ≤ v_{1}))

where K̂d(c) is the version of Kd with ∨ eliminated and so on general grounds of complexity at most ∃∀&∀∃. This new clause is then Π_{3} in the language with just ≤. The whole translation of Cd into the language with just ≤ is then Π_{3} as we can now apply the general elimination procedure to clause (4). All later uses of ∧ take place within contexts in which we have, by this addition to clause (3) of the definition of Cd, guaranteed that the required infimum exists. We can thus apply the general elimination rules for ∧ as well as ∨ to all the remaining formulas at the cost of one level in quantifier complexity.

Theorem 6.15. There are Π_{6} formulas of D in the language with just ≤ that define the relations x′′≤ y′′, x ∈ L_{2}(y) and x′′ = y′′ in any jump ideal containing 0^{(ω)}, a Σ_{7}&Π_{7} one that defines w = x′′ and a Π_{9} one that defines the relation w = x′ in any such ideal.

7 Questions

Before turning to the major topic of this paper, the definability of the jump operator, we would like to point out an interesting class of problems raised by the introduction of our new hierarchies of generalized high and low classes in Definition 2.5. There are clearly many natural questions that these notions suggest. In general terms, one would want to know what properties of the usual generalized high and low hierarchies carry over to these new ones. These properties would include classifications by growth rates and structural properties of the degrees in the various classes.

Returning to our concern with definitions, perhaps someone so well steeped in the ways of the Turing degrees that the lattice and Slaman-Woodin coding procedures are second nature might been inclined to view our definitions as natural. At least in terms of invariance under automorphisms, one can dispense with the Slaman-Woodin coding apparatus. In this case, they simply say that one can determine various classes of degrees by the order types embeddable below them. (More precisely, they are determined by the finitely generated copies of independent degrees of order type ω along with an additional pair of degrees above some subset of these degrees.) In any case, there still seems room for a definition that the casual observer would see as natural. As we are perhaps already close to the border of the natural, it is even more difficult to make a precise claim as to what form of definition would fit the bill. There are, however, a couple of ways in which our results can be improved that do have precise measures.

The first is obviously the quantifier complexity of the definitions. Simpler is better and so we ask the following:

Question 7.1. Are there definitions of L_{2,} the double jump and the jump which are at lower levels of the alternating quantifier hierarchy than those established here?

The second way is the extent to which the definitions are local. Of course, a definition of the (double) jump can only make sense in jump ideals. (Individual instances such as a definition of 0′ can make sense in arbitrary ideals.) Our results require just a bit more: the presence of the single degree 0^{(ω)}. Thus we ask for the best possible results:

Question 7.2. Is there a formula that defines the relations x′ = w in every jump ideal? Is there a formula which defines the degree 0′ in every ideal containing it?

It seems reasonably likely that a definition that supplies positive answers to both questions will also be viewed by all as natural.

We have one suggestion for an approach for a minor improvement along the lines of the first of these questions. It is based on an alternate approach to a lattice coding of sets Σ_{3}^{X} supplied by recursive enumerability.

Theorem 7.3. If c > b and c is r.e. in b then every Σ_{3}^{C} set is coded below a.

Proof. Choose a ∈ (b, c) r.e. in b with a′ = b′. As described in Shore [1982, p. 262], the lattice L of Theorem 2.2 can be embedded in [b, a) with the images of d_{n} becoming uniformly recursive in a. By Shore [1981, Lemma 4.2], given any X ∈ Σ_{3}^{C} there is an exact pair for the ideal generated by {d_{n}|n ∈ X} below c.

Thus we could hope to use a class of degrees every member of which bounds an r.e. degree as a stepping stone to a definition of the (double) jump. A natural definable candidate for such a class is C_{ω} as it is known to contain all the n-REA degrees (Shore and Slaman [2001] but not known to contain any other degrees. (The 1-REA degrees are the r.e. degrees and the (n+1)-REA degrees are those that are REA in an n-REA degree. So all of them bound an r.e. degree.)

Conjecture 7.4. C_{ω} is the union over n ∈ ℕ of the n-REA degrees and indeed for any a C_{ω}^{a} = {{x ≥ a|(∀z ≥ a)(z ∨ x is not a minimal cover of z} is the union of the degrees n-REA in a.

Proposition 7.5. If this conjecture holds then we can define the double jump of h as ∨T^{h} where T^{h} = {x ≥ h|(∃z ∈ C_{ω}^{h})[(∀u < v ≤ z)(u ≥ h → u ∨ x < v ∨ x) & ∀a, c(Cd(x ∨ z, a, c) → (∀y ∈ C_{ω}^{h})(∃ã, c̃)(Cd(y, ã, c̃) & Eq(a, c, ã, c̃)]}. Moreover, the relation x ∈ T^{h} is Σ_{5} and so the resulting definition of the relation h′′ = w is Π_{6}. This then would give a Π_{7} definition of x′ = w in the language with ≤, ∨ and ∧.

Proof. First, if x ∈ T^{h} let z be its witness and let h ≤ u < v ≤ z be such that v is r.e. in u. Thus u ∨ x < v ∨ x and v ∨ x is r.e. in u ∨ x. By the Theorem 7.3, every Σ_{3}^{V ⊕X} set S is coded below v ∨ x. By the definition of T^{h}, S is coded below every y ∈ C_{ω}^{h}. Now choose y to be REA in h with h′ = y′. Thus S ∈ Σ_{3}^{Y} = Σ_{3}^{H} and so (v ∨ x)′′ ≤ h′′ and so a fortiori x′′ ≤_{T} h′′.

On the other hand, consider any z ∈C_{ω}^{h} with z REA in h and h′ = z′. Let x be any set 2-generic with respect to z so that (∀u < v ≤ z)(u ≥ h → u ∨ x ∨ h < v ∨ x ∨ h) and also (x ∨ h ∨ z)′′ = (x ∨ h)′′ = z′′. Thus every S coded below x ∨ h ∨ z is Σ_{3}^{A} and coded below every y ∈ C_{ω}^{h} and so x ∈ T. As z′′ = h′′ is the join of two degrees x_{1} and x_{2} each 2-generic with respect to z, both x_{1} ∨h and x_{2} ∨h are in T^{h} and so h′′ = ∨T^{h} as desired.

We leave the quantifier counting as an exercise given the information already in §6.

A very interesting problem is to attack this issue from the other end and put lower bounds on the complexity of such definitions. Some beginnings to this approach are in Lerman and Shore [1988] who show, for example, that no nonzero degree has a Σ_{2} definition in D. We offer one more such example in the style of that paper that shows that, for at least one of our definitions, the gap between what we have and what is possible is not too large. By Lemma 6.12 L_{2} = {x|x′′ = 0′′} = {x|∀v(x′′ ≤ v′′)} is Π_{6} in the language with just ≤. We show that it is neither Π_{2} nor Σ_{2}.

Proposition 7.6. There is no Π_{2} or Σ_{2} definition in D (with just ≤) of L_{2} (or of L_{2}(y) by relativization).

Proof. Suppose, for the sake of a contradiction to the assumed existence of a Π_{2} definition of L_{2}, that x ∈ L_{2} ⇔ ∀v⃗∃u⃗θ(x, v⃗, u⃗). Choose a minimal degree x_{1} ∈ L_{2} such that there are extensions of [0, x] to initial segments realizing all possible uppersemilattices of size at most 2^{|v⃗|+2} with x as a minimal element. (Clearly there is a finite lattice containing copies of each such extension of a single minimal element as an initial segment. Choose a realization of this lattice inside L_{2} by Lerman [1983] and take the degree corresponding to the single distinguished minimal element as x.) Now choose an x_{2} ∉ L_{2} and witnesses v⃗_{2} such that ¬∀v⃗∃u⃗θ(x_{2}, v⃗, u⃗). Consider the uppersemilattice U generated in D by x_{2} and v⃗_{2}. Now take a realization of U as an initial segment extending x_{1} and let its elements corresponding to v⃗_{2} be v⃗_{1}. As x_{1} ∈ L_{2}, there are degrees u⃗_{1} such that θ(x, v⃗_{1}, u⃗_{1}). As v⃗_{1} generates an usl initial segment, the degrees in u⃗_{1} consist of members of this initial segment (i.e. joins of some of the v⃗_{1}) plus an end extension of it. For those i such that u_{1,i} is a join of elements of v⃗_{1} take as u_{2,i} the corresponding join of elements of v⃗_{2}. All the others form a partial order end extension of the initial segment realization of U. By the usual Kleene-Post construction, there is an isomorphic end extension in D of the usl generated by x_{2} and v⃗_{2}. Use such an extension to define the remaining u_{2,i} and note that we now have constructed witnesses u⃗_{2} such that θ(x_{2}, v⃗_{2}, u⃗_{2}) for the desired contradiction.

To consider a proposed Σ_{2} definition of L_{2} and so a Π_{2} one ∀v⃗∃u⃗θ(x, v⃗, u⃗) for L̄_{2}, just interchange the roles of L_{2} and L̄_{2} by choosing x_{1} and its extensions as initial segments of D not in L_{2} (e.g. not below 0′′). Now choose x_{2} ∈ L_{2} and appropriate witnesses v⃗_{2} such that ¬∀v⃗∃u⃗θ(x_{2}, v⃗, u⃗) and continue on as above to get witnesses u⃗_{2} such that θ(x_{2}, v⃗_{2}, u⃗_{2}) for the desired contradiction.

Finally, the major global fact about D not addressed by our results is that it has at most countably many automorphisms (Slaman and Woodin [2008]). We ask for a local version:

Question 7.7. Does every jump ideal of D have at most countable many automorphisms?

We note that a positive answer would have Slaman and Woodin’s result as a corollary. First a lemma.

Lemma 7.8. The following conditions are equivalent:

1. There are at most countably many automorphisms of D.

2. There is a countable automorphism base for D, i.e. a countable set A of degrees such that any two automorphisms of D that agree on A are identical.

3. There is a finite automorphism base for D.

Proof. (1) ⇒ (2): Suppose {φ_{i}|i ∈ ℕ} lists all the automorphisms of D. Choose d_{i,j} for i ≠ j such that φ_{i}(d_{i,j}) ≠ φ_{j}(d_{i,j}). Clearly {d_{i,j}} is an automorphism base since any two distinct automorphisms must be φ_{i} and φ_{j} for some i ≠ j and so differ on d_{i,j}.

(2) ⇒ (3): As pointed out in Odifreddi and Shore [1991], Slaman-Woodin coding shows that the restriction of any automorphism φ to the degrees below any x is determined by the action of φ on finitely many parameters which are arithmetic in x.

(3) ⇒ (1): Any automorphism takes the members of the finite base to degrees of the same arithmetic degree by Jockusch and Shore [1984] (indeed to ones below their join with 0′′ as all degrees above 0′′ are fixed under all automorphisms). Thus there are only countably many possible images for this base and so only countably many automorphisms.

Proposition 7.9. If every countable jump ideal which is sufficiently large (i.e. contains some fixed degree h) or sufficiently closed (i.e. closed under the ω-jump or any other fixed function F on D) has at most countably many automorphisms then so does D.

Proof. As we know, every automorphism of D restricts to an automorphism of each jump ideal I. Now note that if a countable jump ideal I (containing h or closed under F) is not an automorphism base and φ is an automorphism of D then there is another automorphism ψ of D that agrees with φ on I: If ρ and τ are any distinct automorphisms that agree on I, then ρ^{−1}τφ is the desired ψ. Next we can choose a degree d on which φ and ψ differ. With this procedure as the basic step and the assumption that no countable ideal is an automorphism base, we can start with I_{−1} = I and any automorphisms φ = φ_{∅} and build a binary tree with a degree d_{σ} at each node and a nested sequence of jump ideals I_{n} (closed under F) for each level n of the tree such that, for every string σ, d_{σ} ∈ I_{|σ|} and there are automorphisms φ_{σ} of D such that φ_{σˆ 0} and φ_{σˆ 1} differ at d_{σ} but agree on I_{|σ|−1}. Now consider the jump ideal I_{ω} = ∪I_{n} which contains h (and is closed under F). For every P ∈ 2^{ω} the function ∪{φ_{σ} ↾ I_{|σ|−1}|σ ⊂ P } is an automorphisms of I_{ω} and they are all distinct for the desired contradiction to our assumption that no such countable jump ideal is an automorphism base. Thus, by the Lemma, there are at most countably many automorphisms of D.

8 Bibliography

Cooper, S. B. [1990], The jump is definable in the structure of the degrees of unsolvability (research announcement), Bull. Am. Math. Soc. 23, 151-158.

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

Cooper, S. B. [2001], On a conjecture of Kleene and Post. Math. Log. Q. 47, 3–33. Downey, R. G., Jockusch, C. G. Jr. and Stob, M. [1990], Array nonrecursive sets

and multiple permitting arguments, in Recursion Theory Week, K. Ambos-Spies, G. H. Müller and G. E. Sacks eds., Springer-Verlag, Berlin, 141-174.

Greenberg, N. and Montalbán, A. [2004], Embedding and coding below a 1-generic degree, Notre Dame J. Formal Logic 44, 200-216.

Harrington, L. and Kechris, A. S. [1975], A basis result for Σ_{3}^{0} sets of reals with an application to minimal covers, Proc. Am. Math. Soc. 53, 445-448

Harrington, L. and Shore, R. A. [1981], Definable degrees and automorphisms of D, Bul. Am. Math. Soc. (NS) 4, 97-100.

Jockusch, C. G. Jr. [2002], review of Cooper [2001], Math. Rev. MR1808943 (2002m:03061).

Jockusch, C. G. Jr. and Shore, R. A. [1984], Pseudo-jump operators II: transfinite iterations, hierarchies and minimal covers, J. Symb. Logic 49, 1205-1236.

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

Jockusch, C. G. Jr. and Soare, R. I. [1970], Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25, 856-859.

Jockusch, C. G. Jr. and Solovay, R. M., [1977], Fixed points of jump preserving automorphisms of degrees, Israel J. Math. 26, 91-94.

Jónsson, B. [1953] On the representations of lattices, Math. Scand. 1, 193-206. Kleene, S. C. and Post, E. L. [1954] The upper semi-lattice of degrees of recursive

unsolvability, Ann. of Math. (2) 59, 379–407.

Lachlan, A. [1966], Lower bounds for pairs of recursively enumerable degrees, Proc. Lon. Math. Soc. 16(3), 53-569.

Lerman, M. [1971], Initial segments of the degrees of unsolvability, Ann. Math. 93, 365-89.

Lerman, M. [1983], Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

Lerman, M. and Shore, R. A. [1988], Decidability and invariant classes for degree structures, Trans. Am. Math. Soc. 310, 669-692.

Nies, A., Shore, R. A. and Slaman, T. [1998], Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical Society (3) 77, 241-291.

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

Sacks, G. E. [1963], Recursive enumerability and the jump operator, Trans. Am. Math. Soc. 108, 223-239.

Selman, A. L. [1972], Applications of forcing to the degree theory of the arithmetic hierarchy, Proc. Lon. Math. Soc. 25,586-602.

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

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

Shore, R. A. [2006], Degree Structures: Local and Global Investigations, Bulletin of Symbolic Logic, 12, 369-389

Shore, R. A. [2008], Rigidity and biinterpretability in the hyperdegrees, in Computational Prospects of Infinity, Part II: Presented Talks, C. T. Chong, F. Qi and Y. Yang eds., Lecture Note Series, Institute for Mathematical Sciences, National University of Singapore 15, World Scientific Publishing Co., Singapore.

Shore, R. A. and Slaman, T. A. [1999], Defining the Turing jump, Math. Research Letters 6 (1999), 711-722.

Shore, R. A. and Slaman, T. A. [2001], A splitting theorem for n-REA degrees, Proc. Am. Math. Soc. 129, 3721-3728.

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

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

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

Slaman, T. A. and Woodin, H. W. [2008], Definability in degree structures, J. Math. Logic, to appear.