Mass problems and density^{∗}

Stephen Binns

Department of Mathematics, Statistics, and Physics

College of Arts and Sciences, Qatar University

PO Box 2713, Doha, QATAR sbinns@qu.edu.qa

Richard A. Shore Department of Mathematics

Cornell University Ithaca, NY 14853, USA

http://www.math.cornell.edu/∼shore shore@math.cornell.edu

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

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

November 15, 2015

∗Shore’s research was partially supported by NSF Grants DMS-0852811 and DMS-1161175. Simpson’s research was partially supported by the Eberly College of Science at the Pennsylvania State University, and by Simons Foundation Collaboration Grant 276282.

Keywords: mass problems, Muchnik degrees, degrees of unsolvability, Turing oracles, Turing degrees, Turing jump, hyperarithmetical theory.

Abstract

Recall that E_{w} is the lattice of Muchnik degrees of nonempty effectively compact sets in Euclidean space. We solve a long-standing open problem by proving that E_{w} is dense, i.e., satisfies ∀x ∀y (x < y ⇒ ∃z (x < z < y)). Our proof combines an oracle construction with hyperarithmetical theory.

1 Introduction

The study of degrees of unsolvability began in the mid-20th century. Given a set A of natural numbers, there is an associated decision problem, the problem of “deciding” for each natural number n whether n ∈ A or not. As a method of measuring the algorithmic unsolvability of decision problems, Kleene and Post [10] introduced the semilattice D_{T} consisting of the Turing degrees of arbitrary sets A, while Post [15] emphasized the countable subsemilattice E_{T} consisting of the recursively enumerable Turing degrees, i.e., Turing degrees of sets A which are recursively enumerable. The semilattices D_{T} and E_{T} are defined in terms of Turing oracles, a notion which had been introduced earlier by Turing [30, §4]. Two important landmarks in the study of E_{T} were Sacks’s discovery of the splitting theorem [17]:

Every nonzero recursively enumerable Turing degree is the supremum of two smaller recursively enumerable Turing degrees.

and the density theorem [18]:

For any two comparable recursively enumerable Turing degrees, there is another recursively enumerable Turing degree between them.

Inspired by these results of Sacks, the study of structural properties of E_{T} has played a leading role in recursion theory from the 1960s to the present. See for instance the recent paper [1] and the survey papers [12, 22].

Also in the mid-20th century but largely ignored in the West, Medvedev [13] and Muchnik [14] introduced more general notions of degrees of unsolvability. Given a set P in Euclidean space or some similar space such as the Cantor space {0, 1}^{ℕ} or the Baire space ℕ^{ℕ}, there is an associated mass problem^{1}, the problem of “finding” or “computing” some element of P. Thus P plays the role of the “solution set” of the mass problem. As a method of measuring the algorithmic unsolvability of mass problems, Medvedev [13] and Muchnik [14] introduced the lattices D_{s} and D_{w} of strong degrees and weak degrees, also known as Medvedev degrees and Muchnik degrees respectively. The idea here is that a mass problem P is reducible to a mass problem Q if, given any solution of Q, we can use it as a Turing oracle to compute some solution of P. By requiring the computation to be uniform, we get strong reducibility, a.k.a., Medvedev reducibility. By allowing the computation to be nonuniform, we get weak reducibility, a.k.a., Muchnik reducibility. See also the formal definition of P ≤_{w} Q in §2 below.

2010 Mathematics Subject Classification: Primary 03D30; Secondary 03D28, 03D55.

At the end of the 20th century, and in ignorance of D_{w} but motivated by a desire to highlight certain aspects of E_{T}, Simpson [23, 24] introduced the countable sublattice E_{w} of D_{w} consisting of the Muchnik degrees of nonempty sets which are effectively compact, i.e., Π_{1}^{0} and recursively bounded. The study of E_{w} continued in a number of 21st century publications including the survey papers [27, 28].

As noted in [23, 24] and further emphasized in [25, 26, 28], there is a compelling analogy between E_{T} and E_{w}:

