Local definitions in degree structures: the Turing jump, hyperdegrees and beyond

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

February 27, 2007

Abstract

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. On the other hand, no Π_{2} or Σ_{2} formula in the language with just ≤ defines L_{2} or x ∈ 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 that is invariant under double jump or joining 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. Similar direct coding arguments show that every hyperjump ideal I is rigid and biinterpretable with second order arithmetic with set quantification ranging over sets with hyperdegrees in I. Analogous results hold for various coarser degree structures.

1 Introduction

1.1 The Turing degrees

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 the required notion of sufficiently large has undergone a series of successive weakenings. These results have been intimately connected with the analysis of possible automorphisms of D. The corresponding trend here has been that all automorphisms are fixed on every sufficiently large degree. 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, the output, A′, of this operator corresponds to definability in arithmetic (extended by a predicate for membership in A) by formulas with only one quantifier. Its n^{th} iterate A^{(n)} corresponds to definability by such formulas with n alternations of 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 m is a minimal cover of z if z < m and there is no degree strictly between m and z.) It 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 for those 2-REA operators that correspond to constructions of d-r.e. sets, i.e. ones of the form A − B for A and B r.e. This theorem was like similar ones proven in Jockusch and Shore [1984]. The second ingredient 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). The specific property that Cooper claimed held of some d-r.e. degree but of no r.e. one turned out not to hold of any n-REA degrees for any n < ω (Shore and Slaman [2001]). As every d-r.e. degree is 2-REA, Cooper’s proposed formula did not define the jump operator.

The jump was then proven definable by Shore and Slaman [1999]. (After seeing the counterexample of Slaman and Shore [2001], Cooper changed his definition to a more complicated one that was also shown to have the same flaw (Shore and Slaman [2001a]). He then changed his definition to a still more complicated one (Cooper [2001]) for which there is as yet no counterexample but the list of requirements for his construction even, if successfully satisfied, would not suffice to construct the required set (Jockusch [2002]).) Again, the ingredients of the definition of Shore and Slaman 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 its definability followed from much earlier work of Slaman and Woodin. Although not specifically mentioned 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 is definable in D. The definition requires their entire machinery to internalize their analysis of automorphisms of D within D itself (by coding models of arithmetic and transferring the discussion to the codes). 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 [2007]. 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′′. By their set theoretical nature and the uses of absoluteness, these arguments gave no local information about D (i.e. about the structure of (countable) ideals of D) either in terms of definability or automorphisms.

