Mass Problems and Hyperarithmeticity

Joshua A. Cole University of Notre Dame http://www.nd.edu/∼jcole1/ jcole1@nd.edu

Stephen G. Simpson Pennsylvania State University http://www.math.psu.edu/simpson/ simpson@math.psu.edu

June 4, 2008

Journal of Mathematical Logic, 7:125–143, 2008. Submitted December 12, 2006. Accepted April 17, 2008.

Mathematics Subject Classification Codes: 03D28, 03D30, 03D55, 03D60.

Cole’s research was partially supported by NSF grants DMS-0245167 and RTG-0353748 and a Schmitt Fellowship at the University of Notre Dame.

Simpson’s research was partially supported by NSF grant DMS-0600823.

Abstract

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let P_{w} be the lattice of weak degrees of mass problems associated with nonempty Π_{1}^{0} subsets of the Cantor space. The lattice P_{w} has been studied in previous publications. The purpose of this paper is to show that P_{w} partakes of hyperarithmeticity. We exhibit a family of specific, natural degrees in P_{w} which are indexed by the ordinal numbers less than ω_{1}^{CK} and which correspond to the hyperarithmetical hierarchy. Namely, for each α < ω_{1}^{CK} let h_{α} be the weak degree of 0^{(α)}, the αth Turing jump of 0. If p is the weak degree of any mass problem P, let p^{∗} be the weak degree of the mass problem P^{∗} = {Y | ∃X (X ∈ P and BLR(X) ⊆ BLR(Y))} where BLR(X) is the set of functions which are boundedly limit recursive in X. Let 1 be the top degree in P_{w}. We prove that all of the weak degrees inf(h_{α}^{∗}, 1), α < ω_{1}^{CK}, are distinct and belong to P_{w}. In addition, we prove that certain index sets associated with P_{w} are Π_{1}^{1} complete.

Contents

Abstract 1

Contents 2

1 Introduction 2

2 Bounded limit recursiveness 4

3 Diagonal nonrecursiveness and 1-genericity 7

4 Embedding hyperarithmeticity into P_{w} 8

5 Index sets associated with P_{w} 10

6 More on bounded limit recursiveness 13

References 17

1 Introduction

Let 2^{ω} be the Cantor space, i.e., the space of infinite sequences of 0’s and 1’s. In previous papers [6, 8, 38, 34, 36, 37] Simpson and others studied the lattice P_{w} of degrees of unsolvability of mass problems associated with nonempty Π_{1}^{0} subsets of 2^{ω}. Simpson [34, 36, 37, 38] showed that P_{w} contains many specific, natural degrees in addition to 1 and 0, the top and bottom elements of P_{w}. These specific, natural degrees in P_{w} arise from foundationally interesting topics such as reverse mathematics, algorithmic randomness, computational complexity, and subrecursive hierarchies from Gentzen-style proof theory.

In the present paper we exhibit some new examples of specific, natural degrees in P_{w}. Our new examples arise from hyperarithmetical theory. In order to introduce our new examples, we first review some basic facts about the hyperarithmetical hierarchy. Some useful references for hyperarithmetical theory are Ash/Knight [3], Rogers [29, Chapter 16], Sacks [30, Part A], Shoenfield [31, Sections 7.8–7.11], and Simpson [33, Section VIII.3].

A recursive ordinal is an ordinal number which is the order type of a recursive well ordering of the integers. Obviously the recursive ordinals form a countable initial segment of the countable ordinals.^{1} Let ω_{1}^{CK} (pronounced “omega-one-C-K” or “Church-Kleene-omega-one”) be the least nonrecursive ordinal. Thus for any ordinal α we have α < ω_{1}^{CK} if and only if α is recursive. For each such α let 0^{(α)} be the αth iterated Turing jump of 0. It is known that 0^{(α)} is well defined up to Turing degree. Moreover, 0^{(α)} is a Σ_{3}^{0} singleton.^{2} The Turing degrees 0^{(α)}, α < ω_{1}^{CK} are collectively known as the hyperarithmetical hierarchy. A Turing oracle X is said to be hyperarithmetical if it is Turing reducible to 0^{(α)} for some α < ω_{1}^{CK}. It is known that X is hyperarithmetical if and only if X is Turing reducible to some arithmetical singleton, if and only if X is Δ_{1}^{1}.

1It is known that an ordinal is recursive if and only if is the order type of a Δ_{1}^{1} well ordering of the integers. An interesting refinement of this result is due to Montalbán [26].

Given a Turing oracle X, we identify the Turing degree of X with the weak degree of the singleton set {X}. In particular, for each α < ω_{1}^{CK} let h_{α} be the Turing degree of 0^{(α)}, identified with the weak degree of {0^{(α)}}. We wish to embed the degrees h_{α}, α < ω_{1}^{CK}, into P_{w}. There is a general Embedding Lemma due to Simpson [36, Lemma 3.3] (see also [38]) which reads as follows: If s is the weak degree of a Σ_{3}^{0} set of Turing oracles, then inf(s, 1) belongs to P_{w}. Since {0^{(α)}} is Σ_{3}^{0}, it follows that inf(h_{α}, 1) ∈ P_{w}. However, this particular mapping of the hyperarithmetical hierarchy into P_{w} is of no interest, because for all α ≥ 1 we have inf(h_{α}, 1) = 1 in view of the Kleene Basis Theorem. To obtain an interesting one-to-one embedding of the hyperarithmetical hierarchy into P_{w}, we need an additional device: bounded limit recursiveness.

Given a Turing oracle X and a function f from integers to integers, we say that f is boundedly limit recursive in X, abbreviated f ∈ BLR(X), if there exist an approximating function f̃ and a bounding function f̂ such that f̃ is Turing computable from X, f̂ is Turing computable, and

|{s | f̃(n, s) ≠ f̃(n, s + 1)}| < f̂(n)

with f(n) = lim_{s} f̃(n, s) for all n. Here we are implicitly citing the Limit Lemma, a well known result which says that f is (unboundedly) limit recursive if and only if f is Turing reducible^{3} to 0′, if and only if f is Δ_{2}^{0}. More precisely, one can say that f ∈ BLR(0) if and only if f is weakly truth-table reducible to 0′, if and only if f occurs at the ωth level of the Ershov hierarchy.

We prove below that if S is Σ_{3}^{0} then

S^{∗} = {Y | ∃X (X ∈ S and BLR(X) ⊆ BLR(Y))}

is again Σ_{3}^{0}. In particular, for each α < ω_{1}^{CK}, {0^{(α)}}^{∗} is Σ_{3}^{0}. Therefore, letting h_{α}^{∗} be the weak degree of {0^{(α)}}^{∗}, we have inf(h_{α}^{∗}, 1) ∈ P_{w} by the Embedding Lemma [36, 38]. Moreover, we prove below that all of these weak degrees inf(h_{α}^{∗}, 1), α < ω_{1}^{CK} are distinct. In this way we obtain our specific, natural, one-to-one embedding of the hyperarithmetical hierarchy into P_{w}. This is our first main result.

In order to state our second main result, let P_{i}, i = 0, 1, …, be a standard, recursive enumeration of all of the nonempty Π_{1}^{0} subsets of 2^{ω}. Let p_{i} be the weak degree of P_{i}. Thus by definition P_{w} = {p_{i} | i = 0, 1, …}. We prove below that the index set {i | p_{i} = 1} is a Π_{1}^{1} complete set of integers. More generally, if j is such that p_{j} > 0, then {i | p_{i} = p_{j}} and {i | p_{i} ≥ p_{j}} are Π_{1}^{1} complete sets of integers. We leave it as an open question to characterize the j’s such that {i | p_{i} ≤ p_{j}} is a Π_{1}^{1} complete set of integers.