1. With respect to the arithmetical hierarchy [16, Chapters 14 and 15], E_{w} is the smallest nontrivial sublattice of D_{w}, just as E_{T} is the smallest nontrivial subsemilattice of D_{T}.

2. By [26] we have a natural embedding of E_{T} into E_{w}, given by a ↦ inf(a, 1) where 1 is the top degree in E_{w}. This embedding is one-to-one and preserves the algebraic structure of E_{T} including the top and bottom degrees, the reducibility ordering, and the semilattice operation.

3. The splitting and density theorems hold for E_{w}, just as they do for E_{T}. The splitting theorem for E_{w} is due to Binns [4]. The density theorem for E_{w} is the main theorem of this paper.

On the other hand, E_{w} seems to have a significant advantage over E_{T}:

1.

1The term “mass problem” is a literal translation of the Russian term in [13] and was used by Rogers in his seminal textbook [16].

4. A great many specific natural degrees have been discovered in E_{w}. See for instance [28, Figure 1]. By contrast, no specific natural degrees in E_{T} are known except the top degree 0′ and the bottom degree 0. The problem of finding other specific natural degrees in E_{T} remains open, despite more than 50 years of intensive research on structural aspects of E_{T}.

We feel that these considerations help to motivate and justify the study of E_{w}.

As already mentioned, the main result of this paper is the density theorem for E_{w}. This answers a question which was implicit in [3, 4, 5] and explicit in [21, last paragraph] and [26, Remark 2.11] and [27, Remark 3.1.3].

The paper is organized as follows. In §2 we set up some notation. In §3 we present our density proof. We end with some open questions.

2 Essential notation and definitions

In this section we develop notation and definitions which are needed for precise understanding of the statements of our results in §3.

The set of nonnegative integers is denoted ℕ. Variables such as i, j, m, n, s, t range over ℕ. The set of all functions X : ℕ → ℕ is denoted ℕ^{ℕ}. Variables such as X, Y, Z, … range over ℕ^{ℕ}. We write {n}^{Y} (i) = j to mean that the Turing machine with Gödel number n using Y as a Turing oracle started with input i eventually halts with output j. We write {n}^{Y} (i) ↓ if ∃j ({n}^{Y} (i) = j), otherwise {n}^{Y} (i) ↑. We say that X is Turing reducible to Y, abbreviated X ≤_{T} Y, if ∃n ∀i (X(i) = {n}^{Y} (i)). It is known that ≤_{T} is reflexive and transitive. We say that X is Turing equivalent to Y, abbreviated X ≡_{T} Y, if X ≤_{T} Y and Y ≤_{T} X. The Turing jump of X ∈ ℕ^{ℕ} is X′ ∈ ℕ^{ℕ} defined by letting X′(n) = 1 if {n}^{X}(n) ↓, otherwise X′(n) = 0.

For P, Q ⊆ ℕ^{ℕ} we say that P is Muchnik reducible to Q, abbreviated P ≤_{w} Q, if ∀Y (Y ∈ Q ⇒ ∃X (X ∈ P and X ≤_{T} Y)). Clearly ≤_{w} is reflexive and transitive. We say that P is Muchnik equivalent to Q, abbreviated P ≡_{w} Q, if P ≤_{w} Q and Q ≤_{w} P. The Muchnik degree of P, denoted deg_{w}(P), is the equivalence class of P under ≡_{w}. We define deg_{w}(P) ≤ deg_{w}(Q) to mean that P ≤_{w} Q. Let D_{w} be the set of all Muchnik degrees, partially ordered by ≤. It is known that D_{w} is a complete and completely distributive lattice. A set Q ⊆ ℕ^{ℕ} is said to be Π_{1}^{0} or effectively closed if Q = {Y | {n}^{Y} (n) ↑} for some n. For X, Y ∈ ℕ^{ℕ} we define X ⊕ Y ∈ ℕ^{ℕ} by the equations (X ⊕Y)(2i) = X(i), (X ⊕Y)(2i+1) = Y (i) for all i. A binary predicate U ⊆ ℕ × ℕ^{ℕ} is said to be Π_{1}^{0} if the set {X ⊕ Y | U(X, Y)} is Π_{1}^{0}.

