Defining the Turing Jump

Richard A. Shore^{∗} Theodore A. Slaman^{†}

Cornell University Ithaca, NY 14853 USA

University of California, Berkeley Berkeley, CA 94720-3840 USA

1 Introduction

The primary notion of effective computability is that provided by Turing machines (or equivalently any of the other common models of computation). We denote the partial function computed by the eth Turing machine in some standard list by φ_{e}. When these machines are equipped with an “oracle” for a subset A of the natural numbers ω, i.e. an external procedure that answers questions of the form “is n in A”, they define the basic notion of relative computability or Turing reducibility (from Turing (1939)). We say that A is computable from (or recursive in) B if there is a Turing machine which, when equipped with an oracle for B, computes (the characteristic function of) A, i.e. for some e, φ_{e}^{B} = A. We denote this relation by A ≤_{T} B which we read as A is (Turing) reducible to B or A is recursive (computable) in B. This relation is transitive and reflexive and so induces an equivalence relation ≡_{T} (A ≡_{T} B ⇔ A ≤_{T} B ∧ B ≤_{T} A) and a partial order also denoted by ≤_{T} on the equivalence classes. These equivalence classes are called (Turing) degrees and the equivalence class of a set A ⊆ ω is called its degree. It is typically denoted by a or deg(A).

∗Partially supported by NSF Grant DMS-9802843.

†Partially supported by NSF Grant DMS-97-96121.

The structure D of these degrees has been the object of extensive study over the past fifty or sixty years. (A survey from the early 80s is Shore (1985). Current ones can be found in Griffor (1999).) A central concern in this research over the past twenty 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. (See, for example, Shore (1985) and Slaman (1991).) 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. The first example of what might be considered a natural definition of such a relation which also does not appeal to the general theorems appears in Jockusch and Shore (1984). They define A, the degrees of the arithmetic sets, i.e. those sets definable in arithmetic with quantification only over numbers, in order-theoretic terms within D.

The overarching goal of these investigations has been the definition of the (Turing) jump operator. The (Turing) jump A′ of A ⊆ ω is the halting problem for machines with an oracle for A: A′ = {e| the eth machine with oracle A halts on input e}. So, in particular, 0′ is the degree of the halting problem. (We use 0 for the empty set and so its degree 0 is the degree of the computable sets.) The undecidability of the halting problem says, when relativized to A, that A <_{T} A′ for every A. As the jump is easily seen to be well defined on degrees, it induces a strictly increasing operation on D taking a = deg(A) to a′ = deg(A′). By classical results of Kleene and Post, this operator 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)})}. 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.

Cooper (1990) argued for the definability of the jump along the lines of the definition of A provided by Jockusch and Shore (1984). We outline the plan of the proof of the definability of A so as to be able to both describe Cooper’s proposal and present our own proof, as all of them follow the same general plan. Jockusch and Shore (1984) argued for the definability of A in D by combining a completeness and join theorem for certain operators with known structural results for D and the r.e. degrees. (The recursively enumerable or r.e. sets are those that can be enumerated by a partial recursive function φ_{e} or, equivalently those that are the domain of such a function. In the relativized case we denote the eth set r.e. in A by W_{e}^{A}. It is the domain of φ_{e}^{A}. The r.e. in A degrees are those of the sets W_{e}^{A}.) We begin with the natural order-theoretic properties crucial to this definition of A and the definition itself.

Definition 1.1 A degree a is a minimal cover if there is a b such that a > b and there is no c strictly between a and b. If b is such a degree for a we say that a is a minimal cover of b.

Definition 1.2 C_{ω} = {c|∀z(z ∨ c is not a minimal cover of z}. \overline{C}_{ω} = \{d|∃c ∈C_{ω}(d ≤ c)\}.

Theorem 1.3 (Jockusch and Shore (1984)) A = \overline{C}_{ω} and the relation a is arithmetic in b is definable in D (by the relativization of the definition of A to b).

We next define the operators on sets needed for the analysis. We restrict ourselves here to the case that α ≤ ω but both of the following definitions have been usefully generalized into the transfinite and the corresponding theorems proven.

Definition 1.4 The 1 − REA operators J (from 2^{ω} to 2^{ω}) are those of the form J(A) = J_{e}(A) = A ⊕ W_{e}^{A}. The n − REA operators J are those of the form J_{⟨e_{1},... ,e_{n}⟩} = J_{e_{n}} ∘ J_{e_{n−1}} ∘ … ∘ J_{e_{1}}. The ω − REA operators J are those of the form J(A) = ⨁{J_{f↾n}(A)|n ∈ ω} for some recursive f.

Definition 1.5 The n − r.e. operators J are those of the form J(A)(x) = lim φ_{e}^{A}(x, s) for a (total recursive in A) function φ_{e}^{A} which has φ_{e}^{A}(x, 0) = 0 for all x and for which there are at most n many s such that φ_{e}^{A}(x, s) ≠ φ_{e}^{A}(x, s + 1). The ω − r.e. operators J are those of the form J(A)(x) = lim_{s→∞} φ_{e}^{A}(x, s) for a (total recursive in A) function φ_{e}^{A} which has φ_{e}^{A}(x, 0) = 0 for all x and for which there are at most f(x) many s such that φ_{e}^{A}(x, s) ≠ φ_{e}^{A}(x, s + 1) for some recursive function f.

Now for the completeness theorem needed.

Theorem 1.6 (Jockusch and Shore (1984)) For any α−REA operator J and any C ≥_{T} 0^{(α)} there is an A such that J(A) ≡_{T} C.

An improvement to the completeness theorem that includes a join operation provides an approach to the first natural definability result for D.

Theorem 1.7 (Jockusch and Shore (1984)) For any ω−r.e. operator J and any nonarithmetic D there is an A such that J(A) ≡_{T} D∨0^{(ω)} ≡_{T} D∨A.

It is now the minimal degree construction of Sacks (1963)) that provides the operator relevant to the definition of A.

