An extension of the recursively enumerable Turing degrees

Stephen G. Simpson Department of Mathematics Pennsylvania State University University Park, State College PA, 16802, USA

              simpson@math.psu.edu
        http://www.math.psu.edu/simpson/

August 10, 2004

This research was partially supported by NSF grant DMS-0070718.

AMS Subject Classifications: 03D25, 03D30, 68Q30.

Journal of the London Mathematical Society, 75, 2007, pp. 287–297.

Abstract

Consider the countable semilattice R_{T} consisting of the recursively enumerable Turing degrees. Although R_{T} is known to be structurally rich, a major source of frustration is that no specific, natural degrees in R_{T} have been discovered, except the bottom and top degrees, 0 and 0′. In order to overcome this difficulty, we embed R_{T} into a larger degree structure which is better behaved. Namely, consider the countable distributive lattice P_{w} consisting of the weak degrees (a.k.a., Muchnik degrees) of mass problems associated with nonempty Π_{1}^{0} subsets of 2^{ω}. It is known that P_{w} contains a bottom degree 0 and a top degree 1 and is structurally rich. Moreover, P_{w} contains many specific, natural degrees other than 0 and 1. In particular, we show that in P_{w} one has 0 < d < r_{1} < inf(r_{2}, 1) < 1. Here d is the weak degree of the diagonally nonrecursive functions, and r_{n} is the weak degree of the n-random reals. It is known that r_{1} can be characterized as the maximum weak degree of a Π_{1}^{0} subset of 2^{ω} of positive measure. We now show that inf(r_{2}, 1) can be characterized as the maximum weak degree of a Π_{1}^{0} subset of 2^{ω} whose Turing upward closure is of positive measure. We exhibit a natural embedding of R_{T} into P_{w} which is one-to-one, preserves the semilattice structure of R_{T}, carries 0 to 0, and carries 0′ to 1. Identifying R_{T} with its image in P_{w}, we show that all of the degrees in R_{T} except 0 and 1 are incomparable with the specific degrees d, r_{1}, and inf(r_{2}, 1) in P_{w}.

Contents

Abstract 1

Contents 2

1 Introduction 2

2 Background: R_{T} and P_{w} 3

3 Some specific degrees in P_{w} 6

4 Some additional, specific degrees in P_{w} 9

5 Embedding R_{T} into P_{w} 11

References 13

1 Introduction

A principal object of study in recursion theory going back to the seminal work of Turing [36] and Post [25] has been the countable upper semilattice R_{T} of recursively enumerable Turing degrees, i.e., Turing degrees of recursively enumerable sets of positive integers. See the monographs of Sacks [27], Rogers [26], Soare [35], and Odifreddi [22, 23].

A major difficulty or obstacle in the study of R_{T} has been the lack of natural examples. Although it has long been known that R_{T} is infinite and structurally rich, to this day no specific, natural examples of recursively enumerable Turing degrees are known, beyond the two examples originally noted by Turing: 0′ = the Turing degree of the Halting Problem, and 0 = the Turing degree of solvable problems. Furthermore, 0′ and 0 are respectively the top and bottom elements of R_{T}. This paucity of examples in R_{T} is striking, because it is widely recognized that most other branches of mathematics are motivated and nurtured by a rich stock of examples. Clearly it ought to be of interest to somehow overcome this deficiency in the study of R_{T}.

In 1999 [30, 31] we defined a degree structure, here denoted P_{w}, which is closely related to R_{T}, but superior to R_{T} in at least two respects. First, P_{w} exhibits better structural behavior than R_{T}, in the sense that P_{w} is a countable distributive lattice, while R_{T} is not even a lattice. Second and more importantly, there are plenty of specific, natural degrees in P_{w} which are intermediate between 1 and 0, the top and bottom elements of P_{w}. Thus P_{w} does not suffer from the above-mentioned lack of examples, which plagues R_{T}.

In more detail, let P_{w} be the lattice of weak degrees (a.k.a., Muchnik degrees) of mass problems given by nonempty Π_{1}^{0} subsets of 2^{ω}. In 1999 [30] we showed that among the intermediate degrees in P_{w} is the specific degree r_{1} associated with the set of 1-random reals. The concept of 1-randomness was already well known from algorithmic information theory [19]. After 1999, we and other authors [2, 3, 4, 5, 32, 33, 34] continued the study of P_{w}, using priority arguments to prove structural properties, just as for R_{T}. In addition, we [33] discovered families of specific, natural, intermediate degrees in P_{w} related to foundationally interesting topics such as reverse mathematics, Gentzen-style proof theory, and computational complexity. Some additional degrees of this kind are presented in Sections 3 and 4 below.

The purpose of the present paper is to further clarify the relationship between the semilattice R_{T} and the lattice P_{w}. Namely, we exhibit a specific, natural embedding ϕ : R_{T} → P_{w} which is one-to-one, preserves the semilattice structure of R_{T}, and carries the top and bottom elements of R_{T} to the top and bottom elements of P_{w}. See Theorem 5.5 below. By identifying R_{T} with its image in P_{w}, we place the recursively enumerable Turing degrees into a wider context, where natural intermediate degrees occur. We view this as a step toward overcoming the above-mentioned difficulties concerning R_{T}.

At the same time, our embedding of R_{T} into P_{w} fails to solve the long standing open problem of finding a specific, natural, intermediate degree within R_{T} itself. Indeed, we shall see below (Theorem 5.6) that, regrettably, all of the intermediate degrees belonging to the image of R_{T} under our embedding are incomparable with all of the known natural intermediate degrees in P_{w}.

2 Background: R_{T} and P_{w}

In this section we review some basic information concerning the semilattice R_{T} and the lattice P_{w}.