As in the survey paper [27], let E_{w} (respectively S_{w}) be the lattice of Muchnik degrees of nonempty Π_{1}^{0} subsets of {0, 1}^{ℕ} (respectively ℕ^{ℕ}).^{2} It is easy to see that E_{w} and S_{w} are countable sublattices of D_{w}. It is also known that E_{w} is an initial segment of S_{w}. For a proof of this important fact, see [26, Lemma 3.3] or [27, Theorem 3.3.1, Corollary 3.3.4].

3 Density proof

In this section we prove that S_{w} and consequently E_{w} are dense, i.e., they satisfy the sentence ∀x ∀y (x < y ⇒ ∃z (x < z < y)). Our proof combines a Turing jump oracle construction with some well known facts about relative hyperarithmeticity. Our oracle construction may be compared to the previously known constructions for [7, Lemma 5.1] and [29, Lemma 3.2].

Remark 1. The relevance of hyperarithmetical theory for the general study of E_{w} was already clear in [7]. However, our work in this paper represents the first time that hyperathmetical theory has been used to prove a latticetheoretic property of E_{w}. We do not know how to prove the density of E_{w} without using hyperarithmetical theory.

As a warm-up for our oracle construction in Lemma 2, we first prove the following lemma, which is a generalization of the Friedberg Jump Theorem [16, §13.3, Corollary IX(a)].

Lemma 1. Let Q ⊆ ℕ^{ℕ} be Π_{1}^{0} such that Q ≰_{w} {0}. Given Z ∈ ℕ^{ℕ}, we can find Z̃ ∈ ℕ^{ℕ} such that 0′ ⊕ Z ≡_{T} 0′ ⊕ Z̃ ≡_{T} Z̃′ and Q ≰_{w} {Z̃}.

Proof. Before presenting our construction, we fix some additional notation.

2Let d be a positive integer, and let ℝ^{d} denote d-dimensional Euclidean space. A set in ℝ^{d} is said to be effectively closed if it is the complement of a set which is effectively open, i.e., of the form ⋃_{i=0}^{∞} B(a_{i}, r_{i}) where ⟨a_{i}⟩_{i∈ℕ} is a recursive sequence of d-tuples of rational numbers, ⟨r_{i}⟩_{i∈ℕ} is a recursive sequence of rational numbers, and B(a_{i}, r_{i}) = {x ∈ ℝ^{d} | |x − a_{i}| < r_{i}}. A set in ℝ^{d} is effectively compact if and only if is bounded and effectively closed. It is well known and easy to see that a Muchnik degree belongs to E_{w} if and only if it contains a nonempty effectively compact set in ℝ^{d}.

A string is a finite sequence of nonnegative integers. Variables such as ρ, σ, τ, … range over strings. We write σ = ⟨σ(0), …, σ(|σ|−1)⟩ where |σ| = the length of σ. We write

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

for the concatenation, σ followed by τ. Thus |σ^{⌢}τ| = |σ| + |τ|. We write σ ⊂ τ or σ ⊂ Z to mean that σ is a proper initial segment of τ or of Z respectively. We write σ ⊆ τ to mean that σ ⊂ τ or σ = τ. We write Z↾n = the unique string σ of length n such that σ ⊂ Z. A tree is a set U of strings such that ∀σ ∀τ (σ ⊂ τ ∈ U ⇒ σ ∈ U). A path through U is any Y ∈ ℕ^{ℕ} such that ∀n (Y ↾n ∈ U). It is well known that Q ⊆ ℕ^{ℕ} is Π_{1}^{0} if and only if Q = {Y | Y is a path through U} for some recursive tree U.