2By a Σ_{3}^{0} singleton we mean a Turing oracle X such that the one-element set {X} is Σ_{3}^{0}.

Some interesting results concerning arithmetical singletons are due to H. Tanaka [40] and Leo Harrington (unpublished).

3Note that 0′ = 0^{(1)} = the Turing jump of 0 = the halting problem.

Another open question is to calculate the degree of unsolvability of Th(P_{w}), the first-order theory of the lattice P_{w}. We conjecture that Th(P_{w}) is recursively isomorphic to O^{(ω)}, the ωth Turing jump of O. Here O is Kleene’s O, i.e., a Π_{1}^{1} complete set of integers. This conjecture seems reasonable in light of our results stated above plus the known characterizations of Th(S) (up to recursive isomorphism) for other degree structures S. See for example Simpson [32] and Nies/Shore/Slaman [28].

The idea that P_{w} may partake of hyperarithmeticity was first broached by Simpson in his 2005 grant application to the U.S. National Science Foundation, which eventually resulted in NSF grant DMS-0600823.

The reader who is familiar with the basics of recursion theory and hyperarithmetical theory will find that this paper is largely self-contained. We use standard recursion-theoretical notation from Rogers [29].

2 Bounded limit recursiveness

Let ω = {0, 1, 2, …} = the set of nonnegative integers. Let ω^{ω} be the Baire space, i.e., the set of totally defined functions f : ω → ω.

Definition 2.1. Let A be a Turing oracle. We define f : ω → ω to be boundedly limit recursive in A if there exist an A-recursive approximating function f̃ : ω × ω → ω and a recursive bounding function f̂: ω → ω such that for all n, {s | f̃(n, s) ≠ f̃(n, s + 1)} is finite of cardinality < f̂(n) and lim_{s} f̃(n, s) = f(n). We write

BLR(A) = {f ∈ ω^{ω} | f is boundedly limit recursive in A}.

Remark 2.2. The next three lemmas provide better understanding of BLR(A). See also Section 6 below. We write f ≤_{T} A to mean that f is A-recursive, i.e., Turing reducible to A, i.e., computable using A as a Turing oracle. Let A′ be the Turing jump of A.

Lemma 2.3. We have f ∈ BLR(A) if and only if f ≤_{T} A′ with recursively bounded use of A′ and unbounded use of A.

Proof. “If”. Assume f ≤_{T} A′ with recursively bounded use of A′ and unbounded use of A, say f(n) = φ_{e}^{(2),A}(A′ ↾ b(n), n) where b(n) is recursive. Let A′_{s} = the finite subset of A′ enumerated in the first s steps of some fixed A-recursive enumeration of A′. Let f̃(n, s) = φ_{e,s}^{(2),A↾s}(A′_{s} ↾ b(n), n) if this is defined, 0 otherwise. Then f̃(n, s) is A-recursive and f(n) = lim_{s} f̃(n, s). Moreover

|{s | f̃(n, s) ≠ f̃(n, s + 1)}| ≤ 2b(n) + 1

so f ∈ BLR(A) via f̂(n) = 2b(n) + 2.

“Only if”. Assume f ∈ BLR(A) via an A-recursive approximating function f̃ and a recursive bounding function f̂. We describe how to compute f(n). For each i < f̂(n) we ask the oracle A′ whether

|{s | f̃(n, s) ≠ f̃(n, s + 1)}| > i.

From the answers to these questions, we immediately read off

k(n) = |{s | f̃(n, s) ≠ f̃(n, s + 1)}|.

Then f(n) = f̃(n, t) for the least t such that

|{s < t | f̃(n, s) ≠ f̃(n, s + 1)}| = k(n).

Here we have used A′ only to compute k(n). Therefore, our use of A′ was bounded by b(n) = max{p(n, i) | i < f̂(n)} where p(n, i) is a fixed, primitive recursive function. Since f̂(n) is recursive, so is b(n).

Lemma 2.4. X ≤_{T} Y implies BLR(X) ⊆ BLR(Y), which implies X′ ≤_{T} Y′.

Proof. The first implication is clear from the definition of BLR, because if X ≤_{T} Y then every X-recursive function is Y -recursive. The second implication is an easy consequence of Lemma 2.3.

Lemma 2.5. The following are pairwise equivalent.

1. BLR(X) ⊆ BLR(Y).

2. For each partial X-recursive function ψ(n) we have g ∈ BLR(Y) where