Throughout this paper we shall use standard recursion-theoretic notation from Rogers [26] and Soare [35]. For special aspects of mass problems and Π_{1}^{0} sets, a convenient reference is [33].

We write ω = {0, 1, 2, …} for the set of natural numbers, ω^{ω} for the space of total functions from ω into ω, and 2^{ω} for the space of total functions from ω into {0, 1}. We sometimes identify a set A ⊆ ω with its characteristic function χ_{A} ∈ 2^{ω} given by χ_{A}(n) = 1 if n ∈ A, 0 if n ∉ A. For e, n, m ∈ ω and f ∈ ω^{ω} we write {e}^{f}(n) = m to mean that the Turing machine with Gödel number e and oracle f and input n eventually halts with output m. In the absence of an oracle f, we write {e}(n) = m. For P ⊆ ω^{ω} we consider recursive functionals Φ : P → ω^{ω} given by Φ(f)(n) = {e}^{f}(n) for some e ∈ ω and all f ∈ P and n ∈ ω. A function h : ω → ω is said to be recursive if there exists e ∈ ω such that h(n) = {e}(n) for all n ∈ ω. A set A ⊆ ω is said to be recursively enumerable if it is the image of a recursive function, i.e., A = {m | ∃n (h(n) = m)} for some recursive h : ω → ω.

For f, g ∈ ω^{ω} we write f ≤_{T} g to mean that f is Turing reducible to g, i.e., ∃e ∀n (f(n) = {e}^{g}(n)). The Turing degree of f, denoted deg_{T} (f), is the set of all g such that f ≡_{T} g, i.e., f ≤_{T} g and g ≤_{T} f. The set D_{T} of all Turing degrees is partially ordered by putting deg_{T} (f) ≤ deg_{T} (g) if and only if f ≤_{T} g. Under this partial ordering, the bottom element of D_{T} is 0 = {f ∈ ω^{ω} | f is recursive}. Within D_{T}, the least upper bound of deg_{T} (f) and deg_{T} (g) is deg_{T} (f ⊕ g) where (f ⊕ g)(2n) = f(n) and (f ⊕ g)(2n + 1) = g(n) for all n ∈ ω. A Turing degree a is said to be recursively enumerable if a = deg_{T} (χ_{A}) where A ⊆ ω is recursively enumerable. The set of all recursively enumerable Turing degrees is denoted R_{T}. It is easy to see that R_{T} is closed under the least upper bound operation inherited from D_{T}. The top and bottom elements of R_{T} are 0′ and 0 respectively, where 0′ = deg_{T} (H) is the Turing degree of the Halting Problem, H = {e | ∃m ({e}(0) = m)}. Thus R_{T} is a countable upper semilattice with a top and bottom element.

Definition 2.1. Let P, Q be subsets of ω^{ω}. We say that P is weakly reducible to Q, written P ≤_{w} Q, if for all g ∈ Q there exists f ∈ P such that f ≤_{T} g. The weak degree of P, written deg_{w}(P), is the set of all Q such that P ≡_{w} Q, i.e., P ≤_{w} Q and Q ≤_{w} P. The set D_{w} of all weak degrees is partially ordered by putting deg_{w}(P) ≤ deg_{w}(Q) if and only if P ≤_{w} Q. The concept of weak reducibility goes back to Muchnik [21] and has sometimes been called Muchnik reducibility.

Theorem 2.2. D_{w} is a complete distributive lattice.

Proof. The least upper bound of deg_{w}(P) and deg_{w}(Q) in D_{w} is deg_{w}(P × Q) where

P × Q = {f ⊕ g | f ∈ P and g ∈ Q}.

The greatest lower bound of deg_{w}(P) and deg_{w}(Q) in D_{w} is deg_{w}(P ∪ Q). The bottom element of D_{w} is

0 = {P ⊆ ω^{ω} | ∃f (f ∈ P and f is recursive)}.

Note that P ≤_{w} Q if and only if P̂ ⊇ Q̂, where P̂ is the Turing upward closure of P,

P̂ = {g ∈ ω^{ω} | (∃f ∈ P) (f ≤_{T} g)}.

Thus the lattice of weak degrees, D_{w}, is inversely isomorphic to the lattice of subsets of ω^{ω} which are upward closed with respect to ≤_{T}. It follows that D_{w} is a complete distributive lattice. □

Remark 2.3. There is an obvious, natural embedding of D_{T} into D_{w} given by deg_{T} (f) ↦ deg_{w}({f}). Here {f} is the singleton set whose only member is f. This embedding is one-to-one, preserves the partial ordering relation and least upper bound operation from D_{T}, and carries 0 to 0. Compare this with our embedding of R_{T} into P_{w} in Theorem 5.5 below.

Definition 2.4. A predicate R ⊆ ω^{ω} × ω is said to be recursive if

∃e ∀f ∀n ({e}^{f}(n) = 1 if R(f, n), and {e}^{f}(n) = 0 if ¬R(f, n)).

A set P ⊆ ω^{ω} is said to be Π_{1}^{0} if there exists a recursive predicate R ⊆ ω^{ω} × ω such that P = {f | ∀n R(f, n)}. A set S ⊆ ω^{ω} is said to be Σ_{3}^{0} if there exists a recursive predicate R ⊆ ω^{ω} ×ω×ω×ω such that S = {f | ∃k ∀m ∃n R(f, k, m, n)}. Other levels of the arithmetical hierarchy are defined similarly.

Definition 2.5. A set P ⊆ ω^{ω} is said to be recursively bounded if there exists a recursive function h such that ∀n (f(n) < h(n)) for all f ∈ P.