We provide a direct definition of the jump operator that uses no metamathematical or set theoretic methods. 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)}}. 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 2.2, 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 2.3, calculates the infimum of the double jumps of degrees in C (or 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^{(ω)}. (A jump ideal is a subset of D closed downward and under join and jump.) Even within all of D, our definitions seem significantly simpler than the previous one both conceptually and in terms of quantifier complexity.

Theorem 1.1. There are Π_{5} formulas in the language with ≤, ∨ and ∧ that define the relations x ∈ L_{2}(y), i.e. x ≥ y&x′′ = y′′, x′′≤ y′′and x′′ = y′′ in any jump ideal of D containing 0^{(ω)}. There are ones defining w = x′′ and w = x′ that are Σ_{6}&Π_{6} and Π_{8}, respectively. In the language without ∨ and ∧ the definitions are one level higher up in quantifier complexity.

As a beginning of the investigation of lower bounds for the complexity of such definitions, we show that there is no definition of L_{2} = {x|x′′ = 0′′} or x ∈ L_{2}(y) which is either Π_{2} or Σ_{2} in the language with just ≤. This proof uses the methods and results of Lerman and Shore [1988].

Once we have an independent definition of the (double) jump we can also directly and simply derive the results of Slaman and Woodin [2007] on fixed points of automorphisms and definability and extend them to all jump ideals containing 0^{(ω)}:

Theorem 1.2. If I is any jump ideal in D with 0^{(ω)} ∈ I and φ is any automorphism of I then φ(x) = x for every x ≥ 0′′. Moreover, any relation R on I invariant under the double jump (i.e. if x′′_{i} = y′′_{i} then R(x⃗) ⇔R(y⃗)) 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 hyperdegrees 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.

1.2 The hyperdegrees and beyond

Slaman [1991] points out that the set theoretic and metamathematical methods of Slaman and Woodin [2007] apply to a wide array of degree structures, often giving stronger results based on specific special properties of the reducibility. For example, in the arithmetic degrees, D_{a}, every automorphism is the identity on the degrees above 0^{(ω)}, the first arithmetic jump of 0, while the hyperdegrees D_{h} are rigid and biinterpretable with second order arithmetic. Thus every relation on D_{h} is definable if and only if it is definable in second order arithmetic.

(We say that X is arithmetic in Y, X ≤_{a} Y, if X ≤_{T} Y^{(n)} for some n ∈ ω and X is hyperarithmetic in Y, X ≤_{h} Y, if X ≤_{T} Y^{(α)} for some ordinal α recursive in Y where Y^{(α)} is the α^{th} iterate of the Turing jump applied to Y. Kleene showed (see Sacks [1990, II.1-2]) that X ≤_{h} Y if and only if X is Δ_{1}^{1}(Y). A degree structure D is biinterpretable with second order arithmetic if there is a definable standard model of arithmetic (or class of structures all isomorphic to ℕ) with definable schemes for both quantification over subsets of the model and a relation matching degrees with (codes for) sets in the model which are of the specified degrees. Of course, this immediately gives the desired result on definability of relations on D. See Slaman and Woodin [2007] for more details.)

We provide a proof that D_{h} is rigid by a direct coding argument similar to those we use for the definability of the Turing jump. Along with the analog for D_{h} of Slaman and Woodin [1986] coding, this gives a direct proof of the biinterpretability of D_{h} with second order arithmetic and so the definability (in D_{h}) of all relations (on D_{h}) definable in second order arithmetic. As in the analysis for D, the results all localize:

Theorem 1.3. Every hyperjump ideal I of D_{h} is rigid. Moreover, I (with ≤_{h}) is biinterpretable with second order arithmetic with quantification ranging over sets with hyperdegrees in I. So, in particular, any relation on I 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.

Another view of the hyperarithmetic sets sees them as the subsets of ω constructed in Gödel’s L before the first nonrecursive ordinal, ω_{1}^{CK}. In this view, we see X as hyperarithmetic in Y if X ∈ L_{ω}_{1}^{Y} [Y], i.e. X is constructed before the first ordinal not recursive in Y with the use of a predicate for Y in the language. This view of ≤_{h} has a natural generalization when one sees ω_{1}^{CK} as the first Σ_{1} admissible ordinal and L_{ω}_{1}^{CK} as the least admissible set containing ω. The relativization sees L_{ω}_{1}^{Y} [Y] as the least Σ_{1} admissible set containing Y. The suggested reducibility generalizes Σ_{1} to Σ_{n} and we say that X ≤_{Σ_{n}} Y if X is a member of the least Σ_{n} admissible set containing Y. The associated degrees are called the Σ_{n}-admissible degrees in Slaman [1991]. Our methods apply and results analogous to those for ≤_{h} all hold for these reducibilities and the associated degree structures as well. Similar results for the degrees of constructibility (under mild set theoretic hypotheses) are in Abraham and Shore [1986].)

2 Overview of the Proofs

The crucial idea for both degree structures is that we can characterize a degree x (precisely for D_{h} or up to some approximation for D) by the (sets coded in) lattices that can be embedded “near” x. To do this we must code as much as possible in as easily decodable a fashion as we can. In both degree structures, the starting point is the coding of sets in effective successor models of ℕ introduced in Shore [1981] to analyze the theory of the degrees below 0′. These codings live inside certain types of (partial) lattices with special elements designated by d_{0}, e_{0}, e_{1,}f_{0}, f_{1}, p and q. The basic fact we need about them is that they contain a sequence d_{n} of elements of order type ω generated by the special elements and that there is a uniformly recursive set of positive Σ_{1} formulas ϕ_{n}(x) (in the language with just ≤ and ∨ and parameters for the special elements) such that, in any lattice L with the specified structure, ϕ_{n}(x) holds of x if and only 0 < x ≤ d_{n}. The defining relations to generate the d_{n} are as follows:

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

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