We write {n}_{s}^{Z}(i) = j to mean that the Turing machine with Gödel number n using Z as a Turing oracle started with input i halts after ≤ s steps with output j. We write {n}_{s}^{σ}(i) = j to mean that {n}_{s}^{Z}(i) = j using only oracle information from σ ⊂ Z. We write {n}_{s}^{σ}(i) ↓ if ∃j ({n}_{s}^{σ}(i) = j), otherwise {n}_{s}^{σ}(i) ↑. We write Φ_{n}(σ) = τ to mean that ∀i (i < |τ| ⇒ {n}_{|σ|}^{σ}(i) = τ(i)) and {n}_{|σ|}^{σ}(|τ|) ↑. Note that the predicates {n}_{s}^{σ}(i) = j and {n}_{s}^{σ}(i) ↓ and Φ_{n}(σ) = τ are recursive.

We now present our construction. As above, let U be a recursive tree such that ∀Y (Y ∈ Q ⇔ Y is a path through U). We follow the standard proof of the Friedberg Jump Theorem, taking additional steps to avoid computing a path through U. Given Z ∈ ℕ^{ℕ} we define a sequence of strings τ_{0} ⊆ τ_{1} ⊆ ⋯ ⊆ τ_{s} ⊆ τ_{s+1} ⊆ ⋯ as follows.

Stage 0. Let τ_{0} = ⟨⟩ and n_{0} = 0 and i_{0} = 1.

Stage s + 1. Let n = n_{s} and proceed as follows depending on whether i_{s} is equal to 1, 2, or 3.

Case 1: i_{s} = 1. Let τ_{s+1} = τ_{s}^{⌢}⟨Z(n)⟩ and let n_{s+1} = n_{s} and i_{s+1} = 2. Case 2: i_{s} = 2. If there exists τ ⊇ τ_{s} such that {n}_{|τ|}^{τ}(n) ↓, let τ_{s+1} = the

least such τ, otherwise τ_{s+1} = τ_{s}. Either way, let n_{s+1} = n_{s} and i_{s+1} = 3.

Case 3: i_{s} = 3. If there exists τ ⊃ τ_{s} such that Φ_{n}(τ_{s}) ⊂ Φ_{n}(τ) ∈ U, let τ_{s+1} = the least such τ, and let n_{s+1} = n_{s} and i_{s+1} = 3. Otherwise, let τ_{s+1} = τ_{s} and let n_{s+1} = n_{s} + 1 and i_{s+1} = 1.

This completes the construction. Clearly we have ∀s (τ_{s} ⊂ τ_{s+3}), so letting Z̃ = ⋃_{s} τ_{s} we have Z̃ ∈ ℕ^{ℕ}. Moreover, the entire construction is uniformly ≤_{T} 0′ ⊕ Z and ≤_{T} 0′ ⊕ Z̃, so in particular we have Z̃ ≤_{T} 0′ ⊕ Z.

We claim that there are infinitely many stages s such that i_{s} = 1. Otherwise, there would be a stage s such that n_{t} = n_{s} and i_{t} = 3 for all t ≥ s. And then, letting n = n_{s}, the construction for Case 3 would produce a recursive path ⋃_{t} Φ_{n}(τ_{t}) through U, contradicting our assumption that Q ≰_{w} {0}.

From our claim it follows that for each n there is exactly one stage s such that n_{s} = n and i_{s} = 1. For this s we have Z(n) = τ_{s+1}(|τ_{s}|) = Z̃(|τ_{s}|) by Case 1, and this shows that Z ≤_{T} 0′ ⊕ Z̃. Moreover, for this same s we have n_{s+1} = n and i_{s+1} = 2, so by Case 2 we have Z̃′(n) = 1 if and only if there exists τ ⊇ τ_{s+2} such that {n}_{|τ|}^{τ}(n) ↓, and this shows that Z̃′ ≤_{T} 0′ ⊕ Z. Furthermore, for this same s we have n_{s+2} = n and i_{s+2} = 3, so by our claim there is exactly one stage t ≥ s + 2 such that n_{t} = n and i_{t} = 3 and i_{t+1} = 1. But then by Case 3 there is no τ ⊃ τ_{t} such that Φ_{n}(τ_{t}) ⊂ Φ_{n}(τ) ∈ U, and this shows that Q ≰_{w} {Z̃}. The proof is now complete.