Definition 2.6. For P, Q ⊆ ω^{ω}, a recursive homeomorphism of P onto Q is a recursive functional Φ : P → Q mapping P one-to-one onto Q such that the inverse functional Φ^{−1} : Q → P is recursive. In this case we say that P and Q are recursively homeomorphic.

Theorem 2.7. P ⊆ ω^{ω} is recursively bounded Π_{1}^{0} if and only if P is recursively homeomorphic to a Π_{1}^{0} set P^{∗} ⊆ 2^{ω}.

Proof. See [33, Theorems 4.7 and 4.10]. □

Corollary 2.8. The weak degrees of nonempty recursively bounded Π_{1}^{0} sets are the same as the weak degrees of nonempty Π_{1}^{0} subsets of 2^{ω}.

Proof. This is immediate from Theorem 2.7. □

Definition 2.9. P_{w} is the set of weak degrees of nonempty Π_{1}^{0} subsets of 2^{ω}.

Theorem 2.10. P_{w} is a countable distributive lattice with a top and bottom element, denoted 1 and 0 respectively.

Proof. If P and Q are Π_{1}^{0} subsets of 2^{ω}, then so are P × Q and P ∪ Q. Thus P_{w} is closed under the least upper bound and greatest lower bound operations inherited from D_{w}. Clearly P_{w} is countable, because there are only countably many Π_{1}^{0} subsets of 2^{ω}. Clearly 0 = deg_{w}(2^{ω}) is the bottom element of P_{w}. Let PA be the set of completions of Peano Arithmetic. Identifying sentences with their Gödel numbers, we may view PA as a Π_{1}^{0} subset of 2^{ω}. By Scott [29], deg_{w}(PA) = 1 is the top element of P_{w}. See also [33, Section 6]. □

Remark 2.11. Just like the countable semilattice R_{T}, the countable distributive lattice P_{w} is known to be structurally rich. Binns/Simpson [2, 5] have shown that every countable distributive lattice is lattice embeddable in every nontrivial initial segment of P_{w}. Binns [2, 3] has obtained the P_{w} analog of the Sacks Splitting Theorem for R_{T} [27]. Namely, for all p, q > 0 in P_{w} there exist q_{1}, q_{2} ∈ P_{w} such that q_{1}, q_{2} ≱ p and sup(q_{1}, q_{2}) = q. (The P_{w} analog of the Sacks Density Theorem for R_{T} [28] remains as an open problem.) These structural results for P_{w} are proved by means of priority arguments. They invite comparison with the older, known results for R_{T}, which were also proved by means of priority arguments.

We end this section by mentioning some technical notions and results concerning trees and almost recursiveness.

A finite sequence of natural numbers σ = ⟨σ(0), …, σ(k − 1)⟩ is called a string of length k. The set of all strings is denoted ω^{<ω}. The set of strings of 0’s and 1’s is denoted 2^{<ω}. If σ, τ are strings of length k, l respectively, then the concatenation

σ^{⌢}τ = ⟨σ(0), …, σ(k − 1), τ(0), …, τ(l − 1)⟩

is a string of length k + l. We write σ ⊆ τ if σ^{⌢}ρ = τ for some ρ. If σ is a string of length k, then for all f ∈ ω^{ω} we have σ^{⌢}f ∈ ω^{ω} defined by (σ^{⌢}f)(i) = σ(i) for i < k, f(i − k) for i ≥ k. We write σ ⊂ f if σ^{⌢}g = f for some g ∈ ω^{ω}.

A tree is a set T ⊆ ω^{<ω} such that, for all σ ⊆ τ ∈ T, σ ∈ T. A path through T is an f ∈ ω^{ω} such that (∀σ ⊂ f) (σ ∈ T). The set of all paths through T is denoted [T]. We sometimes identify a string σ with its Gödel number #(σ) ∈ ω. A tree T is said to be recursive if {#(σ) | σ ∈ T } is recursive.

Theorem 2.12. P ⊆ ω^{ω} is Π_{1}^{0} if and only if P = [T] for some recursive tree T ⊆ ω^{<ω}. P ⊆ 2^{ω} is Π_{1}^{0} if and only if P = [T] for some recursive tree T ⊆ 2^{<ω}.

Proof. See [33, Theorem 4.3]. □

Definition 2.13. We say that g ∈ ω^{ω} is almost recursive if for all f ≤_{T} g there exists a recursive function h such that ∀n (f(n) < h(n)).

Theorem 2.14. Suppose g is almost recursive. Then for all f ≤_{T} g we have f = Φ(g) for some total recursive functional Φ : ω^{ω} → ω^{ω}.

Proof. See [33, Theorem 4.18]. □

The following result is known as the Almost Recursive Basis Theorem.

Theorem 2.15. If P ⊆ 2^{ω} is Π_{1}^{0} and nonempty, then there exists g ∈ P such that g is almost recursive.

Proof. This is a restatement of the Hyperimmune-Free Basis Theorem of [15, Theorem 2.4]. See also [33, Theorem 4.19]. □

3 Some specific degrees in P_{w}

In this section we identify and characterize some specific, natural degrees in P_{w}, and we investigate their degree-theoretic properties.

Definition 3.1. Let μ be the “fair coin” probability measure on 2^{ω} given by μ({f ∈ 2^{ω} | f ⊃ σ}) = 1/2^{|σ|} for all σ ∈ 2^{<ω}. Let C be a Turing oracle. A point f ∈ 2^{ω} is said to be C-random if there does not exist a recursive sequence of Σ_{1}^{0,C} sets U_{i}^{C} ⊆ 2^{ω}, i ∈ ω, such that μ(U_{i}^{C}) ≤ 1/2^{i} and f ∈ ⋂_{i=0}^{∞} U_{i}^{C}. If C = 0^{(n−1)} = the (n−1)st Turing jump of 0, where 0 is recursive and n ≥ 1, then f is said to be n-random.