In addition we require that p ≱ q and p ∨ d_{n} ≥ q for each n so that we can let the desired formulas ϕ_{n} be given as follows: ϕ_{0} is x = d_{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). An easy induction shows that ϕ_{n}(x) ⇔ 0 < x ≤ d_{n}.

We can now code a set X in such a lattice L_{X} by adding additional special elements that pick out the d_{n} such that n ∈ X. For D_{h} we require the lattice to have two additional parameters c and c̄ such that d_{n} ≤ c for n ∈ X, d_{n} ∧ c = 0 for n ∉ X, d_{n} ≤ c̄ for n ∉ X and d_{n} ∧ c̄ = 0 for n ∈ X. (So, in particular, ∃x(0 < x ≤ d_{n}, c) → d_{n} ≤ c and ∃x(0 < x ≤ d_{n}, c̄) → d_{n} ≤ c̄.)

For D we use exact pairs, i.e. additional elements g_{0} and g_{1} such that X = {n|d_{n} ≤ g_{0}, g_{1}} and to further simplify the picture by making the d_{n} an independent set we require for each n an element d̃_{n} of our lattice that is above all d_{m} for m ≠ n such that d_{n}∧d̃_{n} = 0. This also guarantees that ∃x(0 < x ≤ d_{n}, g_{0}, g_{1}) → d_{n} ≤ g_{0}, g_{1}.

In either case, n ∈ X just in case some positive Σ_{1} fact, ψ_{n}, (using only ≤ and ∨) holds in any such lattice L_{X}. For D_{h}, we also have the same property for X̄. Now the crucial facts about ≤_{T} and ≤_{h} are the complexity of these orderings restricted to the degrees below some Y. For ≤_{T} it is Σ_{3}^{Y} and for ≤_{h} it is Π_{1}^{1}(Y). Thus if f is an embedding of such an L_{X} in the Turing degrees below y then X ∈ Σ_{3}^{Y} and if the embedding is into the hyperdegrees below y then X, X̄ ∈ Π_{1}^{1}(Y) and so X ≤_{h} Y.

We next need lattice embedding theorems that allow us to embed various such L_{X} “near” the degree of X. We begin with the simpler case of D_{h}.

Theorem 2.1. If L is a (partial) lattice (with 0 and 1) hyperarithmetic in X then there is a lattice embedding of L in D_{h} that sends 0_{L} to deg_{h}(X) and 1_{L} to a degree below that of O^{X}, the complete Π_{1}^{1}(X) set which we call the hyperjump of X.

We now form a new lattice L_{X}^{∗} from two disjoint copies L_{X} and L̂_{X} of our original one described above by letting 1_{L_{X}^{∗}} be the join of 1_{L_{X}} and 1L̂_{X} and 0_{L_{X}^{∗}} be their infimum. Theorem 2.1 gives us an embedding f of L_{X}^{∗} into the hyperdegrees below O^{X} with least element x = deg_{h}(X). Consider now any automorphism π of any hyperjump ideal I containing x. As it is an automorphism, π carries the image of L_{X}^{∗} under f to another image πf(L_{X}^{∗}) in I. The coding scheme assumed above insures that x ≤_{h} πf(1_{L_{X}}), πf(1L̂_{X}). On the other hand, as f is a lattice embedding, x ≡_{h}f(1_{L_{X}}) ∧ f(1L̂_{X}) and so applying the automorphisms gives π(x) ≡_{h} πf(1_{L_{X}}) ∧ πf(1L̂_{X}). Thus x ≤_{h}π(x). The same argument applied to π^{−1} gives x ≤_{h}π^{−1}(x) and so π(x) ≤_{h} x. Thus x ≡_{h}π(x) for every automorphism π of I, i.e. I is rigid as required for Theorem 1.3. The conclusions about biinterpretability and definability in Theorem 1.3 now follow by adapting Slaman-Woodin [1986] coding to D_{h} and exploiting the power that this gives is to quantify over all countable relations to code standard models of arithmetic. Our proof of rigidity then gives a way of definably associating with a degree x the sets S coded in such a model that are of degree x. (Just say that they are of the same hyperdegree as the maximal one Z with lattices L_{Z}^{∗} as described with least element x.) Both Theorem 2.1 and the implementation of Slaman-Woodin coding are established by using Cohen-like forcing in the hyperarithmetic setting as introduced in Feferman [1965] and presented in Sacks [1990]. The former runs along the lines of Shore [1982] and the latter along those of Slaman and Woodin [1986] (both for D). This completes our outline of the proof of Theorem 1.3.