Remark 2. In the proof of Lemma 1, the 0′-recursive functional Z ↦ Z̃ maps any Π_{1}^{0} set S ⊆ ℕ^{ℕ} homeomorphically onto its image S̃ = {Z̃ | Z ∈ S}. This is clear from the construction, because for all stages s such that i_{s} = 1, τ_{s} depends only on Z↾n_{s} and conversely Z↾n_{s} can be recovered from τ_{s}.

Our oracle construction is embodied in the following lemma. We formulate this lemma in greater generality than is needed for the density proof.

Lemma 2. Given Π_{1}^{0} predicates U, V ⊆ ℕ^{ℕ}× ℕ^{ℕ}, we can find a Π_{1}^{0} predicate V̂ ⊆ ℕ^{ℕ} × ℕ^{ℕ} such that for each X with {Y | U(X, Y)} ≰_{w} {X} there is a homeomorphism Z ↦ Ẑ of {Z | V (X, Z)} onto {Ẑ | V̂(X, Ẑ)} with the properties X′ ⊕ Z ≡_{T} X′ ⊕ Ẑ ≡_{T} (X ⊕ Ẑ)′ and {Y | U(X, Y)} ≰_{w} {X ⊕ Ẑ}.

Proof. In order to present our construction, we need some additional notation. We write {n}_{s}^{X,σ}(i) = j to mean that {n}_{s}^{X⊕Z}(i) = j using only oracle information from X and from σ ⊂ Z. We write {n}_{s}^{X,σ}(i) ↓ if ∃j ({n}_{s}^{X,σ}(i) = j), otherwise {n}_{s}^{X,σ}(i) ↑. We write Φ_{n}^{X}(σ) = τ to mean that ∀i (i < |τ| ⇒ {n}_{|σ|}^{X,σ}(i) = τ(i)) and {n}_{|σ|}^{X,σ}(|τ|) ↑. Note that the predicates {n}_{s}^{X,σ}(i) = j and {n}_{s}^{X,σ}(i) ↓ and Φ_{n}^{X}(σ) = τ are uniformly ≤_{T} X.

We now present our construction, which is similar in many respects to the construction for Lemma 1. For each X ∈ ℕ^{ℕ} let U^{X} be a uniformly X-recursive tree such that ∀X ∀Y (U(X, Y) ⇔ Y is a path through U^{X}). To each X ∈ ℕ^{ℕ} and each string σ we associate an infinite sequence of strings τ_{0} ⊆ τ_{1} ⊆ ⋯ ⊆ τ_{s} ⊆ τ_{s+1} ⊆ ⋯ as follows.

Stage 0. Let τ_{0} = ⟨⟩ and i_{0} = 1 and n_{0} = 0.

Stage s + 1. Let n = n_{s}. If n ≥ |σ| the construction halts and we let τ_{t} = τ_{s} and i_{t} = 0 and n_{t} = n_{s} for all t ≥ s + 1. Otherwise we proceed as follows depending on whether i_{s} is equal to 1, 2, or 3.

Case 1: i_{s} = 1. Let τ_{s+1} = τ_{s}^{⌢}⟨σ(n)⟩ and let i_{s+1} = 2 and n_{s+1} = n_{s}.

Case 2: i_{s} = 2. If there exists τ ⊇ τ_{s} such that {n}_{|τ|}^{X,τ}(n) ↓, let τ_{s+1} = the least such τ, otherwise τ_{s+1} = τ_{s}. Either way, let i_{s+1} = 3 and n_{s+1} = n_{s}.