Thus f is 1-random if and only if f is random in the sense of Martin-Löf [20], and f is 2-random if and only if f is random relative to the Halting Problem. For a thorough treatment of randomness and n-randomness, see Kautz [16] or Downey/Hirschfeldt [8]. We write

R_{n} = {f ∈ 2^{ω} | f is n-random}.

Note that μ(R_{n}) = 1.

Lemma 3.2. R_{n} is Σ_{n+1}^{0}. In particular, R_{1} is Σ_{2}^{0}, and R_{2} is Σ_{3}^{0}.

Proof. It is is well known (see for instance [33, Theorem 8.3]) that R = R_{1} is Σ_{2}^{0}. Relativizing to C we see that R^{C} = {f ∈ 2^{ω} | f is C-random} is Σ_{2}^{0,C}, i.e., Σ_{2}^{0} relative to C. Putting C = 0^{(n−1)}, we see that R_{n} is Σ_{2}^{0} relative to 0^{(n−1)}. From this it follows easily that R_{n} is Σ_{n+1}^{0}. □

Lemma 3.3. Let S ⊆ ω^{ω} be Σ_{3}^{0}, and let P ⊆ 2^{ω} be nonempty Π_{1}^{0}. Then we can find a nonempty Π_{1}^{0} set Q ⊆ 2^{ω} such that Q ≡_{w} S ∪ P.

Proof. First use a Skolem function technique to reduce to the case where S is Π_{1}^{0}. Namely, fix a recursive predicate R such that S = {f | ∃k ∀n ∃m R(f, k, n, m)}, and replace S by the set of all ⟨k⟩^{⌢}(f ⊕ g) ∈ ω^{ω} such that ∀n R(f, k, n, g(n)) holds. Clearly the latter set is ≡_{w} S and Π_{1}^{0}. Assuming now that S is a Π_{1}^{0} subset of ω^{ω}, let T_{S} be a recursive subtree of ω^{<ω} such that S is the set of paths through T_{S}. We may safely assume that, for all τ ∈ T_{S} and n < the length of τ, τ(n) ≥ 2. Let T_{P} be a recursive subtree of 2^{<ω} such that P is the set of paths through T_{P}. Define T_{Q} to be the set of strings ρ ∈ ω^{<ω} of the form

ρ = σ_{0}^{⌢}⟨m_{0}⟩^{⌢}σ_{1}^{⌢}⟨m_{1}⟩^{⌢} ⋯^{⌢}⟨m_{k−1}⟩^{⌢}σ_{k}

where ⟨m_{0}, m_{1}, …, m_{k−1}⟩ ∈ T_{S}, σ_{0}, σ_{1}, …, σ_{k} ∈ T_{P}, and ρ(n) ≤ max(n, 2) for all n < the length of ρ. Thus T_{Q} is a recursive subtree of ω^{<ω}. Let Q ⊆ ω^{ω} be the set of paths through T_{Q}. (Compare the construction of T in Jockusch/Soare [14].) It is straightforward to verify that Q ≡_{w} S ∪ P. Note that Q is Π_{1}^{0} and recursively bounded. By Theorem 2.7 we can find a Π_{1}^{0} set Q^{∗} ⊆ 2^{ω} which is recursively homeomorphic to Q. This completes the proof. □

Lemma 3.4. There exist Π_{1}^{0} sets P_{1}, P_{2} ⊆ 2^{ω} such that P_{1} ≡_{w} R_{1} and

P_{2} ≡_{w} R_{2} ∪ PA.

Proof. By Lemmas 3.2 and 3.3 we can find Π_{1}^{0} sets P_{1}, P_{2} ⊆ 2^{ω} such that P_{1} ≡_{w} R_{1} ∪ PA and P_{2} ≡_{w} R_{2} ∪ PA. Since R_{1} is nonempty and Σ_{2}^{0}, there is a nonempty Π_{1}^{0} set Q ⊆ R_{1}. Then Q ≤_{w} PA, hence R_{1} ≤_{w} PA, hence P_{1} ≡_{w} R_{1} ∪ PA ≡_{w} R_{1}. □

Definition 3.5. We write r_{n} = deg_{w}(R_{n}) and

r_{n}^{∗} = inf(r_{n}, 1) = deg_{w}(R_{n} ∪ PA).

Theorem 3.6. We have r_{1} ∈ P_{w} and r_{2}^{∗} ∈ P_{w} and 0 < r_{1} < r_{2}^{∗} < 1.

Proof. By Lemma 3.4 there are Π_{1}^{0} sets P_{1}, P_{2} ⊆ 2^{ω} such that r_{1} = deg_{w}(P_{1}) and r_{2}^{∗} = deg_{w}(P_{2}). Thus r_{1}, r_{2}^{∗} ∈ P_{w} and r_{1}, r_{2}^{∗} ≤ 1. Clearly R_{1} ⊇ R_{2}, hence r_{1} ≤ r_{2}. Clearly R_{1} has no recursive member, i.e., r_{1} > 0. By [33, Section 7] or [15, Corollary 5.4], the Turing upward closure of PA is of measure 0, i.e., PA ≰_{w} S for all S ⊆ 2^{ω} of positive measure. In particular PA ≰_{w} R_{2}, i.e., 1 ≰ r_{2}. Summarizing, we have now shown that 0 < r_{1} ≤ inf(r_{2}, 1) = r_{2}^{∗} < 1.