Turning now to D and the definition of the Turing jump, our penultimate goal (as mentioned above) is to define the relation x′′ ≤ y′′ from C (and from C′). 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′′)}.

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 and 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 the special parameters below x are also coded with the special parameters below y. This will then say that Δ_{3}^{X} ⊆ Δ_{3}^{Y} and so x′′ ≤ y′′ as desired.

The first tool needed to carry out this plan is the coding of sets by exact pairs in effective successor models of ℕ described above. Here the relevant notion of “near x” is “below x”. The crucial fact about the coding is that any set S coded in this way below a degree x is Σ_{3}^{X}. Thus, if both S and S̄ are coded below x, then S ∈ Δ_{3}^{X}, i.e. S ≤_{T} x′′. Of course, we cannot do the coding below every degree so we will need membership in our class to imply that we can do enough coding. We show that being contained in ANR is sufficient.

Theorem 2.2. 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_{3} ≤_{T} x that form a minimal pair for the ideal generated by {d_{n}|n ∈ S̃}.

The proof combines methods from Shore [1981] and [1982] along with those for working below an ANR degree of Downey, Jockusch and Stob [1990].

The second tool that we need is the coding of Slaman and Woodin [1986]. Given their method 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 comparisons relations between parameters below x and ones below y that say that they code the same set.

Given these two ingredients of (effective) coding and comparison, our plan is to (definably in a class 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). 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. We can now define the relation x′′ ≤_{T} y′′ from any class C^{∗} with Properties 1 and 2 by saying that S(x) ⊆ S(y˙) (using Slaman-Woodin coding to make the comparisons).

As every degree x ∈C is obviously not in GL_{2} (i.e. x′′ ≰_{T} (x ∨ 0′)′), \overline{GL}_{2} ⊆ ANR (Downey, Jockusch and Stob [1990]) and ANR is closed upward by definition, Theorem 2.2 shows that both C and C′ have Property 1.

We next prove that these classes have Property 2:

Theorem 2.3. 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′.

The proof here is by a quite ad hoc forcing construction. 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).

We build two (related but not fully mutually generic) generic sequences p_{i} and let our desired sets A_{i} be X ⊕ G_{i} where G_{i} = ∪σ_{p_{i}}.The intuition behind the notion of forcing is that once j ∈ F_{p} no more numbers in column j can be put into G_{i} and so G_{i}^{[j]} = {x| ⟨j, x⟩ ∈ G_{i}} 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_{i} is even slightly generic, G_{i}^{[j]} will be infinite. This allows us to directly control these individual Σ_{2}/Π_{2} alternatives and so diagonalize A_{i}^{(3)} against any ϕ_{e}^{(A_{i}⊕0^{(n)})′′} by making some G_{i}^{[j]} infinite for a large j and so some Σ_{3} fact about A_{i} true while preserving all the two quantifier facts about A_{i} ⊕0^{(n)} needed to force the value of ϕ_{e} at the appropriate number. This puts our sets in C. The infimum of the A′′_{i} is controlled by a Kleene-Post minimal pair type argument but at a higher level. Thus the construction is a combination of an effective forcing argument and a wait and see one.