Case 3: i_{s} = 3. If there exists τ ⊃ τ_{s} such that Φ_{n}^{X}(τ_{s}) ⊂ Φ_{n}^{X}(τ) ∈ U^{X}, let τ_{s+1} = the least such τ, and let i_{s+1} = 3 and n_{s+1} = n_{s}. Otherwise, let τ_{s+1} = τ_{s} and let i_{s+1} = 1 and n_{s+1} = n_{s} + 1.

This completes the construction. Note that the construction does not depend on V. Let us write F_{s}^{X}(σ) = τ_{s} and note that the function F_{s}^{X} is uniformly ≤_{T} X′ and monotone, i.e., s ≤ t and ρ ⊆ σ imply F_{s}^{X}(ρ) ⊆ F_{t}^{X}(σ).

For each X ∈ ℕ^{ℕ} let V^{X} be a uniformly X-recursive tree such that ∀X ∀Z (V (X, Z) ⇔ Z is a path through V^{X}). Consider the tree

Ṽ^{X} = {τ | ∃s ∃σ (σ ∈ V^{X} and τ ⊆ F_{s}^{X}(σ))}.

For each τ ∈ Ṽ^{X}, our construction shows that τ ⊆ F_{s}^{X}(σ) for some s ≤ 3|τ| and some σ ∈ V^{X} such that σ is a substring of τ, i.e., σ = ⟨τ(j_{1}), …, τ(j_{|σ|})⟩ for some j_{1} < ⋯ < j_{|σ|} < |τ|. Thus, in the definition of Ṽ^{X}, the unbounded quantifiers ∃s and ∃σ may be replaced by bounded quantifiers. It follows that the tree Ṽ^{X} is uniformly ≤_{T} X′. Hence, by Post’s Theorem, the predicate Ṽ ⊆ ℕ^{ℕ} × ℕ^{ℕ} defined by

Ṽ(X, Z̃) ≡ Z̃ is a path through Ṽ^{X}

is Π_{2}^{0}, say Ṽ(X, Z̃) ≡ ∀i ∃j B(X, Z̃, i, j) where B is a recursive predicate. We now define our Π_{1}^{0} predicate V̂ ⊆ ℕ^{ℕ} × ℕ^{ℕ} by

V̂(X, Z̃ ⊕ Z̃^{∗}) ≡ ∀i (Z̃^{∗}(i) = the least j such that B(X, Z̃, i, j) holds).

To prove that V̂ has the desired properties, let X be such that {Y | U(X, Y)} ≰_{w} {X}, i.e., X does not compute a path through U^{X}. In such a situation, our construction of ⋃_{n} F_{s}^{X}(Z↾n) for s = 0, 1, 2, … is the straightforward relativization to X of the construction of τ_{s} for s = 0, 1, 2, … in the proof of Lemma 1. Thus, letting Z̃ = F^{X}(Z) = ⋃_{s} ⋃_{n} F_{s}^{X}(Z↾n), we have X′ ⊕ Z ≡_{T} X′ ⊕ Z̃ ≡_{T} (X ⊕ Z̃)′ and {Y | U(X, Y)} ≰_{w} {X ⊕ Z̃}. Moreover, as in Remark 2, Z ↦ Z̃ is an X′-recursive homeomorphism of {Z | V (X, Z)} onto {Z̃ | Ṽ(X, Z̃)}. Now, following the definition of V̂, for each such Z let Z̃^{∗}(i) = the least j such that B(X, Z̃, i, j) holds. Then Z̃^{∗} ≤_{T} X ⊕ Z̃, hence Ẑ = Z̃ ⊕ Z̃^{∗} enjoys the same properties as Z̃, i.e., X′ ⊕ Z ≡_{T} X′ ⊕ Ẑ ≡_{T} (X ⊕ Ẑ)′ and {Y | U(X, Y)} ≰_{w} {X ⊕ Ẑ} and Z ↦ Ẑ is an X′-recursive homeomorphism of {Z | V (X, Z)} onto {Ẑ | V̂(X, Ẑ)}. This completes the proof.