Theorem 1.8 (Sacks (1963)) There is an ω − r.e. operator J such that deg J(A) is a minimal cover of deg A for every A.

Thus for every nonarithmetic degree x there is a z such that x ∨ z is a minimal cover of z. On the other hand, for all n, 0^{(n)} ∨ z is not a minimal cover of z for any z by Jockusch and Soare (1970). This establishes Theorem 1.3.

Cooper (1990) suggested a similar approach to the problem of defining the jump operator. His plan was to use a version of Theorem 1.7 for 2 − r.e. operators to define 0′ by finding a suitable 2 − r.e. operator that would produce a degree with an order-theoretic property that no r.e. degree could have (again even relative to any degree below it). He defined the following notions and classes.

Definition 1.9 d is splittable over a avoiding b if either a, b ≰ d or b ≤ a or there are d_{0}, d_{1} such that a <_{T} d_{0}, d_{1} <_{T} d, d_{0} ∨ d_{1} = d and b ≰_{T} d_{0}, d_{1}. C_{1} = {c|∀a, b(a ∨ c is splittable over a avoiding b}. \overline{C}_{1} = \{d|∃c ∈C_{1}(d ≤_{T} c)\}.

Now, one of the needed results was already well known.

Theorem 1.10 (Sacks (1963)) Every r.e. degree d is in C_{1}.

For the other direction Cooper (1990) claimed as his Main Theorem that there is a suitable 2 − r.e. set and so a 2 − r.e. operator J such that for every C there are a and b such that d ≡_{T} deg(J(C)) is not splittable over a avoiding b. This would have sufficed to define 0′ and so, by relativization, the jump operator itself. Cooper (1990) proposed to argue for the existence of such a 2 − r.e. set with a 0′′′ priority construction similar to that proving Lachlan’s (1975) Nonsplitting Theorem for the recursively enumerable degrees. However, the following theorem shows that there is no such set and so Cooper’s (1990) proposed property does not define the jump.

Theorem 1.11 (Shore and Slaman (n.d.)) Suppose that d, a, and b are Turing degrees such that a and b are recursive in d, b is not recursive in a, and d is n-REA relative to a. Then there are x and y such that x ∨ y = d, x ≥_{T} a and y ≥_{T} a, and x ≱_{T} b and y ≱_{T} b.

As Lachlan has proved that every 2−r.e. set is 2−REA (see Jockusch and Shore (1984) for a proof that every α − r.e. set is α − REA), Theorem 1.11 proves that there is no 2 − r.e. degree which fulfills Cooper’s requirements.

In our approach, we first prove a stronger version of Theorem 1.7 for all n − REA operators and so answer a question of Jockusch and Shore (1984).

Question 1.12 (Jockusch and Shore (1984)) Suppose that J is an n-REA operator and A is a subset of the natural numbers which is not Δ_{n}^{0}, i.e. not recursive in 0^{(n−1)}. Does there exist a G ⊆ ω such that A ⊕ G ≡_{T} J(G) ≡_{T} A ⊕ 0^{(n)}?

The case of this question for ω − REA operators (i.e. replace ω − r.e. by ω − REA in Theorem 1.7) was answered positively by Kumabe and Slaman. In Section 2, we provide an affirmative answer to Question 1.12.

Theorem 2.3 Suppose that n ≥ 1, J is an n-REA operator, and A ⊆ ω is not Δ_{n}^{0}. Then, there is a G ⊆ ω such that A ⊕ G ≡_{T} J(G) ≡_{T} A ⊕ 0^{(n)}.

The other half of our proof of the definability of the jump, however, comes from a quite different direction.

Theorem 1.13 (Slaman and Woodin (n.d.)) The double-jump which maps x to x′′ is definable in D.

Theorem 2.3 applies to all n-REA operators, and the double-jump is the canonical 2-REA operator. And so, we define 0′ in D.

Theorem 1.14 0′ is defined within D as the greatest degree z such that there is no g such that z ∨ g is equal to g′′.

Proof: Clearly no degree less than or equal to 0′ can join any g to g′′. Theorem 2.3 states that any degree not below 0′ does join some g up to g′′. Consequently, 0′ is definable in D in terms of join and the doublejump. The join is clearly definable in D and, by Theorem 1.13, so is the double-jump.

We can relativize the proofs of Theorem 2.3 and hence of Theorem 1.4. We then obtain the following definition of the function mapping x to x′ in D.

Theorem 1.15 For any degree x, x′ is definable from x within D as the greatest degree z such that there is no g greater than or equal to x such that z ∨ g is equal to g′′.

We end with some comments about the methods by which we prove these theorems and some comments about the problems which remain open.

Theorem 1.13 is proved by applying the Slaman and Woodin analysis of automorphisms of the Turing degrees. This analysis involves a fair amount of metamathematics, but not much technical recursion theory.

Note that it is not crucial that we have the definability specifically of the double jump as our starting point. Any definition of the (n + 1)st jump for any n ∈ ω would suffice. We can define the nth jump from the (n + 1)st using Theorem 2.3 in essentially the same way we defined the jump from the double jump in Theorem 1.15.

Theorem 2.3 is first proved in the special case of the n-fold iteration of the Turing jump in Theorem 2.1 using a sharp analysis of Kumabe and Slaman forcing. We give this analysis in Section 2. The general case follows from Theorem 2.2, the Jockusch and Shore (1984) Inversion Theorem for n-REA operators.

Remarkably, one obtains the definitions of 0′ and of the jump presented in Theorems 1.14 and 1.15 without using even one priority construction.

This situation is an advantage in some contexts. Slaman and Woodin showed that the arithmetic jump is definable within the partial order of the arithmetic degrees. In that context, the priority method has limited utility.

However, there are disadvantages as well. For example, the Slaman and Woodin methodology depends on global properties of the degrees. It is open whether 0′ is definable within every ideal of D to which it belongs.

It has been common wisdom that, because of the intrinsic complexity of the relation of Turing reducibility itself, coding methods within the Turing degrees cannot resolve relations which are not invariant under the double jump. Though our definition of the jump is a counter-example to this belief, obtaining even finer resolutions is an open problem. For example, it is open whether the relation “x is REA in y” is definable in D.

2 n-REA Operators and Kumabe–Slaman Forcing 7

Another shortcoming of our proof is that Slaman and Woodin’s definition of the double jump involves an explicit translation of isomorphism facts to definability facts via a coding of (second order) arithmetic. Thus, the definition provided is not based on a naturally order-theoretic property of 0′. One can hope that the above open questions could also be resolved, if one could find a natural definition of the Turing jump. Here natural is meant in the sense that the defining property for A in Jockusch and Shore (1984) and the one proposed in Cooper (1990) for 0′ are natural order-theoretic ones.

2 n-REA Operators and Kumabe–Slaman Forcing

Theorem 2.1 Suppose that n ≥ 1 and A ⊆ ω is not Δ_{n}^{0}. Then there is a G ⊆ ω such that A ⊕ G, A ⊕ 0^{(n)} ≥_{T} G^{(n)}.

Before we give the proof of Theorem 2.1, we combine it with Jockusch and Shore’s (1984) inversion theorem for REA-operators (relativized) to provide a complete solution to Question 1.12.

Theorem 2.2 (Jockusch and Shore (1984)) Suppose that n ≥ 1, J is an n-REA operator, and K ≥_{T} H^{(n)}. Then there is a G such that G ≥_{T} H and J(G) ≡_{T} K.

Theorem 2.3 Suppose that n ≥ 1, J is an n-REA operator, and A ⊆ ω is not Δ_{n}^{0}. Then, there is a G ⊆ ω such that A ⊕ G ≡_{T} J(G) ≡_{T} A ⊕ 0^{(n)}.

Proof: By Theorem 2.1, choose H so that A ⊕ H, A ⊕ 0^{(n)} ≥_{T} H^{(n)}. By Theorem 2.2, choose G ≥_{T} H so that J(G) ≡_{T} A ⊕ H. But then A ⊕ G ≥_{T} A ⊕ H ≥_{T} J(G). Conversely, since J(G) ≡_{T} A ⊕ H, J(G) ≥_{T} A; since J is an n-REA operator, J(G) ≥ G; and so J(G) ≥ A ⊕ G. Thus, A ⊕ G ≡_{T} J(G), as required for the first equivalence. For the second, note that A ⊕ H ≡_{T} A ⊕ 0^{(n)} by our choice of H.

The remainder of this section is devoted to the proof of Theorem 2.1.

Definition 2.4 1. A Turing functional Φ is a set of sequences (x, y, σ) such that x is a natural number, y is either 0 or 1, and σ is a finite binary sequence. Further, for all x, for all y_{1} and y_{2}, and for all compatible σ_{1} and σ_{2}, if (x, y_{1}, σ_{1}) ∈ Φ and (x, y_{2}, σ_{2}) ∈ Φ, then y_{1} = y_{2} and σ_{1} = σ_{2}.

2. Φ is use-monotone if the following conditions hold.

(a) For all (x_{1}, y_{1}, σ_{1}) and (x_{2}, y_{2}, σ_{2}) in Φ, if σ_{1} is a proper initial segment of σ_{2}, then x_{1} is less than x_{2}.

(b) For all x_{1} and x_{2}, y_{2} and σ_{2}, if x_{2} > x_{1} and (x_{2}, y_{2}, σ_{2}) ∈ Φ, then there are y_{1} and σ_{1} such that σ_{1} ⊆ σ_{2} and (x_{1}, y_{1}, σ_{1}) ∈ Φ.

3. We write Φ(x, σ) = y to indicate that there is a τ such that τ is an initial segment of σ, possibly equal to σ, and (x, y, τ) ∈ Φ. If X ⊆ ω, we write Φ(x, X) = y to indicate that there is an ℓ such that Φ(x, X ↾ ℓ) = y, and write Φ(X) for the function evaluated in this way.

Note that in Definition 2.4, we do not require that Φ be recursively enumerable. Consequently, if Φ is a Turing functional and X ⊆ ω, then Φ(X) is recursive only in the join of Φ and X.

The following notion of forcing is due to Kumabe and Slaman, who used it to prove a version of Theorem 2.1 in which the nth jump is replaced by the ωth jump.

Definition 2.5 Let P be the following partial order.

1. The elements p of P are pairs (Φ_{p}, X_{p}) in which Φ_{p} is a finite usemonotone Turing functional and X_{p} is a finite collection of subsets of ω.

2. If p and q are elements of P, then p ≥ q if and only if

(a) i. Φ_{p} ⊆ Φ_{q} and

ii. for all (x_{q}, y_{q}, σ_{q}) ∈ Φ_{q} \ Φ_{p} and all (x_{p}, y_{p}, σ_{p}) ∈ Φ_{p}, the length of σ_{q} is greater than the length σ_{p},

(b) X_{p} ⊆ X_{q},

(c) for every x, y, and X ∈ X_{p}, if Φ_{q}(x, X) = y then Φ_{p}(x, X) = y.

In short, a stronger condition than p can add computations to Φ_{p}, provided that they are longer than any computation in Φ_{p} and that they do not apply to any element of X_{p}.

Definition 2.6 If Φ_{0} and Φ_{1} are finite use-monotone Turing functionals, then Φ_{0} ≥_{0} Φ_{1} if and only if (Φ_{0}, ∅) ≥ (Φ_{1}, ∅) in P.

If G ⊆ P is a (sufficiently, or indeed, even slightly) P -generic filter, then G is naturally associated with the functional Φ_{G} = ⋃{Φ_{p} : p ∈ G}. To prove Theorem 2.1, we will construct a G that is sufficiently P -generic so that every Σ_{n}^{0} statement about Φ_{G} is correctly decided by a condition in P that belongs to G. We will also show that it possible meet the relevant dense subsets of P and still arrange that Φ_{G}(A) is equal to the characteristic function of the complete Σ_{n}^{0} set relative to Φ_{G}. The total effect will be to ensure that Φ_{G}^{(n)} is recursive in the join of Φ_{G} and A

We will treat Φ_{G} as if it were a subset of ω and suppress the recursive apparatus needed to represent Φ_{G} in this way.

Lemma 2.7 Let p = (Φ_{p}, X_{p}) be an element of P.

1. p ⊩ a ∈ Φ_{G} if and only if a ∈ Φ_{p}.

2. p ⊩ a ∉ Φ_{G} if and only if

(a) either a is not a suitable triple,

(b) or a is equal to (x, y, σ), a ∉ Φ_{p}, and either

i. there is a (x_{0}, y_{0}, σ_{0}) ∈ Φ_{p} such that the length of σ_{0} is greater than the length of σ, or x_{0} is greater than or equal to x and σ_{0} is compatible with σ.

ii. or σ is an initial segment of one of the elements of X_{p}.

Proof: For the first claim, if a ∈ Φ_{p} then a ∈ Φ_{G} whenever p ∈ G. Consequently, if a ∈ Φ_{p} then p ⊩ a ∈ Φ_{G}. Conversely, if a ∉ Φ_{p} then let σ be a sequence such that σ has length greater than the length of any sequence mentioned in p or a and such that σ is incompatible with all of the elements of X_{p}. Let x be the least number such that Φ_{p}(x, σ) is not defined. Then q = (Φ_{p} ∪ {(x, 0, σ)}, X_{p}) extends p in P, a ∉ Φ_{p} ∪ {(x, 0, σ)} and no extension r of q can have a ∈ Φ_{r}. Consequently, q ⊩ a ∉ Φ_{G} and so p ⊮ a ∈ Φ_{G}. The proof of the second claim is similar. One observes that if conditions 2(a) and (b) do not hold, then it is possible to extend Φ_{p} to some Φ_{q} so that p ≥ (Φ_{q}, X_{p}) and a ∈ Φ_{q}.

Definition 2.8 Let Φ_{p} be a finite use-monotone Turing functional. Let ψ(Φ_{G}) = (∀m)θ(m, Φ_{G}) be a Π_{n}^{0} sentence about Φ_{G} in which θ(m, Φ_{G}) is Σ_{n−1}^{0}. For τ = (τ_{1}, …, τ_{k}) a sequence of elements of 2^{<ω} all of the same length, we say that τ is essential to ¬ψ(Φ_{G}) over Φ_{p} when the following condition holds. For all q and all m, if q is a condition such that (Φ_{p}, ∅) > q and q ⊩ ¬θ(m, Φ_{G}), then Φ_{q} \ Φ_{p} includes a triple (x, y, σ) such that σ is compatible with at least one component of τ.

Definition 2.9 For Φ_{0} a finite use-monotone Turing functional, and k in ω, let T (Φ_{0}, ψ, k) be the set of length k vectors τ which are essential to ¬ψ(Φ_{G}) over Φ_{0}.

We order T (Φ_{0}, ψ, k) by extension on all coordinates. That is, σ extends τ if and only if for all i less than or equal to k, the ith coordinate of σ extends the ith coordinate of τ. It is immediate that if σ extends τ and σ is essential to ¬ψ(Φ_{G}) over Φ_{0}, then τ is also essential to ¬ψ(Φ_{G}) over Φ_{0}. Consequently, T (Φ_{0}, ψ, k) is a subtree of the tree of length k vectors of binary sequences of equal length ordered as above. That is, T (Φ_{0}, ψ, k) is a subtree of a recursively bounded recursive tree. Here, a recursive tree T is recursively bounded if there is a recursive function t such that for all n, t(n) is a finite set which contains the nth splitting level of T.

Lemma 2.10 Suppose that Φ_{0} is a finite use monotone functional, ψ(Φ_{G}) is a Π_{n}^{0} sentence with n ≥ 1, and k is a natural number.

1. If there is a size k set X of subsets of ω such that (Φ_{0}, X) ⊩ ψ(Φ_{G}), then T (Φ_{0}, ψ, k) is infinite.

2. If T (Φ_{0}, ψ, k) is infinite, then it has an infinite path Y. Further, each such Y is naturally identified with a size k set X(Y) of subsets of ω such that (Φ_{0}, X(Y)) ⊩ ψ(Φ_{G}).

Proof: Say that ψ(Φ_{G}) is equal to (∀m)θ(m, Φ_{G}) where θ(m, Φ_{G}) is Σ_{n−1}^{0}. For the first claim, suppose there is a size k set X = (X_{1}, …, X_{k}) of subsets of ω such that (Φ_{0}, X) ⊩ ψ(Φ_{G}). Fix such an X and consider the set of sequences τ_{ℓ} = (X_{1} ↾ ℓ, …, X_{k} ↾ ℓ), as ℓ ranges over ω. For all q extending (Φ_{0}, ∅) and all m, if q ⊩ ¬θ(m, Φ_{G}), then q is incompatible with (Φ_{0}, X). In particular, (Φ_{q}, X_{q}∪X) does not extend (Φ_{0}, X) in P. But then, there must be an i such that Φ_{q} \ Φ_{0} contains an element (x, y, σ) such that X_{i} extends σ. This σ is compatible with the ith component of each τ_{ℓ}. Consequently, each τ_{ℓ} is essential to ¬ψ(Φ_{G}) over Φ_{0} and hence T (Φ_{0}, ψ, k) is infinite. This verifies the first claim.

For the second claim of the lemma, suppose that T (Φ_{0}, ψ, k) is infinite. By König’s Lemma, since T (Φ_{0}, ψ, k) is a finitely branching tree, it has at least one infinite path. Now suppose that Y is such an infinite path. Let X(Y) be the size k set {X_{1}, …, X_{k}} in which each X_{i} is the limit of the ith coordinates of the elements of Y. For every extension q of (Φ_{0}, ∅) and every m, if q ⊩ ¬θ(m, Φ_{G}) then Φ_{q} \ Φ_{0} includes an element (x, y, σ) such that σ is compatible with at least one component of each element of Y. But then, for all sufficiently large elements of Y, σ is extended by a coordinate of Y, and so σ is extended by at least one of the elements of X(Y). Thus, for all m, no extension of (Φ_{0}, X(Y)) can force ¬θ(m, Φ_{G}). Therefore, (Φ_{0}, X(Y)) ⊩ ψ(Φ_{G}), as required to verify the second claim.

Lemma 2.11 For each finite use monotone functional Φ_{0}, each Π_{n}^{0} sentence ψ(Φ_{G}) with n ≥ 1, and each number k, T (Φ_{0}, ψ, k) is Π_{n}^{0}, uniformly in Φ_{0}, ψ, and k.

Proof: First consider the forcing relation for sentences in which all of the quantifiers are bounded. Suppose ¬θ(Φ_{G}) is a bounded sentence about Φ_{G}. Applying Lemma 2.7, whether (Φ_{0}, X) ⊩ ¬θ(Φ_{G}) is a bounded property, given uniformly in terms of Φ_{0}, ¬θ(Φ_{G}), and X. Fix a bound m on the quantifiers in the formula which defines this property. Again, by referring to Lemma 2.7, if X_{0} is a subset of X such that for all X ∈ X, there is an X_{0} ∈ X_{0} such that X and X_{0} agree on the numbers less than m, then (Φ_{0}, X) ⊩ ¬θ(Φ_{G}) if and only if (Φ_{0}, X_{0}) ⊩ ¬θ(Φ_{G}). Since there are only finitely many incompatible binary sequences of length m, we can capture the possible behaviors of sets X by quantifying over the possible behaviors of subsets of the set of length m binary sequences. Consequently, uniformly in ¬θ, whether there is a finite set X such that (Φ_{0}, X) ⊩ ¬θ(Φ_{G}) is a bounded property given uniformly in terms of Φ_{0} and ¬θ(Φ_{G}).

We now prove Lemma 2.11 by induction on n. First consider the base case when n is equal to 1. That is ψ is of the form (∀x)θ(x, Φ_{G}) and θ(x, Φ_{G}) is bounded. Let k be fixed and suppose that τ is a length k sequence of elements of 2^{<ω} all of the same length. By Definition 2.8, τ is essential to ¬ψ(Φ_{G}) over Φ_{0} if and only if for all q ∈ P and all m ∈ ω, if (Φ_{0}, ∅) > q and q ⊩ ¬θ(m, Φ_{G}), then Φ_{q} \ Φ_{0} includes a triple (x, y, σ) such that σ is compatible with at least one component of τ. By the analysis of the forcing relation for bounded sentences, for each finite use-monotone functional Φ_{q}, whether there is a finite set X_{q} such that (Φ_{0}, ∅) > q and q ⊩ ¬θ(m, Φ_{G}) is a bounded property of Φ_{q} and m. Thus, the quantifier over q in P can be replaced by a quantifier over finite use-monotone functionals Φ_{q} with Φ_{0} ≥_{0} Φ_{q}. (See Definition 2.6.) Consequently, τ ’s being essential to ¬ψ(Φ_{G}) over Φ_{0} is a Π_{1}^{0} property of τ, and so T (Φ_{0}, ψ, k) is a Π_{1}^{0} tree, verifying the lemma for n = 1. Note that the Π_{1}^{0} definition of T (Φ_{0}, ψ, k) was obtained uniformly in terms of Φ_{0}, ψ, and k.

For the inductive argument, we assume that the lemma holds for n. We repeat the argument for the base case, with the inductive assumption used to analyze the forcing relation for Π_{n}^{0} sentences. Let k be fixed and suppose that τ is a length k sequence of elements of 2^{<ω} all of the same length. Again, τ is essential to ¬ψ(Φ_{G}) over Φ_{0} if and only if, for all q ∈ P and all m ∈ ω, if (Φ_{0}, ∅) > q and q ⊩ ¬θ(m, Φ_{G}), then Φ_{q} \ Φ_{0} includes a triple (x, y, σ) such that σ is compatible with at least one element of τ. This condition is equivalent to “for all Φ_{q} with Φ_{0} ≥_{0} Φ_{q}, for all k, and all m ∈ ω, if there is a size k set X such that (Φ_{q}, X) ⊩ ¬θ(m, Φ_{G}) then Φ_{q} \ Φ_{0} includes a triple (x, y, σ) such that σ is compatible with at least one element of τ ”. By Lemma 2.10, “there is a size k set X such that (Φ_{q}, X) ⊩ ¬θ(m, Φ_{G})” can be replaced by “T (Φ_{q}, ¬θ(m), k) is infinite”. Thus, τ is essential to ¬ψ(Φ_{G}) over Φ_{0} if and only if, for all Φ_{q} such that Φ_{0} ≥_{0} Φ_{q}, for all k, and all m ∈ ω, if T (Φ_{q}, ¬θ(m), k) is infinite then Φ_{q} \ Φ_{0} includes a triple (x, y, σ) such that σ is compatible with at least one element of τ ” Since ¬θ(m, Φ_{G}) is a Π_{n}^{0} sentence, we can apply induction to conclude that T (Φ_{q}, ¬θ(m), k) is uniformly Π_{n}^{0} in terms of Φ_{q}, ψ, m, and k. As a fact of pure definability, whether a Π_{n}^{0} subtree of a recursively bounded recursive tree is infinite is itself Π_{n}^{0}: it is Σ_{n}^{0} to state that there is a splitting level in the recursive tree which is disjoint from the Π_{n}^{0} subtree. So, “τ is essential to ¬ψ(Φ_{G}) over Φ_{0}” is equivalent to a condition of the form “for all Φ_{q} with Φ_{0} ≥_{0} Φ_{q}, for all k, and all m ∈ ω, if a Π_{n}^{0} condition holds, then so does a bounded one”. Thus, “τ is essential to ¬ψ(Φ_{G}) over Φ_{0}” is a Π_{n+1}^{0} property of τ, Φ_{0} and ψ. Consequently, for each k and for each Π_{n+1}^{0} sentence ψ, T (Φ_{0}, ψ, k) is Π_{n+1}^{0}, uniformly in Φ_{0}, ψ, and k. This completes the verification of the lemma.

Corollary 2.12 Suppose that A is not Δ_{n}^{0}. Let Φ_{0} be a finite use-monotone functional, ψ(Φ_{G}) be a Π_{n}^{0} sentence about Φ_{G}, and k be a positive natural number. If there is a size k set X of subsets of ω such that (Φ_{0}, X) ⊩ ψ(Φ_{G}), then there is such a set X such that A ∉ X. Moreover, we can find such an X all of whose members are recursive in 0^{(n)} uniformly in ψ, k and A⊕0^{(n)}.

Proof: Suppose that there is a size k set X of subsets of ω such that (Φ_{0}, X) ⊩ ψ(Φ_{G}). By Lemmas 2.10 and 2.11, T (Φ_{0}, ψ, k) is a Π_{n}^{0} subtree of a recursively bounded recursive tree T which has an infinite path. Thus, the infinite paths through T (Φ_{0}, ψ, k) form a nonempty Π_{n}^{0} class in the sense of Jockusch and Soare (1972) and so by their Corollary 2.11 (relativized to 0^{(n−1)}), there is an infinite path Y in T (Φ_{0}, ψ, k) in which A is not recursive and so, in particular, A ∉ X(Y). By Lemma 2.10, (Φ_{0}, X(Y)) ⊩ ψ(Φ_{G}) for any such Y. Thus all we need to do is find an infinite path Y in T (Φ_{0}, ψ, k) such that A ∉ X(Y) recursively in A ⊕ 0^{(n)} given that there is one. Since there is such a path, there is one with an initial segment σ such that all of the components of σ are incompatible with A. Moreover, any infinite path through T (Φ_{0}, ψ, k) beginning with such a σ has the desired properties. As A can tell which σ have all their components incompatible with A and 0^{(n)} can tell which nodes have infinite paths through them and so then actually construct such a path, we have the desired conclusion.

Lemma 2.13 Suppose that n is greater than 0, A is not Δ_{n}^{0}, and ψ(Φ_{G}) is a Π_{n}^{0} sentence about Φ_{G}; say ψ(Φ_{G}) = (∀x)θ(x, Φ_{G}) in which θ is Σ_{n−1}^{0}. For any condition p = (Φ_{p}, X_{p}) with A ∉ X_{p}, there is a stronger condition q = (Φ_{q}, X_{q}) which we can find uniformly in Φ_{p} and A⊕0^{(n)} ⊕X_{p} such that the following conditions hold.

1. A ∉ X_{q} and each X ∈ X_{q} − X_{p} is recursive in 0^{(n)}.

2. For all x, if Φ_{q}(x, A) is defined, then Φ_{p}(x, A) is defined. That is, q does not add any new computations to Φ_{G} which apply to A.

3. Either q ⊩ ψ(Φ_{G}) or there is an m such that q ⊩ ¬θ(m, Φ_{G}) (and we can tell which formula we have forced).

Proof: Fix p = (Φ_{p}, X_{p}) in P. Let X_{1}, …, X_{k} be an enumeration of the elements of X_{p}. First, use 0^{(n)} to determine if T (Φ_{p}, ψ, k + 1) is infinite. If so, Corollary 2.12 supplies a condition r = (Φ_{p}, X) forcing ψ(Φ_{G}) with A ∉ X and every X ∈ X recursive in 0^{(n)}. As (2) is trivially satisfied if Φ_{p} is kept fixed, our desired condition q is (Φ_{p}, X_{p}∪X). If T (Φ_{p}, ψ, k+1) is not infinite, then X_{p} ∪ {A} does not provide an infinite path through it. Thus, for some ℓ, τ (ℓ) = (X_{1} ↾ ℓ, …, X_{k} ↾ ℓ, A ↾ ℓ) is not essential to ¬ψ(Φ_{G}) over Φ_{p}. Then, there is an number m and a condition r = (Φ_{r}, X_{r}) extending (Φ_{p}, ∅) such that Φ_{r} does not add any new computations compatible with any of the components of τ (ℓ) and r ⊩ ¬θ(m, Φ_{G}). In particular, Φ_{r} does not add any new computations which apply to A or to any element of X_{p} and, by Lemma 2.10 there is a k such that T (Φ_{r}, ¬θ(m, Φ_{G}), k) is infinite. As we can decide which Φ_{r} extending Φ_{p} add no new computations which apply to A or to any element of X_{p} recursively in A ⊕ X_{p} and then whether T (Φ_{r}, ¬θ(m, Φ_{G}), k) is infinite recursively in 0^{(n−1)} we can find such a Φ_{r} and k recursively in A ⊕ 0^{(n)} ⊕ X_{p}. We can now apply Corollary 2.12 again to get an X of size k with A ∉ X such that every X ∈ X is recursive in 0^{(n)} and (Φ_{r}, X) ⊩ ¬θ(m, Φ_{G}). Our desired condition q is thus (Φ_{r}, X_{p} ∪X).

Now we can complete the proof of Theorem 2.1. Suppose that A ⊆ ω is not Δ_{n}^{0}. Let (ψ_{i}(Φ_{G}) : i ≥ 1) be a recursive enumeration of the Π_{n} sentences about Φ_{G}. We build a sequence of conditions (p_{i} : i ∈ ω) recursively in A ⊕ 0^{(n)} so that p_{0} = (∅, ∅), p_{i} > p_{i+1}, and for all i, p_{i} decides ψ_{i}(Φ_{G}), A ∉ X_{p_{i}} and every X ∈ X_{p_{i}} is recursive in 0^{(n)}.

Given p_{i−1}, we obtain p_{i} in two steps. Suppose that ψ_{i} is ∀xθ_{i}(x, Φ_{G}) and θ_{i}(x, Φ_{G}) is Σ_{i−1}. First, we apply Lemma 2.13 to find a condition q = (Φ_{q}, X_{q}) extending p_{i−1} such that A ∉ X_{q}, every X ∈ X_{q} is recursive in 0^{(n)}, Φ_{q}(A) is equal to Φ_{p}(A), and either q ⊩ ψ_{i}(Φ_{G}) or there is an m in ω such that q ⊩ ¬θ_{i}(m, Φ_{G}). Let ℓ be so large that it is greater than m, it is greater than the length of any sequence mentioned in Φ_{q}, and for each X in X_{q} there is an x less than ℓ with X(x) ≠ A(x). We define p_{i} to be (Φ_{q} ∪ {(n, 0, A ↾ ℓ)}, X_{q}), if q ⊩ ψ_{i}(Φ_{G}), and (Φ_{q} ∪ {(n, 1, A ↾ ℓ)}, X_{q}), if q ⊩ ¬ψ_{i}(Φ_{G}). In other words, we build p_{i} by first deciding the ith Π_{n} sentence about Φ_{G} without extending Φ_{G}(A), and then defining Φ_{G}(n, A) to record the value decided.

Let Φ_{G} be the union of the Φ_{p_{i}}. By induction on the logical complexity of its subformulas, for each Π_{n} sentence ψ_{i} about Φ_{G}, ψ_{i}(Φ_{G}) is true if and only if p_{i} ⊩ ψ_{i}(Φ_{G}). But then Φ_{G}(A) is the characteristic function of a complete Σ_{n} set relative to Φ_{G}. So, Φ_{G} ⊕ A ≥_{T} Φ_{G}(A) ≥_{T} Φ_{G}^{(n)}. As the whole construction is recursive in A ⊕ 0^{(n)} and it decides the truth of all Π_{n} sentences about Φ_{G}, we also have A ⊕ 0^{(n)} ≥_{T} Φ_{G}^{(n)} as required.

The uniformity of this construction clearly provides a proof of the theorem for the ω − REA operators as well.

Theorem 2.14 (Kumabe and Slaman) Suppose that J is an ω-REA operator, and A ⊆ ω is not Δ_{n}^{0} for any n ∈ ω. Then, there is a G ⊆ ω such that A ⊕ G ≡_{T} J(G) ≡_{T} A ⊕ 0^{(ω)}.

We can now continue into the transfinite. Using our results, it is not hard to see that deciding if there is an extension q of a condition p which forces a bounded sentence with a predicate for Φ_{G}^{(ω)} is recursive in 0^{(ω)}. One can then employ an inductive analysis similar to that of Lemmas 2.11 and 2.13 to see that such decisions can be made for sentences which are Π_{n} in Φ_{G}^{(ω)} can be made recursively in 0^{(ω+n)}. At limit levels of the transfinite jump hierarchy the uniformity of our constructions carries us through. Thus we can answer Question 1.12 for all the recursive ordinals as asked originally in Jockusch and Shore (1984).

Theorem 2.15 Suppose that J is an α − REA operator, and A ⊆ ω is not recursive in 0^{(β)} for any β < α. Then, there is a G ⊆ ω such that A ⊕ G ≡_{T} J(G) ≡_{T} A ⊕ 0^{(α)}.

References

Cooper, S. B. (1990). The jump is definable in the structure of the degrees of unsolvability, Bull. Amer. Math. Soc. 23: 151–158.

Griffor, E. (ed.) (1999). Handbook of Computability Theory, North-Holland Publishing Co., Amsterdam.

Jockusch, Jr., C. G. and Shore, R. A. (1984). Pseudo-jump operators II: Transfinite iterations, hierarchies, and minimal covers, J. Symbolic Logic 49: 1205–1236.

Jockusch, Jr., C. G. and Soare, R. I. (1970). Minimal covers and arithmetical sets, Proc. Amer. Math. Soc. 25: 856–859.

Jockusch, Jr., C. G. and Soare, R. I. (1972). Π_{1}^{0} classes and degrees of theories, Trans. Amer. Math. Soc. 173: 33–56.

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

Lachlan, A. H. (1975). A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9: 307–365.

Sacks, G. E. (1963). On the degrees less than 0′, Ann. of Math. 77: 211–231.

Shore, R. A. (1985). The structure of the degrees of unsolvability, Recursion theory (Ithaca, N.Y., 1982), Amer. Math. Soc., Providence, R.I., pp. 33–51.

Shore, R. A. and Slaman, T. A. (n.d.). A splitting theorem for n-REA degrees. Unpublished.

Slaman, T. A. (1991). Degree structures, Proceedings of the International Congress of Mathematicians, Kyoto, 1990, Vol. I, Springer–Verlag, Heidelberg, pp. 303–316.

Slaman, T. A. and Woodin, W. H. (n.d.). Definability in degree structures. Unpublished.

Turing, A. M. (1939). Systems of logic based on ordinals, Proc. London Math. Soc. (3) 45: 161–228.