It remains to show that r_{1} ≱ r_{2}^{∗}, i.e., R_{1} ≱_{w} R_{2} ∪ PA. By Lemma 3.2, let P be a nonempty Π_{1}^{0} subset of R_{1}. By the Almost Recursive Basis Theorem 2.15, let g ∈ P be almost recursive. By Kautz [16, Theorem IV.2.4(iv)] or Dobrinen/Simpson [7, Remark 2.8], there is no almost recursive f ∈ R_{2}. In particular, there is no f ∈ R_{2} such that f ≤_{T} g. Suppose there were f ∈ PA such that f ≤_{T} g. By Theorem 2.14 let Φ : 2^{ω} → 2^{ω} be a total recursive functional such that f = Φ(g). Put \overline{P} = \{\overline{g} ∈ P | Φ(\overline{g}) ∈ PA\}. We have Φ(g) = f ∈ PA, hence g ∈ \overline{P}, hence \overline{P} is nonempty. Since P and PA are Π_{1}^{0}, it follows by [33, Theorem 4.4] that \overline{P} ⊆ P ⊆ R_{1} is Π_{1}^{0}. Hence, by [33, Lemma 8.8], \overline{P} is of positive measure. Since Φ : \overline{P} → PA, it follows that the Turing upward closure of PA is of positive measure, but this is a contradiction. We have now shown that, for a particular g ∈ R_{1}, there is no f ≤_{T} g such that f ∈ R_{2} ∪ PA. Thus R_{2} ∪ PA ≰_{w} R_{1}, and this completes the proof. □

Remark 3.7. As an application of Theorem 3.6, we can find essentially undecidable, finitely axiomatizable theories T_{1} and T_{2} in the first-order predicate calculus, with the following properties: every 1-random real computes a completion of T_{1}; every 2-random real but not every 1-random real computes a completion of T_{2}. This follows from Theorem 3.6 plus the well known, general relationship between Π_{1}^{0} subsets of 2^{ω} and finitely axiomatizable theories. See [32, Theorem 3.18 and Remark 3.19] and Peretyatkin [24].

Theorem 3.8. We can characterize r_{1} as the maximum weak degree of a Π_{1}^{0} subset of 2^{ω} of positive measure. We can characterize r_{2}^{∗} as the maximum weak degree of a Π_{1}^{0} subset of 2^{ω} whose Turing upward closure is of positive measure.

Proof. The first statement is [33, Theorem 8.10]. For the second statement, assume that Q is a Π_{1}^{0} subset of 2^{ω} whose Turing upward closure Q̂ is of positive measure. A computation in the style of Tarski and Kuratowski (compare Rogers [26, Section 14.3]) shows that Q̂ is Σ_{3}^{0}. Since Q̂ is Σ_{3}^{0} of positive measure, let Q′ ⊆ Q̂ be Π_{2}^{0} of positive measure. By Kautz [16, Lemma II.1.4(ii)] or Dobrinen/Simpson [7, Theorem 3.3], we may assume that Q′ is Π_{1}^{0} relative to 0′. Relativizing [33, Lemma 8.7] to 0′, we have Q′ ≤_{w} R_{2}. Since Q′ ⊆ Q̂, it follows that Q̂ ≤_{w} R_{2}, hence Q ≤_{w} R_{2}. Furthermore, since Q is a nonempty Π_{1}^{0} subset of 2^{ω}, we have Q ≤_{w} PA. We now see that Q ≤_{w} R_{2} ∪ PA, i.e., deg_{w}(Q) ≤ r_{2}^{∗}. On the other hand, by Theorem 3.6 let P_{2} be a Π_{1}^{0} subset of 2^{ω} such that deg_{w}(P_{2}) = r_{2}^{∗}. Note that P̂_{2} ⊇ R_{2}, hence P̂_{2} is of positive measure. We have now shown that r_{2}^{∗} is the maximum deg_{w}(Q) ∈ P_{w} such that Q̂ is of positive measure. This completes the proof of our theorem. □

Corollary 3.9. Let Q be a nonempty Π_{1}^{0} subset of 2^{ω}. Then Q ≤_{w} R_{2} if and only if Q̂ is of positive measure.

Proof. If Q ≤_{w} R_{2} then trivially Q̂ ⊇ R_{2}, hence Q̂ is of measure 1. Conversely, if Q̂ is of positive measure, then by Theorem 3.8 we have Q ≤_{w} R_{2}. □

Corollary 3.10. We can find a Π_{1}^{0} set Q ⊆ 2^{ω} whose Turing upward closure Q̂ is of positive measure yet does not include any Π_{1}^{0} set of positive measure.

Proof. By Theorem 3.6 let Q ⊆ 2^{ω} be Π_{1}^{0} such that deg_{w}(Q) = r_{2}^{∗}. By Theorem 3.8, Q̂ is of positive measure. If there were a Π_{1}^{0} set P ⊆ Q̂ of positive measure, then by Theorem 3.8 we would have r_{1} ≥ deg_{w}(P) ≥ deg_{w}(Q) = r_{2}^{∗}, contradicting Theorem 3.6. □

Theorem 3.11. Let p, q ∈ P_{w}. If r_{1} ≥ inf(p, q) then either r_{1} ≥ p or r_{1} ≥ q. If r_{2}^{∗} ≥ inf(p, q) then either r_{2}^{∗} ≥ p or r_{2}^{∗} ≥ q.