Lemma 3. Suppose Kleene’s O is not hyperarithmetical in X. Then, there is a nonempty Π_{1}^{0} set S ⊆ ℕ^{ℕ} such that S ≰_{w} {X′}.

Proof. The predicate n ∉ O is Σ_{1}^{1}, so by the Kleene Normal Form Theorem (see [16, §16.1, Corollary III] or [19, Theorem I.1.3]), let S(n, Z) be a Π_{1}^{0} predicate such that ∀n (n ∉ O ⇔ ∃Z S(n, Z)). For some n ∉ O we must have {Z | S(n, Z)} ≰_{w} {X′}, because otherwise O would be arithmetical in X, hence hyperarithmetical in X. Fix such an n and let S = {Z | S(n, Z)}.

Remark 3. In Lemma 3 the property S ≰_{w} {X′} can be strengthened to say that no Z ∈ S is hyperarithmetical in X.

The next theorem implies that S_{w} is dense. The special case Q = ∅ says that S_{w} has no top degree.

Theorem 1. Let P and Q be Π_{1}^{0} subsets of ℕ^{ℕ} such that P <_{w} Q. Then, we can find a Π_{1}^{0} set R ⊆ ℕ^{ℕ} such that P <_{w} R <_{w} Q.

Proof. The set {X | X ∈ P and Q ≰_{w} {X}} is arithmetical, hence Σ_{1}^{1}, so by the Gandy Basis Theorem (see [16, §16.7, Corollary XLII(a)] or [19, Theorem III.7.2]), let X_{0} ∈ P be such that Q ≰_{w} {X_{0}} and Kleene’s O is not hyperarithmetical in X_{0}. By Lemma 3 let S ⊆ ℕ^{ℕ} be nonempty Π_{1}^{0} such that S ≰_{w} {X′_{0}}. Apply Lemma 2 with U(X, Y) ≡ Y ∈ Q and V (X, Z) ≡ Z ∈ S to get a Π_{1}^{0} predicate V̂(X, Ẑ). Let

R = {X ⊕ Ẑ | X ∈ P and V̂(X, Ẑ)} ∪ Q.

Trivially R is Π_{1}^{0} and P ≤_{w} R ≤_{w} Q. Since X_{0} ∈ P and Q ≰_{w} {X_{0}}, we have Q ≰_{w} {X_{0} ⊕ Ẑ} and X_{0} ⊕ Ẑ ∈ R for all Z ∈ S, so Q ≰_{w} R. It remains to prove that R ≰_{w} P. Since X_{0} ∈ P, it suffices to prove that R ≰_{w} {X_{0}}. If R ≤_{w} {X_{0}}, then since Q ≰_{w} {X_{0}} there must exist X ⊕ Ẑ ≤_{T} X_{0} such that X ∈ P and V̂(X, Ẑ) holds. But then Q ≰_{w} {X}, hence X′ ⊕Z ≡_{T} X′ ⊕Ẑ for some Z ∈ S, hence Z ≤_{T} X′_{0}, a contradiction. This completes the proof.

The next theorem says that E_{w} is dense.

Theorem 2. Let P and Q be nonempty Π_{1}^{0} subsets of {0, 1}^{ℕ} such that P <_{w} Q. Then, we can find a nonempty Π_{1}^{0} set R ⊆ {0, 1}^{ℕ} such that P <_{w} R <_{w} Q.

Proof. This follows from Theorem 1 plus the fact, noted in §2, that E_{w} is an initial segment of S_{w}.

We close with some additional remarks.

Remark 4. By relativization, Theorems 1 and 2 also hold with Π_{1}^{0} replaced by boldface Π_{1}^{0}, i.e., closed. The lattices of Muchnik degrees of closed subsets of {0, 1}^{ℕ} and ℕ^{ℕ} have been studied by Shafer [20].

Remark 5. Shafer [21] suggested that if the density of E_{w} could be proved, then this might perhaps lead to further progress on the problem of calculating the Turing degree^{3} of the first-order theory of E_{w}. Unfortunately, no such further progress has materialized. For further progress, more sophisticated extension-of-embedding results for E_{w} seem to be needed.