g(n) = \{ \begin{matrix}ψ(n) + 1 & if ψ(n) is defined, \\ 0 & otherwise. \end{matrix}

3. There exists h ∈ BLR(Y) such that

∀n (if φ_{n}^{(1),X}(n) is defined then h(n) = φ_{n}^{(1),X}(n)).

Proof. Clearly 1 ⇒ 2 and 2 ⇒ 3. To prove 3 ⇒ 2, assume that ψ(n) is partial X-recursive. Let e be an index of ψ, i.e., φ_{e}^{(1),X}(n) ≃ ψ(n) for all n. Let θ(n) ≃ the least σ ⊂ X such that φ_{e,|σ|}^{(1),σ}(n) is defined. Since θ(n) is partial

X-recursive, let p(n) be primitive recursive such that θ(n) ≃ φ_{p(n)}^{(1),X}(p(n)). Let

h be as in 3, and let g(n) ≃ φ_{e,|h(p(n))|}^{(1),h(p(n))}(n)+1 if the latter is defined, 0 otherwise. Then g satisfies 2. To prove 2 ⇒ 1, let f ∈ BLR(X) be given. For all n and all i ≤ f̂(n) + 1, let ψ_{i}(n) ≃ the ith successive value of f̃(n, s) as s → ∞. The functions ψ_{i}(n) are uniformly partial X-recursive, so by 2 the functions g_{i}(n) = ψ_{i}(n) + 1 if ψ_{i}(n) is defined, 0 otherwise, are uniformly BLR(Y) with uniformly recursive bounding functions ĝ_{i}(n). Let g(n) = g_{i}(n) − 1 for the least i such that g_{i+1}(n) = 0. Then f = g ∈ BLR(Y) via the recursive bounding function ĝ(n) = ∑{ĝ_{i}(n) | i < f̂(n)}.

Theorem 2.6. The binary relation BLR(X) ⊆ BLR(Y) is Σ_{3}^{0}. Furthermore, if S is Σ_{3}^{0} then so is

S^{∗} = {Y | ∃X (X ∈ S and BLR(X) ⊆ BLR(Y))}.

Proof. By Lemma 2.5, BLR(X) ⊆ BLR(Y) if and only if there exists h ∈ BLR(Y) such that ∀n (h(n) = φ_{n}^{(1),X}(n) if the latter is defined). This holds if and only if there exist (indices for) a totally defined Y -recursive function h̃ and a totally defined recursive function ĥ such that

∀n (|{s | h̃(n, s) ≠ h̃(n, s + 1)}| < ĥ(n))

and ∀n ∀s ∃t > s (h̃(n, t) = φ_{n,t}^{(1),X↾t}(n) if the latter is defined). A Tarski/Kuratowski computation (see Rogers [29, Section 14.3]) shows that this statement is Σ_{3}^{0}. This proves the first part of the theorem.

In order to prove the second part, we first prove it with S replaced by P, where P is a Π_{1}^{0} subset of ω^{ω}. Let T ⊆ ω^{<ω} be a recursive tree such that

P = {paths through T },

i.e.,

P = {f ∈ ω^{ω} | ∀j (f ↾ j ∈ T)}.

By Lemma 2.5, Y ∈ P^{∗} if and only if there exist f ∈ P and g ∈ BLR(Y) such that ∀i (g(2i) = f(i)) and ∀n (g(2n + 1) = φ_{n}^{(1),f}(n) if the latter is defined). This holds if and only if there exist (indices for) a totally defined Y -recursive function g̃ and a totally defined recursive function ĝ such that

∀n (|{s | g̃(n, s) ≠ g̃(n, s + 1)}| < ĝ(n))

and

∀j ∀s ∃t > s (⟨g̃(2i, t) | i < j⟩ ∈ T)

and

∀n ∀j ∀s ∃t > s (g̃(2n + 1, t) = φ_{n,t}^{(1),⟨g̃(2i,t)|i<j⟩}(n) if the latter is defined).

Thus, by a Tarski/Kuratowski computation, P^{∗} is Σ_{3}^{0}.

Now let S be Σ_{3}^{0}, say

S = {X | ∃i ∀m ∃n R(i, m, n, X)}

where R is recursive. Consider the Π_{1}^{0} set

P = {⟨i⟩^{⌢}(X ⊕ f) | ∀m R(i, m, f(m), X)}.

By what we have already proved, P^{∗} is Σ_{3}^{0}. But clearly the Turing upward closure of S is the same as the Turing upward closure of P. Hence by Lemma 2.4 we have S^{∗} = P^{∗}. It follows that S^{∗} is Σ_{3}^{0}.

Remark 2.7. (1) We could modify Definition 2.1 by requiring f̂ to be not only recursive but also primitive recursive. In this case, Lemma 2.3 would hold with “recursively bounded” replaced by “primitive recursively bounded”. Lemma 2.5 and Theorems 2.6, 4.4, 4.5, 4.7 would go through unchanged but with a different meaning. (2) Alternatively, we could modify Definition 2.1 by allowing f̂ to be A-recursive instead of merely recursive. In this case, Lemma 2.3 would hold with “recursively bounded” replaced by “A-recursively bounded”. Lemma 2.5 would fail, the definition of S^{∗} would need to be changed accordingly, and Theorems 2.6, 4.4, 4.5, 4.7 would go through with this change.

3 Diagonal nonrecursiveness and 1-genericity

Definition 3.1. A function g ∈ ω^{ω} is said to be 1-generic if for every recursively enumerable set of strings A ⊆ ω^{<ω} there exists a string σ ⊂ g such that either σ ∈ A or ¬ ∃τ (σ ⊆ τ and τ ∈ A).

Remark 3.2. There is an extensive literature on 1-genericity. See Kumabe [24] and the references listed there.

Remark 3.3. In the definition of 1-genericity, it suffices to consider only the particular recursive sets of strings

A_{n} = {τ ∈ ω^{<ω} | φ_{n,|τ|}^{(1),τ}(n) is defined}.

This is because, for any recursively enumerable set A ⊆ ω^{<ω}, we can find an n such that for all g ∈ ω^{ω}, φ_{n}^{(1),g}(n) is defined if and only if ∃τ ⊂ g (τ ∈ A).

Lemma 3.4. Given a Turing oracle X, we can find a 1-generic g such that BLR(X) = BLR(g).

Proof. Define h ∈ ω^{ω} by h(n) = φ_{n}^{(1),X}(n)+1 if φ_{n}^{(1),X}(n) is defined, 0 otherwise. Let the sets A_{n}, n = 0, 1, 2, … be as in Remark 3.3. Define a sequence of strings τ_{0} ⊆ τ_{1} ⊆ ⋯ ⊆ τ_{n} ⊆ ⋯ as follows. Begin with τ_{0} = ⟨⟩, the empty string. Assuming that τ_{n} has already been defined, ask the oracle 0′ whether there exists τ ⊇ τ_{n}^{⌢}⟨h(n)⟩ such that τ ∈ A_{n}. If the answer is yes, let τ_{n+1} = the least such τ in some fixed recursive enumeration of ω^{<ω}. If the answer is no, let τ_{n+1} = τ_{n}^{⌢}⟨h(n)⟩. Finally let g = ⋃_{n} τ_{n}. By Remark 3.3, g is 1-generic. By construction, the sequence of strings τ_{n}, n = 0, 1, 2, … is boundedly limit recursive in each of the oracles X and g with bounding functions 4^{n} and 2^{n} respectively. Moreover, h(n) = τ_{n+1}(|τ_{n}|) and φ_{n}^{(1),g}(n) ≃ φ_{n,|τ_{n+1}|}^{(1),τ_{n+1}}(n). It follows by Lemma 2.5 that BLR(X) = BLR(g).

Definition 3.5. A function f ∈ ω^{ω} is said to be diagonally nonrecursive, abbreviated DNR, if f(n) ≄ φ_{n}^{(1)}(n) for all n.

Remark 3.6. There is an extensive literature on DNR functions and their Turing degrees. See for instance Jockusch [21], Kjos-Hanssen/Merkle/Stephan [23], and Ambos-Spies/Kjos-Hanssen/Lempp/Slaman [1]. The following lemma appears in Demuth/Kučera [15, Corollary 9].

Lemma 3.7. If g is 1-generic, there is no DNR function ≤_{T} g.

Proof. Fix an index e. Consider the recursively enumerable set of strings

A = {τ | ∃n (φ_{e}^{(1),τ} (n) ↓ = φ_{n}^{(1)}(n) ↓)}.

Because g is 1-generic, there are two cases.

Case 1. There exists τ ⊂ g such that τ ∈ A. Then for some n we have φ_{e}^{(1),τ} (n) ↓ = φ_{n}^{(1)}(n) ↓, hence φ_{e}^{(1),g}(n) ↓ = φ_{n}^{(1)}(n) ↓, hence φ_{e}^{(1),g} is not DNR.

Case 2. For some σ ⊂ g, there is no τ ⊇ σ belonging to A. Fix such a σ. Define a partial recursive function θ(n) as follows. Given n, look for τ ⊇ σ such that φ_{e}^{(1),τ} (n) ↓. If and when we find such a τ, define θ(n) = φ_{e}^{(1),τ} (n). If no such τ is found, let θ(n) be undefined.

Let n be an index of θ. We claim that φ_{e}^{(1),τ} (n) ↑ for all τ ⊇ σ. Otherwise, there exists τ ⊇ σ such that φ_{e}^{(1),τ} (n) ↓ and θ(n) ≃ φ_{e}^{(1),τ} (n), by definition of θ(n). But then

φ_{e}^{(1),τ} (n) ↓ = θ(n) ↓ = φ_{n}^{(1)}(n) ↓,

hence τ ∈ A, contradicting the case hypothesis. This proves our claim.

Our claim implies that φ_{e}^{(1),g}(n) ↑. Hence φ_{e}^{(1),g} is not totally defined, hence not DNR.

We have now shown that φ_{e}^{(1),g} is not DNR for any e.

Theorem 3.8. Given a Turing oracle X, we can find a Turing oracle Y such that BLR(X) = BLR(Y) and there is no DNR function ≤_{T} Y.

Proof. This is immediate from Lemmas 3.4 and 3.7.

4 Embedding hyperarithmeticity into P_{w}

The Embedding Lemma of Simpson [36, 38] reads as follows.

Lemma 4.1 (Embedding Lemma). Let S ⊆ ω^{ω} be Σ_{3}^{0}. Let s be the weak degree of S. Then inf(s, 1) belongs to P_{w}.

Proof. See [36, Lemma 3.3] or [38, Lemma 4].

Remark 4.2. Simpson [34, 36, 37, 38] has used the Embedding Lemma to obtain many examples of specific, natural degrees in P_{w}. In particular, let d be the weak degree of DNR, the set of diagonally nonrecursive functions, and let r_{n} be the weak degree of R_{n}, the set of n-random sequences of 0’s and 1’s. Using the Embedding Lemma 4.1, Simpson [34, 36] has shown that d and r_{1} and inf(r_{2}, 1) belong to P_{w} and that

0 < d < r_{1} < inf(r_{2}, 1) < 1,

where 0 and 1 are the bottom and top degrees in P_{w}.

We now extend this methodology as follows.

Definition 4.3. For any set S of Turing oracles, let

S^{∗} = {Y | ∃X (X ∈ S and BLR(X) ⊆ BLR(Y))}.

If s is the weak degree of S, let s^{∗} be the weak degree of S^{∗}. By Lemma 2.4, s^{∗} depends only on the weak degree s and not on its representative S.

Theorem 4.4. If S is Σ_{3}^{0}, then the weak degree inf(s^{∗}, 1) belongs to P_{w}.

Proof. By Theorem 2.6 S^{∗} is Σ_{3}^{0}. Therefore by Lemma 4.1 inf(s^{∗}, 1) ∈ P_{w}.

Theorem 4.5. If ∅ ≠ S ⊆ {X | X′ ≥_{T} 0′′}, then the weak degree inf(s^{∗}, 1) is incomparable with each of the weak degrees d and r_{1} and inf(r_{2}, 1).

Proof. Since S is nonempty, Theorem 3.8 gives Y ∈ S^{∗} such that there is no DNR function ≤_{T} Y. It follows that d ≰ s^{∗}, hence d ≰ inf(s^{∗}, 1). On the other hand, since S ⊆ {X | X′ ≥_{T} 0′′}, it follows by Lemma 2.4 that S^{∗} ⊆ {Y | Y′ ≥_{T} 0′′}, and this set is known to be of measure 0. (See for instance [37, proof of Theorem 4.5].) In addition, recall that 1 is the weak degree of PA, the set of complete extensions of Peano Arithmetic, and it is known that the set {Y ∈ 2^{ω} | ∃X (X ∈ PA and X ≤_{T} Y)} is also of measure 0. (See for instance the general non-helping result in [34, Lemma 7.3].) Since R_{2} is of measure 1, we can find Y ∈ R_{2} not belonging to either of these sets of measure 0. It follows that r_{2} ≱ inf(s^{∗}, 1), hence inf(r_{2}, 1) ≱ inf(s^{∗}, 1). The proof is now finished, because d < r_{1} < inf(r_{2}, 1).

Remark 4.6. The effect of Theorems 4.4 and 4.5 is to supplement the Embedding Lemma 4.1 by providing another general method for discovering specific, natural degrees in P_{w}. We shall now use this technique to embed the hyperarithmetical hierarchy into P_{w}. Recall from the Introduction that 0^{(α)} is the αth Turing jump of 0, and h_{α} is the weak degree of the singleton set {0^{(α)}}.

Theorem 4.7. For each α < ω_{1}^{CK} we have inf(h_{α}^{∗}, 1) ∈ P_{w}. For each α < ω_{1}^{CK} except 0, inf(h_{α}^{∗}, 1) is incomparable with d and r_{1} and inf(r_{2}, 1) in the lattice ordering of P_{w}. For all α < β < ω_{1}^{CK} we have inf(h_{α}^{∗}, 1) < inf(h_{β}^{∗}, 1), in fact inf(h_{α}^{∗}, d) < inf(h_{β}^{∗}, d).

Proof. By [30, Section II.4] or [33, Section VIII.3], the singleton set {0^{(α)}} is Σ_{3}^{0}. Hence, by Theorem 4.4, inf(h_{α}^{∗}, 1) ∈ P_{w}. For α > 0 we obviously have 0^{(α)} ≥_{T} 0′, hence by Theorem 4.5 inf(h_{α}^{∗}, 1) is incomparable with d and r_{1} and inf(r_{2}, 1). For α < β < ω_{1}^{CK} we obviously have 0^{(α)} <_{T} 0^{(β)}, hence h_{α} < h_{β}, hence h_{α}^{∗} ≤ h_{β}^{∗}, hence inf(h_{α}^{∗}, d) ≤ inf(h_{β}^{∗}, d). To obtain a strict inequality, apply Theorem 3.8 to get Y such that BLR(0^{(α)}) = BLR(Y) and there is no DNR function ≤_{T} Y. Then Y ∈ {0^{(α)}}^{∗} and, since BLR(0^{(α)}) ⫋ BLR(0^{(β)}), there is no Z ≤_{T} Y such that Z ∈ {0^{(β)}}^{∗}. This shows that h_{α}^{∗} ≱ inf(h_{β}^{∗}, d). It now follows that inf(h_{α}^{∗}, d) < inf(h_{β}^{∗}, d), hence inf(h_{α}^{∗}, 1) < inf(h_{β}^{∗}, 1).

5 Index sets associated with P_{w}

In this section we prove that certain index sets associated with weak reducibility in P_{w} are Π_{1}^{1} complete. The proof is based on the following lemma concerning Π_{1}^{0} subsets of ω^{ω}. Let REC = {g ∈ ω^{ω} | g is recursive}.

Lemma 5.1. Given Π_{1}^{0} sets P, Q ⊆ ω^{ω} such that Q∩REC = ∅, we can effectively find a Π_{1}^{0} set H(P, Q) ⊆ ω^{ω} such that P is homeomorphic to H(P, Q) and there do not exist g ∈ Q and h ∈ H(P, Q) such that g ≤_{T} h.

Proof. The proof of Lemma 5.1 will involve a construction and two sublemmas. We begin with some general remarks concerning treemaps.

Definition 5.2. A treemap is a function F : ω^{<ω} → ω^{<ω} such that

F (σ)^{⌢}⟨i⟩ ⊆ F (σ^{⌢}⟨i⟩)

for all σ ∈ ω^{<ω} and all i ∈ ω. A tree is a set T ⊆ ω^{<ω} such that

∀σ ∀τ ((σ ⊂ τ and τ ∈ T) ⇒ σ ∈ T).

Given a treemap F and a tree T, we have another tree

F (T) = {τ | ∃σ (σ ∈ T and τ ⊆ F (σ))}.

Remark 5.3. Given τ ∈ F (T), let σ be mininal such that τ ⊆ F (σ). Then σ ∈ T and σ is a substring of τ, i.e., σ = ⟨τ(j_{0}), τ(j_{1}), …, τ(j_{m−1})⟩ for some j_{0} < j_{1} < ⋯ < j_{m−1} < |τ| where m = |σ|. Therefore, in the definition of F (T), the quantifier ∃σ can be replaced by a bounded quantifier, namely

F (T) = {τ | (∃σ substring of τ) (σ ∈ T and τ ⊆ F (σ))}.

From this it follows that, for example, if F and T are recursive then so is F (T).

Remark 5.4. The sets

P = {paths through T }

and

F (P) = {paths through F (T)}.

are closed subsets of ω^{ω} and we have a homeomorphism F : P → F (P), i.e., a continuous, open, one-to-one mapping of P onto F (P), defined by

F (f) = ⋃{F (σ) | σ ⊂ f}

for all f ∈ P. In particular, if T ⊆ ω^{<ω} is a recursive tree and F : ω^{<ω} → ω^{<ω} is a recursive treemap, then P and F (P) are Π_{1}^{0} subsets of ω^{ω}, and F : P → F (P) is a recursive homeomorphism of P onto F (P).

We now begin the proof of Lemma 5.1. Given a Π_{1}^{0} set Q ⊆ ω^{ω} such that Q ∩ REC = ∅, let U ⊆ ω^{<ω} be a recursive tree such that

Q = {g ∈ ω^{ω} | g is a path through U}.

We shall use U to define a treemap H_{Q}.

In constructing H_{Q}, we shall sometimes identify strings σ ∈ ω^{<ω} with their Gödel numbers #(σ) = ∏_{i<|σ|} p_{i}^{σ(i)+1}, where p_{0}, p_{1}, p_{2}, … are the prime numbers 2, 3, 5, … in increasing order. For integers e and strings σ, we write Φ_{e}(σ) = ⟨φ_{e,|σ|}^{(1),σ}(j) | j < n⟩ where n = least j such that φ_{e,|σ|}^{(1),σ}(j) ↑. Note that Φ_{e} : ω^{<ω} → ω^{<ω} is recursive and monotonic, i.e., σ ⊆ τ implies Φ_{e}(σ) ⊆ Φ_{e}(τ).

The construction of H_{Q} is as follows. We define H_{Q}(σ) by induction on σ ∈ ω^{<ω}. Begin with H_{Q}(⟨⟩) = ⟨⟩ where ⟨⟩ is the empty string. Assume that H_{Q}(σ) has already been defined. In order to define H_{Q}(σ^{⌢}⟨i⟩), let e = |σ| and let τ_{0} = H_{Q}(σ)^{⌢}⟨i⟩. Given τ_{n}, let τ_{n+1} = the least τ such that τ_{n} ⊂ τ and Φ_{e}(τ_{n}) ⊂ Φ_{e}(τ) ∈ U. If no such τ exists, let τ_{n+1} be undefined. This must happen for some n, because otherwise we would have Φ_{e}(τ_{n}) ⊂ Φ_{e}(τ_{n+1}) ∈ U for all n, hence ⋃_{n} Φ_{e}(τ_{n}) would be a recursive path through U, i.e., a member of Q ∩ REC, contradicting the assumption that Q ∩ REC = ∅. We then let H_{Q}(σ^{⌢}⟨i⟩) = τ_{n} for the least n such that τ_{n+1} is undefined.

Sublemma 5.5. H_{Q} is a treemap, and H_{Q} ≤_{T} 0′.

Proof. This is clear from the construction of H_{Q}.

Sublemma 5.6. There do not exist f ∈ ω^{ω} and g ∈ Q such that H_{Q}(f) ≥_{T} g.

Proof. Suppose H_{Q}(f) ≥_{T} g. Let e be such that φ_{e}^{(1),H_{Q}(f)} = g. Let σ^{⌢}⟨i⟩ = f ↾ e + 1 and consider the definition of H_{Q}(σ^{⌢}⟨i⟩). Since τ_{n+1} is undefined and τ_{n} = H_{Q}(σ^{⌢}⟨i⟩) = H_{Q}(f ↾ e + 1), there is no τ ⊃ H_{Q}(f ↾ e + 1) such that Φ_{e}(τ) ⊃ Φ_{e}(H_{Q}(f ↾ e + 1)) and Φ_{e}(τ) ∈ U. In particular, φ_{e}^{(1),H_{Q}(f)} is not a path through U. In other words, g ∉ Q. This proves the sublemma.

Now let P ⊆ ω^{ω} be Π_{1}^{0}. By Remarks 5.3 and 5.4 and Sublemma 5.5, H_{Q}(P) is Π_{1}^{0,0′} and H_{Q} is a homeomorphism of P onto H_{Q}(P). It follows that H_{Q}(P) is Π_{2}^{0}, say

H_{Q}(P) = {h ∈ ω^{ω} | ∀m ∃n R(m, n, h)}

where R ⊆ ω × ω × ω^{ω} is recursive. Define

H(P, Q) = {h ⊕ k ∈ ω^{ω} | ∀m (k(m) = least n such that R(m, n, h))}.

Clearly H(P, Q) is Π_{1}^{0} and h ↦ h ⊕ k is a homeomorphism of H_{Q}(P) onto H(P, Q). Moreover, for all h ⊕ k ∈ H(P, Q) we have h ⊕ k ≡_{T} h ∈ H_{Q}(P), hence by Sublemma 5.6 there is no g ∈ Q such that g ≤_{T} h ⊕ k. Note also that our construction was such that, given Π_{1}^{0} indices of P and Q, we can effectively find a Π_{1}^{0,0′} index of H_{Q}(P), a Π_{2}^{0} index of H_{Q}(P), and a Π_{1}^{0} index of H(P, Q).

This finishes the proof of Lemma 5.1.

We now return to the study of Π_{1}^{0} subsets of 2^{ω}.

Theorem 5.7. Let P_{i}, i = 0, 1, … be a standard recursive enumeration of the nonempty Π_{1}^{0} subsets of 2^{ω}. For each i, let p_{i} be the weak degree of P_{i}. If j is such that p_{j} > 0, then the index sets {i | p_{i} = p_{j}} and {i | p_{i} ≥ p_{j}} are Π_{1}^{1} complete sets of integers.

Proof. Let S_{e}, e = 0, 1, … be a standard recursive enumeration of the Π_{1}^{0} subsets of ω^{ω}. As a consequence of the Kleene Normal Form Theorem, it is well known that the index set {e | S_{e} = ∅} is a Π_{1}^{1} complete set of integers. We shall reduce this Π_{1}^{1} complete set to each of the index sets in question. Fix an index j such that p_{j} > 0, i.e., P_{j} ∩ REC = ∅. Given an index e, Lemma 5.1 tells us that we can effectively find an index h(e, j) such that S_{h(e,j)} = H(S_{e}, P_{j}). Also, the proof of the Embedding Lemma 4.1 (see also Simpson [36, Lemma 3.3] and [38, Lemma 4]) tells us that we can effectively find an index f(e, j) such that P_{f(e,j)} is weakly equivalent to S_{e} ∪ P_{j}. Combining these two results, we obtain:

Given an index e, we can effectively find an index i = f(h(e, j), j)

such that P_{i} is weakly equivalent to H(S_{e}, P_{j}) ∪ P_{j}.

Now, if S_{e} = ∅ then H(S_{e}, P_{j}) = ∅, hence P_{i} is weakly equivalent to P_{j}. On the other hand, if S_{e} ≠ ∅ then H(S_{e}, P_{j}) ≠ ∅ and for all h ∈ H(S_{e}, P_{j}) there is no g ∈ P_{j} such that g ≤_{T} h, hence P_{j} is not weakly reducible to P_{i}. Thus we see that the Π_{1}^{1} complete set {e | S_{e} = ∅} is reducible to both {i | p_{i} = p_{j}} and {i | p_{i} ≥ p_{j}} via the reduction e ↦ f(h(e, j), j). This proves our theorem.

Corollary 5.8. The index set {i | p_{i} = 1} is Π_{1}^{1} complete.

Proof. This is the special case p_{j} = 1 of Theorem 5.7.

Remark 5.9. All of the special cases p_{j} ≥ d of Theorem 5.7 can be given an alternative proof based on Theorems 2.6 and 3.8. An open question is to characterize the indices j such that {i | p_{i} ≤ p_{j}} is Π_{1}^{1} complete.

The following corollary of Theorem 5.7 is originally due to Simpson/Slaman [39] who proved it using a different method. Let P_{s} be the lattice of strong degrees of nonempty Π_{1}^{0} subsets of 2^{ω}.

Corollary 5.10. Each nonzero weak degree in P_{w} includes infinitely many strong degrees in P_{s}.

Proof. We begin with some background information. If P and Q are mass problems, we say that P is strongly reducible to Q if there exists a partial recursive functional Ψ such that Ψ(Y) ∈ P for all Y ∈ Q. A strong degree is an equivalence class of mass problems under strong reducibility. Obviously strong reducibility implies weak reducibility, but the converse does not hold. In the case of Π_{1}^{0} subsets of 2^{ω}, the strong reducibility relation

{(i, j) | P_{i} is strongly reducible to P_{j}}

is easily seen to be arithmetical, in fact Σ_{3}^{0}. (See for instance Simpson [34, Corollary 4.9] or Cenzer/Hinman [9].) On the other hand, Theorem 5.7 implies that the weak reducibility relation

{(i, j) | P_{i} is weakly reducible to P_{j}}

is Π_{1}^{1} complete, hence not arithmetical, hence not Σ_{3}^{0}.

To prove Corollary 5.10, let p > 0 be a weak degree in P_{w}. We must show that there exists an infinite set I ⊆ ω such that (a) for all i ∈ I, P_{i} is of weak degree p, and (b) for all i, j ∈ I, if i ≠ j then P_{i} and P_{j} are of different strong degrees. If such an I did not exist, then there would be a finite set of indices j_{1}, …, j_{n} such that for all i, P_{i} is of weak degree p if and only if P_{i} is of the same strong degree as one of P_{j_{1}}, …, P_{j_{n}}. Hence the index set

{i | P_{i} is of weak degree p}

would be Σ_{3}^{0}, contradicting Theorem 5.7 which says that this set is Π_{1}^{1} complete. This proves the corollary.

6 More on bounded limit recursiveness

This section is tangential to the rest of the paper. The purpose of this section is to compare our notion of bounded limit recursiveness, Definition 2.1 above, with other notions that have appeared in the recursion-theoretical literature.

Remark 6.1. Rogers [29, Chapters 8 and 9] and Downey/Jockusch/Stob [17] have considered truth-table reducibility and weak truth-table reducibility. For X, Y ∈ 2^{ω} we write X ≤_{tt} Y to mean that X is truth-table computable from Y. For f ∈ ω^{ω} and Y ∈ 2^{ω} we write f ≤_{wtt} Y to mean that f is weakly truth-table computable from Y. We sometimes identify a set A ⊆ ω with its characteristic function χ_{A} ∈ 2^{ω} defined by χ_{A}(n) = 1 if n ∈ A, 0 if n ∉ A.

Theorem 6.2. For f ∈ ω^{ω} we have f ∈ BLR(0) if and only if f ≤_{wtt} 0′, if and only if f occurs at level ≤ ω of the Ershov hierarchy.

Proof. The proof is straightforward. See Lemma 2.3 above, plus Rogers [29, Exercise 9-45, pages 158–159], plus Downey/Jockusch/Stob [17, paragraph preceding Definition 1.1], plus Arslanov [2]. Note also that, according to [17, Definition 1.1], a Turing oracle X is array recursive if and only if there exists g ≤_{wtt} 0′ which eventually dominates all f ≤_{T} X.

Remark 6.3. For arbitrary Turing oracles Y, it is not always the case that f ∈ BLR(Y) if and only if f ≤_{wtt} Y′. For example, let f ∈ ω^{ω} be so fastgrowing that f ≰_{wtt} Z for all Z ∈ 2^{ω}. In particular f ≰_{wtt} Y′ for all Turing oracles Y, but by Lemma 3.4 we have f ∈ BLR(Y) for some Y.

On the other hand, there is the following result for {0, 1}-valued functions.

Theorem 6.4. For X ⊆ ω we have X ∈ BLR(Y) if and only if X ≤_{tt} Y′.

Proof. Let g be the characteristic function of X. Note that g ∈ 2^{ω}. For the “if” part of the theorem, assume X ≤_{tt} Y′, i.e., g ≤_{tt} Y′. This means that there is a recursive mapping n ↦ ⟨τ_{n,i} | i < k_{n}⟩ such that for all n, g(n) = 1 if and only if (∃i < k_{n}) (τ_{n,i} ⊂ Y′). Let Y′ = ⋃_{s} Y′_{s} where Y′_{0} ⊆ Y′_{1} ⊆ ⋯ ⊆ Y′_{s} ⊆ Y′_{s+1} ⊆ ⋯ is a Y -recursive sequence of finite sets. Let g̃(n, s) = 1 if (∃i < k_{n}) (τ_{n,i} ⊂ Y′_{s}), 0 otherwise, and let ĝ(n) = max{|τ_{n,i}| | i < k_{n}}. Clearly g ∈ BLR(Y′) via the Y -recursive approximating function g̃ and the recursive bounding function ĝ.

For the “only if” part of the theorem, assume g ∈ BLR(Y′) via a Y -recursive approximating function g̃ and a recursive bounding function ĝ. We may safely assume that g̃(n, s) < 2 for all n and s, and g̃(n, 0) = 0 for all n. We now describe how to compute g from Y′. Given n, for each i < ĝ(n) ask the oracle Y′ whether |{s | g̃(n, s) ≠ g̃(n, s + 1)}| > i. Upon receiving the answers to these questions, we know the number |{s | g̃(n, s) ≠ g̃(n, s + 1)}|. Then g(n) = 0 if this number is even, 1 if it is odd. Thus X ≤_{tt} Y′, Q.E.D.

Corollary 6.5. For arbitrary Turing oracles X and Y, we have X′ ≤_{tt} Y′ if and only if X′ ∈ BLR(Y).

Proof. This is immediate from Theorem 6.4 upon recalling that X′ ⊆ ω.

Corollary 6.6. For arbitrary Turing oracles X and Y, the binary relation X′ ≤_{tt} Y′ is Σ_{3}^{0} in X and Y.

Proof. Let h be the characteristic function of X′. By Corollary 6.5, X′ ≤_{tt} Y′ if and only X′ ∈ BLR(Y), i.e., h ∈ BLR(Y). This holds if and only if there exist (indices for) a totally defined Y -recursive function h̃ and a totally defined recursive function ĥ such that

∀n (|{s | h̃(n, s) ≠ h̃(n, s + 1)}| < ĥ(n))

and

∀n (n ∈ X′ ⇒ ∀s ∃t (t > s and h̃(n, t) = 1))

and

∀n (n ∉ X′ ⇒ ∀s ∃t (t > s and h̃(n, t) = 0)).

By a Tarski/Kuratowski computation, this statement is Σ_{3}^{0} in X and Y.

Definition 6.7. We say that X is jump-traceable by Y (Simpson [35]) if there exist recursive functions f(n) and g(n) such that ∀n (φ_{n}^{(1),X}(n) ↓ ⇒ φ_{n}^{(1),X}(n) ∈ W_{f(n)}^{Y}) and ∀n (|W_{f(n)}^{Y}| ≤ g(n)).

Lemma 6.8. Assume that BLR(X) ⊆ BLR(Y). Then X is jump-traceable by Y and X′ ≤_{tt} Y′.

Proof. Assume BLR(X) ⊆ BLR(Y). By Lemma 2.5 the function

h(n) = h^{X}(n) = \{ \begin{matrix}φ_{n}^{(1),X}(n) + 1 & if φ_{n}^{(1),X}(n) ↓, \\ 0 & otherwise \end{matrix}

belongs to BLR(Y), say h(n) = lim_{s} h̃(n, s) and

|{s | h̃(n, s) ≠ h̃(n, s + 1)}| < ĥ(n)

where h̃ is Y -recursive and ĥ is recursive. By the S-m-n Theorem let f(n) be recursive such that W_{f(n)}^{Y} = {h̃(n, s) | s = 0, 1, 2, …} for all n. Then

h(n) ∈ W_{f(n)}^{Y} and |W_{f(n)}^{Y}| ≤ ĥ(n), hence X is jump-traceable by Y. To show that X′ ≤_{tt} Y′, note that X′ ∈ BLR(X), hence X′ ∈ BLR(Y), hence X′ ≤_{tt} Y′ by Theorem 6.4.

Remark 6.9. Lemma 6.8 may suggest that, in general, BLR(X) ⊆ BLR(Y) if and only if X is jump-traceable by Y and X′ ≤_{tt} Y′. We do not endorse such a conjecture, but we shall now prove some additional results in this direction.

Lemma 6.10. Assume that X is jump-traceable by Y and (X ⊕ Y)′ ≤_{tt} Y′. Then BLR(X) ⊆ BLR(Y).

Proof. Consider the partial X-recursive function θ^{X}(n) ≃ the least σ ⊂ X such that φ_{n,|σ|}^{(1),σ}(n) ↓. Clearly X′ = dom(θ^{X}) = {n | θ^{X}(n) ↓}. Since X is jump-traceable by Y, let f(n) and g(n) be recursive functions such that ∀n (θ^{X}(n) ↓ ⇒ θ^{X}(n) ∈ W_{f(n)}^{Y}) and ∀n (|W_{f(n)}^{Y}| ≤ g(n)). We may safely assume

that for all σ ∈ W_{f(n)}^{Y} we have φ_{n,|σ|}^{(1),σ}(n) ↓ and φ_{n,|ρ|}^{(1),ρ}(n) ↑ for all ρ ⊂ σ. Now for each n and each i < g(n) let σ_{n,i} ≃ the ith member of W_{f(n)}^{Y} in order of Y -

recursive enumeration. As in the proof of Lemma 6.8, let h^{X}(n) = φ_{n}^{(1),X}(n)+1 if φ_{n}^{(1),X}(n) ↓, 0 otherwise. We shall now describe how to compute h^{X}(n) from Y′. Since (X ⊕ Y)′ ≤_{tt} Y′, we can ask questions of the oracle (X ⊕ Y)′ via the oracle Y′. Given n, for each i < g(n) ask the oracle Y′ whether σ_{n,i} ↓ ⊂ X. After receiving the answers to these questions, we know the unique i < g(n) such that σ_{n,i} ↓ ⊂ X if such an i exists. We can then use the oracle Y to find this σ = σ_{n,i}. We then have h^{X}(n) = φ_{n,|σ|}^{(1),σ}(n) + 1 if σ exists, 0 otherwise. Since our use of Y′ in computing h^{X}(n) was recursively bounded, we have h^{X} ∈ BLR(Y) by Lemma 2.3. It then follows by Lemma 2.5 that BLR(X) ⊆ BLR(Y), Q.E.D.

Theorem 6.11. Assume that X ≥_{T} Y. Then BLR(X) ⊆ BLR(Y) if and only if X is jump-traceable by Y and X′ ≤_{tt} Y′.

Proof. The “only if” follows from Lemma 6.8. The “if” follows from Lemma 6.10 upon noting that X ≥_{T} Y and X′ ≤_{tt} Y′ imply (X ⊕ Y)′ ≤_{tt} Y′.

We say that X ⊆ ω is Y -recursively enumerable if X is the range of a Y - recursive function.

Theorem 6.12. Assume that X ≥_{T} Y and X is Y -recursively enumerable. Then the following are pairwise equivalent.

1. BLR(X) ⊆ BLR(Y).

2. X is jump-traceable by Y.

3. X′ ≤_{tt} Y′.

Proof. Lemma 6.8 gives 1 ⇒ 2 and 1 ⇒ 3. To prove 2 ⇒ 1, assume X is jump-traceable by Y. Let θ^{X}(n), h^{X}(n), f(n), g(n), σ_{n,i} be as in the proof of Lemma 6.10. Since X is Y -recursively enumerable, let X = ⋃_{s} X_{s} where X_{0} ⊆ X_{1} ⊆ ⋯ ⊆ X_{s} ⊆ X_{s+1} ⊆ ⋯ is a Y -recursive sequence of finite sets. We identify the sets X and X_{s} with their characteristic functions. We shall now describe how to compute h^{X}(n) from Y′. Given n, for each i < g(n) ask the oracle Y′ whether ∃s (σ_{n,i} ↓ ⊂ X_{s}) and whether ∃s ∃t (s < t and σ_{n,i} ↓ ⊂ X_{s} and σ_{n,i} ⊄ X_{t}). After receiving the answers to these 2g(n) questions, we know the unique i < g(n) such that σ_{n,i} ↓ ⊂ X if such an i exists. We can then use the oracle Y to find this σ = σ_{n,i}. We then have h^{X}(n) = φ_{n,|σ|}^{(1),σ}(n) + 1 if σ exists, 0 otherwise. Thus h^{X} ∈ BLR(Y). It follows by Lemma 2.5 that BLR(X) ⊆ BLR(Y). This finishes the proof of 2 ⇒ 1. To prove 3 ⇒ 2, recall the proof by Nies (see (ii)⇒(i) of [27, Theorem 4.1]) that if X is recursively enumerable and X′ ≤_{tt} 0′ then X is jump-traceable. The same proof relativizes to Y to give our implication 3 ⇒ 2.

We now draw some additional corollaries.

Definition 6.13. We say that X is superlow (see Mohrherr [25], Nies [27], Simpson [35]) if X′ ≤_{tt} 0′. We say that X is jump-traceable (see Nies [27], Simpson [35], Figueira/Nies/Stephan [20], Cholak/Downey/Greenberg [11], Downey/Greenberg [16]) if there exist recursive functions f(n), g(n) such that ∀n (φ_{n}^{(1),X}(n) ↓ ⇒ φ_{n}^{(1),X}(n) ∈ W_{f(n)}) and ∀n (|W_{f(n)}| < g(n)).

Corollary 6.14. The set {X | X is superlow} is Σ_{3}^{0}.

Proof. This is the special case Y = 0 of Corollary 6.6.

Corollary 6.15. For all X, BLR(X) ⊆ BLR(0) if and only if X is jumptraceable and superlow.

Proof. This is the special case Y = 0 of Theorem 6.11.

Remark 6.16. Nies [27] has shown that, in general, jump-traceability does not imply superlowness, and superlowness does not imply jump-traceability. In the following corollary, the equivalence 2 ⇔ 3 is due to Nies [27, Theorem 4.1].

Corollary 6.17. If X is recursively enumerable, the following are pairwise equivalent.

1. BLR(X) ⊆ BLR(0).

2. X is jump-traceable.

3. X is superlow.

Proof. This is the special case Y = 0 of Theorem 6.12.

Definition 6.18. We say that Y is superhigh (see Mohrherr [25], Binns/Kjos-Hanssen/Lerman/Solomon [7], Cholak/Greenberg/Miller [12], Kjos-Hanssen [22], Simpson [35]) if 0′′ ≤_{tt} Y′. We say that Y is generalized superhigh (see Barmpalias/Lewis/Soskova [4]) if (Y ⊕ 0′)′ ≤_{tt} Y′.

Corollary 6.19. For all Y the following are pairwise equivalent.

1. BLR(Y ⊕ 0′) ⊆ BLR(Y).

2. Y ⊕ 0′ is jump-traceable by Y.

3. Y is generalized superhigh.

Proof. This is the special case X = Y ⊕ 0′ of Theorem 6.12.

Corollary 6.20. The set {Y | Y is generalized superhigh} is Σ_{3}^{0}.

Proof. The method of Theorem 2.6 shows that, for any Σ_{3}^{0} binary relation S(X, Y), the set

{Y | ∃X (S(X, Y) and BLR(X) ⊆ BLR(Y))}

is Σ_{3}^{0}. Letting S(X, Y) be the binary relation X = Y ⊕ 0′, we see that the set {Y | BLR(Y ⊕ 0′) ⊆ BLR(Y)} is Σ_{3}^{0}. Our result then follows in view of Corollary 6.19.

Remark 6.21. We do not know whether the set {Y | Y is superhigh} is Σ_{3}^{0}, nor whether Y being superhigh is equivalent to BLR(0′) ⊆ BLR(Y). More generally, for 1 ≤ α < ω_{1}^{CK} we do not know whether 0^{(α+1)} ≤_{tt} Y′ is equivalent to BLR(0^{(α)}) ⊆ BLR(Y). If this were the case, it would follow by Theorems 2.6 and 4.7 that {Y | 0^{(α+1)} ≤_{tt} Y′} is Σ_{3}^{0} and of weak degree h_{α}^{∗}.

References

[1] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman. Comparing DNR and WWKL. Journal of Symbolic Logic, 69:1089– 1104, 2004.

[2] Marat M. Arslanov. Generalized tabular reducibilities in infinite levels of the Ershov difference hierarchy. In [5], pages 15–23, 2006.

[3] Christopher J. Ash and Julia Knight. Computable Structures and the Hyperarithmetical Hierarchy. Number 144 in Studies in Logic and the Foundations of Mathematics. North-Holland, 2000. XV + 346 pages.

[4] George Barmpalias, Andrew E. M. Lewis, and Mariya Soskova. Randomness, lowness and degrees. Journal of Symbolic Logic, 73:559–577, 1988.

[5] A. Beckmann, U. Berger, B. Löwe, and J. V. Tucker, editors. Logical Approaches to Computational Barriers: Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30 – July 5, 2006, Proceedings. Number 3988 in Lecture Notes in Computer Science. Springer-Verlag, 2006. XV + 608 pages.

[6] Stephen Binns. A splitting theorem for the Medvedev and Muchnik lattices. Mathematical Logic Quarterly, 49:327–335, 2003.

[7] Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, and David Reed Solomon. On a question of Dobrinen and Simpson concerning almost everywhere domination. Journal of Symbolic Logic, 71:119–136, 2006.

[8] Stephen Binns and Stephen G. Simpson. Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes. Archive for Mathematical Logic, 43:399– 414, 2004.

[9] Douglas Cenzer and Peter G. Hinman. Density of the Medvedev lattice of Π_{1}^{0} classes. Archive for Mathematical Logic, 42:583–600, 2003.

[10] Z. Chatzidakis, P. Koepke, and W. Pohlers, editors. Logic Colloquium ’02: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Colloquium Logicum, held in Münster, Germany, August 3–11, 2002. Number 27 in Lecture Notes in Logic. Association for Symbolic Logic, 2006. VIII + 359 pages.

[11] Peter Cholak, Rod Downey, and Noam Greenberg. Strong jumptraceability I: the computably enumerable case. Advances in Mathematics, 217:2045–2074, 2008.

[12] Peter Cholak, Noam Greenberg, and Joseph S. Miller. Uniform almost everywhere domination. Journal of Symbolic Logic, 71:1057–1072, 2006.

[13] C.-T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors. Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20 – August 15, 2005. Number 15 in Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific, 2008.

[14] S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors. Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Number 224 in London Mathematical Society Lecture Note Series. Cambridge University Press, 1996. VII + 347 pages.

[15] Oswald Demuth and Antonín Kučera. Remarks on 1-genericity, semigenericity and related concepts. Commentationes Mathematicae Universitatis Carolinae, 28:85–94, 1987.

[16] Rod Downey and Noam Greenberg. Strong jump-traceability II: the general case. 2007. In preparation.

[17] Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob. Array nonrecursive degrees and genericity. In [14], pages 93–105, 1996.

[18] B. Durand and W. Thomas, editors. STACS 2006: Twenty-Third Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23–25, 2006, Proceedings. Number 3884 in Lecture Notes in Computer Science. Springer-Verlag, 2006. XIX + 714 pages.

[19] J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors. Logic, Methodology and Philosophy of Science VIII. Number 126 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989. XVII + 702 pages.

[20] Santiago Figueira, André Nies, and Frank Stephan. Lowness properties and approximations of the jump. Annals of Pure and Applied Logic, 152:51–66, 2008.

[21] Carl G. Jockusch, Jr. Degrees of functions with no fixed points. In [19], pages 191–201, 1989.

[22] Bjørn Kjos-Hanssen. Low-for-random reals and positive-measure domination. Proceedings of the American Mathematical Society, 135:3703–3709, 2007.

[23] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. Kolmogorov complexity and the recursion theorem. In [18], pages 149–161, 2006.

[24] Masahiro Kumabe. A 1-generic degree with a strong minimal cover. Journal of Symbolic Logic, 65:1395–1442, 2000.

[25] Jeanleah Mohrherr. A refinement of low n and high n for the r.e. degrees. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 32:5– 12, 1986.

[26] Antonio Montalbán. Up to equimorphism, hyperarithmetic is recursive. Journal of Symbolic Logic, 70:360–378, 2005.

[27] André Nies. Reals which compute little. In [10], pages 260–274, 2006.

[28] André Nies, Richard A. Shore, and Theodore A. Slaman. Interpretability and definability in the recursively enumerable degrees. Proceedings of the London Mathematical Society, 77:241–291, 1998.

[29] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. XIX + 482 pages.

[30] Gerald E. Sacks. Higher Recursion Theory. Perspectives in Mathematical Logic. Springer-Verlag, 1990. XV + 344 pages.

[31] Joseph R. Shoenfield. Mathematical Logic. Addison–Wesley, 1967. VII + 344 pages.

[32] Stephen G. Simpson. First order theory of the degrees of recursive unsolvability. Annals of Mathematics, 105:121–139, 1977.

[33] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, 1999. XIV + 445 pages.

[34] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005.

[35] Stephen G. Simpson. Almost everywhere domination and superhighness. Mathematical Logic Quarterly, 53:462–482, 2007.

[36] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, 75:287–297, 2007.

[37] Stephen G. Simpson. Mass problems and almost everywhere domination. Mathematical Logic Quarterly, 53:483–492, 2007.

[38] Stephen G. Simpson. Some fundamental issues concerning degrees of unsolvability. In [13], pages 313–332, 2008.

[39] Stephen G. Simpson and Theodore A. Slaman. Medvedev degrees of Π_{1}^{0} subsets of 2^{ω}. July 2001. Preprint, 4 pages, in preparation, to appear.

[40] Hisao Tanaka. A property of arithmetic sets. Proceedings of the American Mathematical Society, 31:521–524, 1972.