Thus the Turing double jump and so single jump is definable from both C and C′. Indeed, they are definable from any class of degrees having Properties 1 and 2. All the standard jump classes from \overline{GL}_{2} to GH_{3} have both but we still have no direct definition for any or them. We can, however, define our new variation C on the classical jump classes (and so C′ as well). We do so in terms of the class C_{ω} = {x|(∀z)(z ∨ x is not a minimal cover of 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. As a notational convenience we use set parameters and quantification over them to replace the coding formulas in terms of the special parameters and quantification over them. In particular we say that a set S is coded below a degree x to mean that all the parameters needed to code the set can be taken to be below x.

Theorem 2.4. 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}_{2} ⊆ 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.

This concludes our outline of the definability of the Turing jump. The precise calculations of the complexity of this and other definitions provided in Theorem 1.1 require further analysis and some extra effort. The derivation of Theorem 1.2 from the definability results follows a fairly standard route. The ideas for fixing automorphisms 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].

In our setting, for the 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 claim about definability, we note that, as in D_{h}, using the coding of Slaman and Woodin [1986] we can definably in I 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 Questions

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

A very interesting problem is to attack this issue from the other end and put lower bounds on the complexity of such definitions. We begin this analysis by extending a results of Lerman and Shore [1988] that no nonzero degree has a Σ_{2} definition in D.

Proposition 3.3. There is no Π_{2} or Σ_{2} definition in D (with just ≤) of L_{2} or x ∈ L_{2}(y).

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

Question 3.4. 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.

Proposition 3.5. If every sufficiently large, i.e. containing some fixed degree, or sufficiently closed, i.e. closed under the ω-jump or any other fixed function F on D, countable jump ideal has at most countably many automorphisms then so does D.

Of course, the major issue for D is whether our results can be improved more drastically by, for example, lowering the base of the cone fixed under all automorphisms.

Question 3.6. Are all degrees above 0′ or even 0 fixed under all automorphisms of D or of even of every jump ideal I?

In the former case, we would expect our results on definability to extend to the degrees above 0′. In the latter, D is rigid and so by Slaman and Woodin [2007] biinterpretable with second order arithmetic. We expect that any direct proof of either result on automorphisms would also directly give the ones on definability and biinterpretability for both D and every appropriate jump ideal.

Finally, we ask if our methods (or others) avoiding set theoretic and metamathematical arguments can be applied to other reducibility orderings. In particular, the case of the arithmetic degrees D_{a} seems the most intriguing.

Question 3.7. Is there a direct proof that the arithmetic jump is definable in D_{a}, the cone above the arithmetic degree of 0^{(ω)} is fixed under all automorphisms of D_{a} and every relation on arithmetic degrees above that of 0^{(ω)} (or invariant under the arithmetic jump) is definable over D_{a} if and only if it is definable in second order arithmetic and there are at most countably many automorphisms of D_{a}? Do the analogs of all (any) of these results hold for every (sufficiently large) arithmetic jump ideal?

Question 3.8. Is D_{a} rigid and hence biinterpretable with second order arithmetic? Is every (sufficiently large) arithmetic jump ideal rigid and biinterpretable with second order arithmetic with quantification over sets with degrees in the ideal?

4 Bibliography

Abraham, U. and Shore, R. A. [1986], The degrees of constructibility below a Cohen real, J. London Math. Society (3) 53, 193-208

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.

Feferman, S. [1965], Some applications of the notion of forcing and generic sets, Fund. Math. 56, 325-45.

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.

Kleene, S. C. and Post, E. L. [1954] The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379–407.

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

Sacks, G. E. [1990], Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

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

Shore, R. A. and Slaman, T. A. [2001a], A discrete splitting theorem for n-REA degrees, http://www.math.cornell.edu/˜ shore/papers/pdf/dsplit5.pdf .

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. [2007], Definability in degree structures, J. Math. Logic, to appear.