Remark 6. We do not know whether E_{w} and/or S_{w} have the dense splitting property, i.e., ∀x ∀y (x < y ⇒ ∃u ∃v (x < u < y, x < v < y, sup(u, v) = y)). Lachlan [11] proved that E_{T} does not have the dense splitting property. Binns [4] proved that E_{w} has the splitting property, i.e., the special case x = 0. We do not know whether S_{w} has the splitting property.

References

[1] George Barmpalias, Mingzhong Cai, Steffen Lempp, and Theodore A. Slaman. On the existence of a strong minimal pair. Journal of Mathematical Logic, 15(1):1550003 (28 pages), 2015. DOI: 10.1142/S0219061315500038. 2

[2] A. Beckmann, V. Mitrana, and M. Soskova, editors. Evolving Computability, Proceedings of CiE 2015 (Bucharest). Number 9136 in Lecture Notes in Computer Science. Springer, 2015. XV + 363 pages. 13 [3] Stephen Binns. The Medvedev and Muchnik Lattices of Π_{1}^{0} Classes.

3A precise value for this Turing degree has been conjectured [7, page 127].

PhD thesis, Pennsylvania State University, June 2003. VII + 80 pages, http://etda.libraries.psu.edu/paper/6092/. 4

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

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

[6] 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

[7] Joshua A. Cole and Stephen G. Simpson. Mass problems and hyperarithmeticity. Journal of Mathematical Logic, 7(2):125–143, 2008. 5, 10

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

[9] Edward R. Griffor, editor. Handbook of Computability Theory. Number 140 in Studies in Logic and Foundations of Mathematics. North-Holland, 1999. XII + 727 pages. 12

[10] Stephen C. Kleene and Emil L. Post. The upper semi-lattice of degrees of recursive unsolvability. Annals of Mathematics, 59(3):379–407, 1954. 2

[11] Alistair H. Lachlan. A recursively enumerable degree which will not split over all lesser ones. Annals of Mathematical Logic, 9(4):307–365, 1976. 10

[12] Steffen Lempp, Manuel Lerman, and Reed Solomon. Embedding finite lattices into the computably enumerable degrees – a status survey. In [6], pages 206–229, 2006. 2

[13] Yuri T. Medvedev. Degrees of difficulty of mass problems. Doklady Akademii Nauk SSSR, n.s., 104(4):501–504, 1955. In Russian. 2, 3 [14] Albert A. Muchnik. On strong and weak reducibilities of algorithmic

problems. Sibirskii Matematicheskii Zhurnal, 4(6):1328–1341, 1963. In Russian. 2, 3

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

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

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

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

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

[20] Paul Shafer. Coding true arithmetic in the Medvedev and Muchnik degrees. Journal of Symbolic Logic, 76(1):267–288, 2011. 10

[21] Paul Shafer. Coding true arithmetic in the Medvedev degrees of Π_{1}^{0} classes. Annals of Pure and Applied Logic, 163(3):321–337, 2012. 4, 10

[22] Richard A. Shore. The recursively enumerable degrees. In [9], pages 170–197, 1999. 2

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

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

[25] Stephen G. Simpson. FOM: natural r.e. degrees. FOM e-mail list [8], 27 February 2005. 3

[26] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, 75(2):287–297, 2007. 3, 4, 5 [27] Stephen G. Simpson. Mass problems associated with effectively closed

sets. Tohoku Mathematical Journal, 63(4):489–517, 2011. 3, 4, 5

[28] Stephen G. Simpson. Degrees of unsolvability: a tutorial. In [2], pages 83–94, 2015. 3, 4

[29] Stephen G. Simpson. Implicit definability in arithmetic. Notre Dame Journal of Formal Logic, 2016 (estimated). 14 pages, accepted for publication 3 March 2014. 5

[30] A. M. Turing. Systems of logic based on ordinals. Proceedings of the London Mathematical Society, 45:161–228, 1939. 2