Proof. The first statement is [33, Theorem 8.12, part 3]. For the second statement, let P, Q ⊆ 2^{ω} be nonempty Π_{1}^{0} subsets of 2^{ω} with p = deg_{w}(P) and q = deg_{w}(Q). Trivially inf(p, q) = deg_{w}(P ∪ Q). Moreover { \atop P ∪ Q} = P̂ ∪ Q̂, hence { \atop P ∪ Q} is of positive measure if and only if at least one of P̂ and Q̂ is of positive measure. By Corollary 3.9 this means that r_{2}^{∗} ≥ inf(p, q) if and only if r_{2}^{∗} ≥ at least one of p and q. □

Definition 3.12. As in [33, Section 7], say that s ∈ P_{w} is separating if there is a pair of disjoint, recursively enumerable sets A, B ⊆ ω such that s = deg_{w}(S) where S = {f ∈ 2^{ω} | f separates A, B}. In particular, 1 is separating.

Theorem 3.13. If s is separating and s ≤ sup(q, r_{n}), then s ≤ q.

Proof. This is a special case of [33, Theorem 7.5]. □

Corollary 3.14. For all weak degrees q < 1, we have sup(q, r_{2}^{∗}) < 1.

Proof. Assume q < 1. By the definition of r_{2}^{∗}, we have r_{2}^{∗} ≤ 1, hence sup(q, r_{2}^{∗}) ≤ 1. Since 1 is separating and q ≱ 1, Theorem 3.13 tells us that sup(q, r_{2}) ≱ 1, hence sup(q, r_{2}^{∗}) ≱ 1. □

Corollary 3.15. Within the lattice P_{w}, the degrees r_{1} and r_{2}^{∗} are meet-irreducible and do not join to 1.

Proof. This follows from Theorem 3.11 and Corollary 3.14. □

4 Some additional, specific degrees in P_{w}

In this section we identify some additional specific, natural, intermediate degrees in P_{w} related to diagonal nonrecursiveness.

Definition 4.1. A function g : ω → ω is said to be diagonally nonrecursive if g(n) ≠ {n}(n) for all n ∈ ω. We put d = deg_{w}(DNR) where

DNR = {g ∈ ω^{ω} | g is diagonally nonrecursive}.

The Turing degrees of diagonally nonrecursive functions have been studied by Jockusch [12]. In particular, a Turing degree contains a diagonally nonrecursive function if and only if it contains a fixed point free function, if and only if it contains an effectively immune set, if and only if it contains an effectively biimmune set. Thus we see that the weak degree d is recursion-theoretically natural.

Theorem 4.2. We have d ∈ P_{w}.

Proof. Put DNR_{2} = {g ∈ 2^{ω} | g is diagonally nonrecursive}. Obviously DNR_{2} is a nonempty Π_{1}^{0} subset of 2^{ω}. By Lemma 3.3 we can find a nonempty Π_{1}^{0} set Q ⊆ 2^{ω} such that Q ≡_{w} DNR ∪ DNR_{2}. But DNR ⊇ DNR_{2}, hence Q ≡_{w} DNR. We now see that d = deg_{w}(DNR) = deg_{w}(Q) ∈ P_{w}. □

Theorem 4.3. In P_{w} we have

0 < d < r_{1} < r_{2}^{∗} < 1.

Proof. By Theorem 3.6 we have 0 < r_{1} < r_{2}^{∗} < 1. Clearly DNR has no recursive member, i.e., d > 0. By Giusto/Simpson [11, Lemma 6.18], for all f ∈ R_{1} there exists g ≤_{T} f such that g ∈ DNR. Thus we have 0 < d ≤ r_{1}. It remains to show that d ≱ r_{1}. By Kumabe [18] there is a diagonally nonrecursive function which is of minimal Turing degree. But if f ∈ 2^{ω} is 1-random, then f is not of minimal Turing degree, because the functions g and h defined by f = g ⊕ h are Turing incomparable (see for instance van Lambalgen [37]). This proves d ≱ r_{1}. An alternative reference for the conclusion d ≱ r_{1} is Ambos-Spies et al [1, Theorems 1.4 and 2.1]. □

Definition 4.4. Let DNR_{REC} be the set of recursively bounded DNR functions. Thus we have

DNR_{REC} = {g ∈ DNR | (∃ recursive h) ∀n (g(n) < h(n))}.

Put d_{REC} = deg_{w}(DNR_{REC}). For an extended discussion of the recursiontheoretic naturalness of d_{REC} and related weak degrees, see [33, Section 10].

Theorem 4.5. We have d_{REC} ∈ P_{w} and

0 < d < d_{REC} < r_{1} < r_{2}^{∗} < 1.

Proof. A Tarski/Kuratowski computation shows that DNR_{REC} is Σ_{3}^{0}. Let DNR_{2} be as in the proof of Theorem 4.2. By Lemma 3.3 we can find a nonempty Π_{1}^{0} set Q_{REC} ⊆ 2^{ω} such that Q_{REC} ≡_{w} DNR_{REC} ∪ DNR_{2} = DNR_{REC}. Thus d_{REC} = deg_{w}(DNR_{REC}) = deg_{w}(Q_{REC}) ∈ P_{w}. By Ambos-Spies et al [1, Theorems 1.4, 1.8, 1.9] we have d < d_{REC} < r_{1}, and the rest is from Theorem 4.3. □

Definition 4.6. For all f ∈ ω^{ω} put

DNR^{f} = {g ∈ ω^{ω} | ∀n (g(n) ≠ {n}^{f}(n))},

the set of functions which are diagonally nonrecursive relative to f. Put DNR^{1} = DNR and, for each n ≥ 1,

DNR^{n+1} = {f ⊕ g | f ∈ DNR^{n} and g ∈ DNR^{f}}.

Clearly DNR^{n} is a Π_{1}^{0} subset of ω^{ω}. Put d^{n} = deg_{w}(DNR^{n}).

Remark 4.7. Trivially d^{1} = d and d^{n} ≤ d^{n+1} for all n ≥ 1. The proofs of Theorems 4.2 and 4.3 show that d^{n} ∈ P_{w} and d^{n} < r_{1} for all n ≥ 1. By Kumabe [18] we have d^{1} < d^{2}, and we conjecture that d^{n} < d^{n+1} for all n. Thus in P_{w} we apparently have

0 < d = d^{1} < d^{2} < ⋯ < d^{n} < d^{n+1} < ⋯ < r_{1} < r_{2}^{∗} < 1.

Note also that the sequence d^{1} < ⋯ < d^{n} < ⋯ can be extended into the transfinite.

Remark 4.8. We conjecture that, for all n ≥ 2, d^{n} is incomparable with d_{REC}. Note also that these d^{n}’s are not to be confused with the d_{α}’s of Simpson [33, Example 10.14]. Indeed, we conjecture that, for all n ≥ 2 and α ≥ 0, d^{n} is incomparable with d_{α}.

Remark 4.9. We do not know of any specific, natural degrees in P_{w} outside the interval from d to r_{2}^{∗}, except 0 and 1. On the other hand, by Theorem 4.5 and Remarks 4.7 and 4.8, the interval from d to r_{2}^{∗} within P_{w} appears to be remarkably rich in specific, natural degrees.

5 Embedding R_{T} into P_{w}

In this section we exhibit a specific, natural embedding of the countable upper semilattice R_{T} into the countable distributive lattice P_{w}.

Definition 5.1. A Π_{2}^{0} singleton is a point f ∈ ω^{ω} such that the singleton set {f} is Π_{2}^{0}.

Lemma 5.2. Given a Π_{2}^{0} singleton f, we have deg_{w}({f} ∪ PA) ∈ P_{w}. Thus

ϕ : deg_{T} (f) ↦ deg_{w}({f} ∪ PA)  (1)

is an upper semilattice homomorphism of the Turing degrees of Π_{2}^{0} singletons into P_{w}.

Proof. The first statement is the special case of Lemma 3.3 with S = {f} and P = PA. For the second statement, note that for any f, g ∈ ω^{ω} and P ⊆ ω^{ω} we have {f ⊕g}∪P ≡_{w} ({f}∪P)×({g}∪P), and f ≤_{T} g implies {f}∪P ≤_{w} {g}∪P. In particular this holds when f and g are Π_{2}^{0} singletons and P = PA. □

Lemma 5.3. We have an upper semilattice homomorphism ϕ of the Turing degrees ≤ 0′ into P_{w}, given by (1). Moreover, ϕ(0) = 0 and ϕ(0′) = 1.

Proof. The first statement is a special case of Lemma 5.2, because deg_{T} (f) ≤ 0′ if and only if f is Δ_{2}^{0} (see Kleene [17, Theorem XI, page 293]), which implies that f is a Π_{2}^{0} singleton. It is easy to see that ϕ(0) = 0. To show that ϕ(0′) = 1, by Kleene [17, Theorem 38*, pages 401–402] let f ∈ PA be Δ_{2}^{0}. Then deg_{T} (f) ≤ 0′ and ϕ(deg_{T} (f)) = deg_{w}({f} ∪ PA) = deg_{w}(PA) = 1, hence ϕ(0′) = 1. □

Lemma 5.4. If a, b are Turing degrees ≤ 0′, and if b ∈ R_{T}, then a ≤ b if and only if ϕ(a) ≤ ϕ(b). In particular, the restriction of ϕ to R_{T} is one-to-one.

Proof. Let f, g ∈ ω^{ω} be such that deg_{T} (f) = a and deg_{T} (g) = b. We must show that f ≤_{T} g if and only if {f} ∪ PA ≤_{w} {g} ∪ PA. The “only if” part is trivial. For the “if” part, suppose {f} ∪ PA ≤_{w} {g} ∪ PA. In particular, {f} ∪ PA ≤_{w} {g}. If f ≰_{T} g, then PA ≤_{w} {g}, hence DNR ≤_{w} {g}, hence deg_{T} (g) = 0′ by the Arslanov Completeness Criterion [12], hence f ≤_{T} g, a contradiction. Thus f ≤_{T} g. This proves our lemma. □

We now obtain our main result.

Theorem 5.5. We have an embedding ϕ : R_{T} → P_{w} given by (1). The embedding ϕ is one-to-one, preserves the partial ordering relation and the least upper bound operation from R_{T}, carries 0 to 0, and carries 0′ to 1.

Proof. This result is obtained by combining Lemmas 5.3 and 5.4. □

Theorem 5.6. Let ϕ : R_{T} → P_{w} be the embedding given by (1). Let a ∈ R_{T} be a recursively enumerable Turing degree other than 0 and 0′. Then the weak degree ϕ(a) ∈ P_{w} is incomparable with each of the specific weak degrees d, r_{1}, r_{2}^{∗} ∈ P_{w} of Theorem 4.3.

Proof. By the Arslanov Completeness Criterion [12] we have ϕ(a) ≱ d. It remains to show that ϕ(a) ≰ r_{2}^{∗}. This is obvious, because for any nonrecursive A we have μ({f ∈ 2^{ω} | A ≤_{T} f}) = 0 [27, §10, Theorem 1]. □

We finish by noting some generalizations of Theorem 5.5.

Remark 5.7. A set A ⊆ ω is said to be n-REA if A = A_{1} ⊕ ⋯ ⊕ A_{n} where A_{1} is recursively enumerable and, for each i = 1, …, n − 1, A_{i+1} is recursively enumerable relative to A_{i} and ≥_{T} A_{i}. A Turing degree is said to be n-REA if it contains an n-REA set. Note that any n-REA set is a Π_{2}^{0} singleton. Hence by Lemma 5.2 we have ϕ(a) ∈ P_{w} for all n-REA Turing degrees a. Jockusch et al [13, Theorem 5.1] have generalized the Arslanov Completeness Criterion to n-REA Turing degrees. In our terms, their result says that if a is an n-REA Turing degree for some n ∈ ω, then ϕ(a) ≥ d if and only if a ≥ 0′, in which case ϕ(a) = 1. Therefore, letting R_{T}^{∗} (≤ 0′) denote the set of Turing degrees which are ≤ 0′ and n-REA for some n ∈ ω, we have as in Theorem 5.5 an embedding

ϕ : R_{T}^{∗} (≤ 0′) → P_{w}

which is one-to-one, preserves the partial ordering relation and the least upper bound operation from R_{T}^{∗} (≤ 0′), and carries 0 to 0 and 0′ to 1. Moreover, for all a ∈ R_{T}^{∗} (≤ 0′) other than 0 and 0′, we have as in Theorem 5.6 that ϕ(a) is incomparable with d, r_{1}, r_{2}^{∗}.

Remark 5.8. More generally, given q ∈ P_{w} such that q ≥ d, we have an embedding

ϕ_{q} : R_{T}^{∗} (≤ 0′) → P_{w}(≤ q)

defined by ϕ_{q}(a) = inf(ϕ(a), q). The embedding ϕ_{q} is one-to-one, preserves the partial ordering relation and least upper bound operation from R_{T}^{∗} (≤ 0′), carries 0 to 0, and carries 0′ to q. If we set q = 1, we recover the embedding ϕ : R_{T}^{∗} (≤ 0′) → P_{w} of Remark 5.7. If we set q = 1 and restrict to R_{T}, we recover the embedding ϕ : R_{T} → P_{w} of Theorem 5.5.

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] Stephen Binns. The Medvedev and Muchnik Lattices of Π_{1}^{0} Classes. PhD thesis, Pennsylvania State University, August 2003. VII + 80 pages.

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

[4] Stephen Binns. Small Π_{1}^{0} classes. Archive for Mathematical Logic, 45:393– 410, 2006.

[5] 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.

[6] J. C. E. Dekker, editor. Recursive Function Theory. Proceedings of Symposia in Pure Mathematics. American Mathematical Society, 1962. VII + 247 pages.

[7] Natasha L. Dobrinen and Stephen G. Simpson. Almost everywhere domination. Journal of Symbolic Logic, 69:914–922, 2004.

[8] Rodney G. Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. May 2004. Preprint, 305 pages, in preparation, to appear.

[9] 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.

[10] FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/. September 1997 to the present.

[11] Mariagnese Giusto and Stephen G. Simpson. Located sets and reverse mathematics. Journal of Symbolic Logic, 65:1451–1480, 2000.

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

[13] Carl G. Jockusch, Jr., Manuel Lerman, Robert I. Soare, and Robert M. Solovay. Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion. Journal of Symbolic Logic, 54:1288– 1323, 1989.

[14] Carl G. Jockusch, Jr. and Robert I. Soare. Degrees of members of Π_{1}^{0} classes. Pacific Journal of Mathematics, 40:605–616, 1972.

[15] Carl G. Jockusch, Jr. and Robert I. Soare. Π_{1}^{0} classes and degrees of theories. Transactions of the American Mathematical Society, 173:35–56, 1972.

[16] Steven M. Kautz. Degrees of Random Sets. PhD thesis, Cornell University, 1991. X + 89 pages.

[17] Stephen C. Kleene. Introduction to Metamathematics. Van Nostrand, 1952. X + 550 pages.

[18] Masahiro Kumabe. A fixed point free minimal degree. 1997. Preprint, 48 pages.

[19] Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and its Applications. Graduate Texts in Computer Science. Springer-Verlag, 2nd edition, 1997. XX + 637 pages.

[20] Per Martin-Löf. The definition of random sequences. Information and Control, 9:602–619, 1966.

[21] Albert A. Muchnik. On strong and weak reducibilities of algorithmic problems. Sibirskii Matematicheskii Zhurnal, 4:1328–1341, 1963. In Russian.

[22] Piergiorgio Odifreddi. Classical Recursion Theory. Number 125 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989. XVII + 668 pages.

[23] Piergiorgio Odifreddi. Classical Recursion Theory, Volume 2. Number 143 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1999. XVI + 949 pages.

[24] Mikhail G. Peretyatkin. Finitely Axiomatizable Theories. Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997. XIV + 294 pages.

[25] Emil L. Post. Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, 50:284– 316, 1944.

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

[27] Gerald E. Sacks. Degrees of Unsolvability. Number 55 in Annals of Mathematics Studies. Princeton University Press, 1963. IX + 174 pages.

[28] Gerald E. Sacks. The recursively enumerable degrees are dense. Annals of Mathematics, 80:300–312, 1964.

[29] Dana S. Scott. Algebras of sets binumerable in complete extensions of arithmetic. In [6], pages 117–121, 1962.

[30] Stephen G. Simpson. FOM: natural r.e. degrees; Pi01 classes. FOM e-mail list [10], 13 August 1999.

[31] Stephen G. Simpson. FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes. FOM e-mail list [10], 16 August 1999.

[32] Stephen G. Simpson. Mass problems. 24 May 2004. Preprint, 24 pages, submitted for publication.

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

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

[35] Robert I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag, 1987. XVIII + 437 pages.

[36] Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230–265, 1936.

[37] Michiel van Lambalgen. Von Mises’ definition of random sequences reconsidered. Journal of Symbolic Logic, 52:725–755, 1987.