Topological aspects of the Medvedev lattice

Andrew E. M. Lewis^{†}, Richard A. Shore^{∗} and Andrea Sorbi^{‡}

Abstract

We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space.

1 Introduction

The Medvedev lattice 𝔐 was introduced by Medvedev, [7], in order to provide a computational semantics for constructive propositional logic: see for instance [7], [15], [18], [20]. On the other hand, Medvedev reducibility, whose degree structure gives rise to the Medvedev lattice, provides a novel computability-theoretic reducibility paradigm which is interesting in its own right. For instance, it is not difficult to see that classical degree structures such as the Turing degrees and the enumeration degrees can be embedded into the Medvedev lattice. But, perhaps more interestingly, Medvedev reducibility is a reducibility on sets of reals, not just reals, so its domain of discourse is a very interesting mathematical structure, namely the Baire space (or the Cantor space, if we confine ourselves to 0-1-valued functions). As such, Medvedev reducibility and the Medvedev lattice make it possible, from a computability-theoretic point of view, to discuss and study properties of topological objects such as closed, dense and discrete sets of reals. In this paper we investigate the sublattices generated by the closed, dense and discrete Medvedev degrees; we study the prime ideal generated by the dense degrees and its complement, a prime filter; we also study the filter generated by the nonzero closed degrees, and the filter generated by the nonzero discrete degrees. We describe the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice of the closed Medvedev degrees is not a Brouwer algebra. Among other things, we also investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold both of the Medvedev lattice on the Baire space and of the Medvedev lattice on the Cantor space.

†Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, U.K.; Email:

andy@aemlewis.co.uk. The author was supported by a Royal Society Research Fellowship.

∗Department of Mathematics, Cornell University, Ithaca, NY 14853, USA; E-mail:

shore@math.cornell.edu. Part of this work was carried out while the author was a GNSAGA Visiting Professor at the Department of Mathematics and Computer Science “Roberto Magari” of the University of Siena. He was also partially supported by NSF Grant DMS-0852811 and Grant 13408 from the John Templeton Foundation.

‡Department of Mathematics and Computer Science “R. Magari”, University of Siena, 53100 Siena, Italy; E-mail: sorbi@unisi.it.

In the rest of this section, we briefly introduce notions, terminology and background material that are relevant to this paper. For other unexplained notions and terminology, the reader is referred to any standard textbook, such as [3], [6], [10], or [16]. Let ω^{ω} denote the collection of all functions from the set ω of natural numbers into itself. If A is any set, by A^{∗} we denote the set of all finite sequences, or strings, of elements of A. We use standard notations and terminology for strings. In particular, λ denotes the empty string; if σ, τ ∈ A^{∗} and f is a function f : ω ⟶ A then: σˆ τ denotes the concatenation of σ and τ; |σ| denotes the length of σ; σˆ f denotes the function

σˆ f(x) = \{ \begin{matrix}σ(x), & if x < |σ|, \\ f(x − |σ|), & otherwise; \end{matrix}

we use σ ⊆ τ to denote that σ is an initial segment of τ, and σ ⊂ f to denote that the string σ is an initial segment of the function f; we write σ|τ to mean that σ and τ are ⊆-incomparable. We let ⟨a_{0} ⋯ a_{n−1}⟩ denote the string of length n formed by the elements a_{0}, ⋯, a_{n−1} of A.

For every string σ ∈ ω^{∗}, let

[[σ]] = {f ∈ ω^{ω} : σ ⊂ f} .

The Baire topology on ω^{ω} is the topology generated by the basic open neighborhoods {[[σ]] : σ ∈ ω^{∗}}. With this topology, ω^{ω} is called the Baire space. In view of this topology, finite strings will be sometimes also called basic neighborhoods, or intervals. Notice that each [[σ]] is also closed. The Baire space is a complete metric space. Restriction to the set 2^{ω} of 0-1-valued functions gives the Cantor space, which up to homeomorphisms can be characterized as the unique space that is compact, Hausdorff, without isolated points, and with a countable base (provided by {[[σ]] : σ ∈ 2^{∗}}, where 2 = {0, 1}) of clopen (i.e. closed and open) sets. For properties of the Baire space and the Cantor space see for instance [5].

Let ϕ_{n}^{f} be the partial function computed with oracle f by the oracle Turing machine with index n (see [16] for an introduction to oracle Turing machines). In the following, by a Turing functional on the Baire space we mean a partial mapping Ψ : ω^{ω} ⟶ ω^{ω} for which there exists some n such that domain(Ψ) = {f : ϕ_{n}^{f} total}, and for every f ∈ domain(Ψ) and x ∈ ω, Ψ(f)(x) = ϕ_{n}^{f}(x). This also gives us an effective listing {Ψ_{n}}_{n∈ω} of the Turing functionals. If Ψ = Ψ_{n} is a Turing functional and σ is a string, then Ψ(σ) denotes the partial function Ψ(σ)(x) = ϕ_{n}^{σ}(x): for details see [16, Definition 1.7]. When necessary we can also regard Ψ as a mapping from strings to strings by identifying Ψ(σ) with the longest string ρ ⊆ Ψ(σ). Turing functionals on the Cantor space, and related definitions, are defined similarly.

A mass problem is any subset A ⊆ ω^{ω}. On mass problems one can define ([7]; see also [10], section XIII.7) the following reducibility relation ≤,

A ≤ B ⇔ (∃n)[Ψ_{n}(B) ⊆ A],

i.e. A ≤ B if there is a uniform Turing reduction procedure by means of which any function in B computes some function of A. Let ≡ denote the equivalence relation generated by ≤. The ≡-equivalence class of a mass problem A, denoted by deg_{M}(A), is called the Medvedev degree (or simply, the M-degree) of A, or the degree of difficulty of A. We use boldface capital letters A, B, … to denote Medvedev degrees.

The collection of Medvedev degrees is not only a partial order, but in fact:

Theorem 1.1 ([7]) The Medvedev degrees form a distributive lattice with 0, 1, denoted by 𝔐.

Proof. We sketch the proof for later reference. We define the following operations ∨ and ∧ on mass problems A, B:

1. A ∨ B = {f ⊕ g : f ∈ A and g ∈ B}, where, given partial functions ϕ and ψ,

we let

ϕ ⊕ ψ(x) = \{ \begin{matrix}ϕ(y), & if x = 2y, \\ ψ(y), & if x = 2y + 1; \end{matrix}

2. A ∧ B = ⟨0⟩ˆ A ∪ ⟨1⟩ˆ B, where for a given string σ and a given mass problem

A,

σˆ A = {σˆ f : f ∈ A} .

It is now easy to see (for an easy reference, see for instance [10, Section XIII.7]) that these operations on mass problems can be used to define the operations of supremum ∨, and infimum ∧, on Medvedev degrees as

deg_{M}(A) ∨ deg_{M}(B) = deg_{M}(A ∨ B),
deg_{M}(A) ∧ deg_{M}(B) = deg_{M}(A ∧ B).

These operations distribute over each other: for instance, one can easily check that, for all mass problems A, B, C,

A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C).

Finally, the least degree 0 is defined as 0 = deg_{M}(A), where A contains some computable function; and the greatest degree 1 is defined as 1 = deg_{M}(∅). □

It is known that 𝔐 has cardinality 2^{2^{ℵ_{0}}} ([9]), although each Medvedev degree has big cardinality, as shown by the following:

Lemma 1.2 Every M-degree contains 2^{2^{ℵ_{0}}} different mass problems.

Proof. Let A be any mass problem. For every mass problem B we have by absorption that A ≡ (A ∨ B) ∧ A; since different B’s produce different mass problems of the form (A ∨ B) ∧ A, the claim is proved. □

We recall that a Brouwer algebra is a distributive lattice 𝔏 with 0, 1, equipped with a binary operation →, satisfying for all a, b ∈ 𝔏,

a → b = min {c : b ≤ a ∨ c} .

Lemma 1.3 ([7]) 𝔐 is a Brouwer algebra.

Proof. We give the proof for later reference. If A, B are mass problems, then define a new mass problem

A → B = {⟨z⟩ˆ g : (∀f ∈ A)[Ψ_{z}(f ⊕ g) ∈ B]} .

It is easy to see that B ≤ (A → B) ∨ A, and B ≤ C ∨ A if and only if (A → B) ≤ C. Thus we can extend to degrees by defining

deg_{M}(A) → deg_{M}(B) = deg_{M}(A → B),

thus showing that 𝔐 is a Brouwer algebra. □

Definition 1.4 An M-degree in 𝔐 is called closed (respectively: dense, discrete) if it contains a mass problem that is closed (respectively: dense, discrete) in the Baire space.

The following two lemmas record known facts. (By a sublattice, we mean also that the least element and the greatest element are preserved.)

Lemma 1.5 ([2]) The closed Medvedev degrees form a sublattice, 𝔐_{Cl}.

Dyment, [4], shows that there is no greatest dense Medvedev degree. However:

Lemma 1.6 ([4]) The dense Medvedev degrees, with the addition of 1, form a sublattice, 𝔐_{De}. The discrete Medvedev degrees form a sublattice, 𝔐_{Di}.

If we restrict our attention to mass problems that are subsets of the Cantor space, and use for reduction on these mass problems Turing functionals on the Cantor space, we get in a similar way a Brouwer algebra, denoted by 𝔐^{0,1}, called the Medvedev lattice on the Cantor space.

The Medvedev degree in 𝔐^{01} of a mass problem A ⊆ 2^{ω} will be denoted by deg_{M^{01}}(A). Similarly to the Medvedev lattice on the Baire space, an M-degree in 𝔐^{01} is called closed (respectively: dense, discrete) if it contains a mass problem that is closed (respectively: dense, discrete) in the Cantor space. Thus, in analogy with the Baire space, one can consider the sublattices formed by the closed (dense, discrete) degrees, denoted by 𝔐_{Cl}^{0,1} (𝔐_{De}^{0,1}, 𝔐_{Di}^{0,1}): in order to get lattices with a greatest element, for 𝔐_{De}^{0,1}, 𝔐_{Di}^{0,1}, in analogy with the Baire space case, one has to add the top element 1.

For every f ∈ ω^{ω} define (viewing a function as an infinite sequence)

f^{01} = ⟨1^{f(0)}01^{f(1)}01^{f(2)} ⋯ ⟩

where 1^{x} denotes \underbrace{1 ⋯ 1}_{x times}. Notice that the assignment f ↦ f^{01} is a Turing functional

and provides a homeomorphism between ω^{ω} and the subset G of the Cantor space,

G = {g ∈ 2^{ω} : (∃^{∞}x)[g(x) = 0]} .

Given A ⊆ ω^{ω}, define the mass problem A^{01} ⊆ 2^{ω}, as A^{01} = {f^{01} : f ∈ A}; and given B ⊆ G, define B^{ω} = {f ∈ ω^{ω} : f^{01} ∈ B}.

Theorem 1.7 The embedding ι : 𝔐^{01} ⟶ 𝔐 given by ι(deg_{M^{01}}(B)) = deg_{M}(B) is an isomorphism. The isomorphism maps closed degrees to closed degrees; the isomorphism, and its inverse, map dense (discrete) degrees to dense (discrete) degrees. In particular 𝔐_{De}^{0,1} ≃ 𝔐_{De} and 𝔐_{Di}^{0,1} ≃ 𝔐_{Di}, where ≃ denotes lattice-theoretic isomorphism.

Proof. Notice that if A ⊆ ω^{ω} then A ≡ A^{01}, and A is dense (discrete) if and only if so is A^{01}. Moreover, if B ⊆ G, then B ≡ B^{ω} and B is dense (discrete) if and only if so is B^{ω}. Notice also that every closed B in the Cantor space is also closed in the Baire space. The rest of the proof is a routine check. □

It is worth noticing that if A is closed in the Baire space, then A^{01} need not be closed in the Cantor space: for instance, choose a noncomputable f and take

A = {⟨n⟩ˆ f : n ∈ ω} .

Then the constant function g(x) = 1 is in the closure of A^{01} (since for every n, ⟨1^{n}⟩ˆ ⟨0⟩ˆ f^{01} ∈ A^{01}), but not in A^{01}.

Remark 1.8 In the rest of the paper we do not specify whether we work in the Baire space or in the Cantor space, in those cases in which proofs for both 𝔐 and 𝔐^{01} are, mutatis mutandis, virtually the same, or the Cantor case immediately transfers to the Baire space and vice versa, by the isomorphism provided by Theorem 1.7. Of course, mass problems have to be meant as mass problems in the Baire space or in the Cantor space, and Turing functionals must be regarded as Turing functionals on the Baire space or the Cantor space, according to the case. When distinctions between the Cantor space and the Baire space are necessary (for instance when dealing with closed degrees, or with perfect trees) we will treat each case separately.

Finally we observe that the Turing degrees and the enumeration degrees can be viewed as substructures of the Medvedev lattice. Since f ≤_{T} g if and only if {f} ≤ {g}, it is immediate to observe ([7]) that the Turing degrees embed into the Medvedev lattice, via an embedding preserving least element 0 and join operation ∨. Medvedev degrees of singletons are usually called degrees of solvability.

If A is a set then let

E_{A} = {f : range(f) = A} ,

and let E_{A} = deg_{M}(E_{A}). If A ≠ ∅, then E_{A} is called the problem of enumerability of A, and E_{A} is called the degree of enumerability of A. As already observed by Medvedev, [7], if B ≠ ∅ then A ≤_{e} B if and only if E_{A} ≤ E_{B}, thus the degrees of enumerability are isomorphic with the enumeration degrees (preserving 0 and ∨).

2 The closed Medvedev degrees

Since 𝔐_{Cl} is a sublattice of 𝔐, it is natural to ask if it is also a Brouwer subalgebra, or at least a Brouwer algebra.

Theorem 2.1 𝔐_{Cl} is not a Brouwer algebra.

Proof. In fact, if f, g are functions such that {g} ≰ {f} and f is the characteristic function of a 1-generic set, then for every closed mass problem C such that {g} ≤ {f} ∨ C, we can construct a function h such that C ≰ {h} and {g} ≤ {f} ∨ {h}. To show this, let f, g be as above: without loss of generality, we may assume that also g is a characteristic function, so we start in fact with sets A, B such that A is 1-generic, and B ≰_{T} A. Let C be a closed mass problem such that for every k ∈ C, k ≰_{T} A. We want to build a suitable h as the characteristic function of a set D. In the rest of the proof we often identify A, B, and the set D to be constructed, with their respective characteristic functions f, g, h. We recall that a set X is 1-generic if for every c.e. set W of strings in 2^{∗}, there is a σ ⊂ X such that either σ ∈ W, or for every τ ⊇ σ, τ ∉ W.

We aim at constructing D so that k ≰_{T} D for all k ∈ C, and

B ≤_{T} A ⊕ D.

We construct D by a finite extension argument. In order that A⊕D should compute B we use the following coding: the nth bit of B will be A(m) where m is the nth bit on which A and D differ. At stage s we define a finite initial segment τ_{s} of D.

Stage 0. Let τ_{0} = λ. Stage s + 1. Suppose we have defined τ_{s}. We want to ensure that Ψ_{s}(D) is

partial or lies outside C. Suppose τ_{s} is of length n and let E be A with the first n bits replaced by τ_{s}, i.e.

E(i) = \{ \begin{matrix}τ_{s}(i), & if i < n; \\ A(i), & if i ≥ n. \end{matrix}

We distinguish the following two cases:

1. Ψ_{s}(E) is partial. Then there must be some finite initial segment of E which is sufficient to force partiality. In order to see this suppose otherwise, and let m be the least number such that Ψ_{s}(E)(m) ↑. Then the c.e. set of strings

V = {σ : Ψ_{s}(σ)(m) ↓}

can be transformed into a c.e. set V′ to give a witness that A is not 1-generic – just let Ψ_{s} be replaced by any Turing functional Φ such that for every function k, Φ((A ↾ n)ˆ k) = Ψ_{s}(τ_{s}ˆ k), where A ↾ n is the initial segment of A of length n. In this case, then, we can take an initial segment of E sufficient to force partiality. This still codes B correctly, because this initial segment agrees with A on its new bits. Then extend it to a suitable τ_{s+1} so as to code the next bit of B, B(s).

2. Ψ_{s}(E) is total. In this case Ψ_{s}(E) ∉ C because Ψ_{s}(E) ≤_{T} A and nothing in C is computable in A. Because C is closed we can take τ such that τ_{s} ⊆ τ ⊂ E, and nothing extending Ψ_{s}(τ) is in C. Finally, choose τ_{s+1} to be some finite extension of τ which codes the next bit B(s) of B.

□

Corollary 2.2 𝔐_{Cl}^{0,1} is not a Brouwer algebra.

Proof. The above proof works for 𝔐^{0,1} as well, as h is built as a function that lies in the Cantor space. □

Remark 2.3 Recall that Muchnik reducibility ≤_{w} on mass problems (see [8]) is the nonuniform version of Medvedev reducibility: A ≤_{w} B if

(∀f ∈ B)(∃g ∈ A)[g ≤_{T} f].

The equivalence classes of mass problems under the equivalence relation ≡_{w} generated by ≤_{w} are called Muchnik degrees. It is well known, see [8], that Muchnik reducibility gives rise to a Brouwer algebra on Muchnik degrees, called the Muchnik lattice. The proof of Theorem 2.1 shows that the result stated therein holds of Muchnik reducibility too: if f, g are as in the proof of the theorem then there is no closed mass problem C such that {g} ≤_{w} C ∨ {f} and C ≤_{w} D for all closed D such that {g} ≤_{w} D ∨ {f}. Thus the lattice of closed Muchnik degrees is not a Brouwer algebra: see also Simpson’s result, [14], stating that the lattice of Muchnik degrees of (lightface) Π_{1}^{0} classes does not form a Brouwer algebra.

3 The dense Medvedev degrees

We now turn our attention to the dense Medvedev degrees, i.e. the Medvedev degrees containing some dense mass problem. It might be worth noticing that the property of M-degrees of not being dense does not coincide at all with the property of being nowhere dense. Indeed, every M-degree is nowhere dense, in the sense that it contains some nowhere dense mass problem: to see this, for every mass problem A we have that A ≡ A ∨ {f} when f is computable, and A ∨ {f} is nowhere dense.

Given a poset 𝔓 = ⟨P, ≤⟩, we recall that a subset B ⊆ P is an automorphism base for 𝔓, if every automorphism F of 𝔓 which is the identity on B, is also the identity on P. We begin our investigation on the dense degrees with the following result.

Theorem 3.1 The dense Medvedev degrees form an automorphism base of 𝔐.

Proof. Suppose that A and B are mass problems and A ≰ B. We show that there exists a dense D such that D ≤ A, but D ≰ B. (This is enough to show that the dense degrees form an automorphism base of the Medvedev lattice. Indeed, suppose that F is an automorphism which is the identity on the dense degrees, and F (A) = B where A ≰ B: if D is dense, D ≤ A, and D ≰ B, then D = F (D) ≤ F (A) = B, a contradiction.) So, let A ∈ A, B ∈ B, and construct a dense D as follows. For every Turing functional Ψ, since A ≰ B, choose a function f = f_{Ψ} ∈ B such that Ψ(f) ↑ or Ψ(f) ∉ A, and let

D = {g : (∀Ψ)[g ≠ Ψ(f_{Ψ})]} .

Then D ≰ B; moreover D ≤ A since A ⊆ D; finally D is dense since its complement is countable. □

Next, we introduce a class of dense degrees that are particularly useful in examples and applications:

Definition 3.2 For every f, let

B_{f} = {g : g ≰_{T} f} ,

and let B_{f} = deg_{M}(B_{f}).

Mass problems of the form B_{f}, for some f, and their respective M-degrees have been extensively used in the literature concerning the Medvedev lattice, see e.g. [18]. For instance, it is known, see [18, Lemma 2.2] that each B_{f} is join-irreducible and meet-irreducible: in fact, join-irreducibility follows from the fact that for every noncomputable f,

B_{f} ∧ deg_{M}({f}) = max {A : A < B_{f}} .

Moreover:

Theorem 3.3 For every non-computable f, the non-zero M-degrees of the form B_{f} are exactly the M-degrees X satisfying 𝔐 ⊧ ϕ(X), where ϕ(v) is the first order formula in the language of posets,

ϕ(v) := (∃u < v)(∀w < v)(w ≤ u).

As a consequence the M-degrees of the form B_{f}, for some function f, are first-order definable in 𝔐.

They are also characterized by:

B_{f} = min {A : A ≰ deg_{M}({f})} .

Since the M-degrees of the form deg_{M}({f}) (called the degrees of solvability) are first-order definable ([4]), this provides another first-order definition of the B_{f}’s.

Proof. By the remark preceding the Theorem, it suffices show that if B is an Mdegree satisfying ϕ(v), then B = B_{f}, for some f. Let A be the greatest M-degree strictly below B. By Dyment’s characterization of empty intervals in [4], there exists an f such that A = B ∧ deg_{M}({f}), and B ≰ deg_{M}({f}). Let B ∈ B. It follows that B ≰ {f} hence B ⊆ B_{f}, hence B_{f} ≤ B. On the other hand B_{f} ≰ B ∧ {f}. Hence B ≡ B_{f}. □

Question 3.4 Is 𝔐_{De} a Brouwer subalgebra of 𝔐, or at least a Brouwer algebra?

4 Ideals and filters

We recall some basic notions and definitions of lattice theory. For more details see for instance [1].

Definition 4.1 In a lattice 𝔏 = ⟨L, ∨, ∧, ≤⟩ a nonempty subset I ⊆ L is said to be an ideal if for all x, y ∈ L,

y ∈ I and x ≤ y ⇒ x ∈ I,
x, y ∈ I ⇒ x ∨ y ∈ I.

Let I be an ideal of 𝔏. I is proper if I ≠ L. A proper ideal is prime if for all x, y ∈ L,

x ∧ y ∈ I ⇒ x ∈ I or y ∈ I.

If 𝔏 is a lattice then the ideal I generated by a nonempty subset X ⊆ L (i.e. the smallest ideal under inclusion, containing X) is given by

I = {a : (∃F ⊆ X)[F finite, F ≠ ∅ and a ≤ ⋁ F]} .

The dual notion of an ideal is that of a filter. It is well known (see e.g. [1]) that I is a prime ideal if and only if the complement I^{c} is a prime filter.

Definition 4.2 ([4]) Let ℑ be the ideal generated by the dense degrees.

The following is trivial by Lemma 1.6:

ℑ = {A : (∃D ∈ 𝔐_{De} − {1}) [A ≤ D]} .

It is shown in [17] that ℑ is not principal. We will show in Theorem 5.5 that the dense degrees themselves do not form an ideal. Moreover:

Corollary 4.3 ([17]) ℑ is prime.

Proof. We give the proof for later reference. Suppose that A ∧ B ≤ D where D is dense, and let Ψ be a Turing functional providing the reduction. Suppose that there exists an initial segment α such that Ψ(α)(0) = 0. Then consider

D^{−} = {f : αˆ f ∈ D} .

Clearly D^{−} is dense, and the Turing functional Φ(f) = Ψ(αˆ f) reduces D^{−} to A, showing that deg_{M}(A) ∈ ℑ. A similar argument shows that deg_{M}(B) ∈ ℑ if we assume that there exists an initial segment α such that Ψ(α)(0) = 1. Since one of these cases must hold, we have proved that either deg_{M}(A) ∈ ℑ or deg_{M}(B) ∈ ℑ. □

Hence:

Corollary 4.4 ([2]) The complement of ℑ is a prime filter, denoted by 𝔉.

It is shown in [2] that 𝔉 is not principal.

Definition 4.5 ([2]) Let 𝔉_{Cl} be the filter generated by the nonzero closed Medvedev degrees.

The following is trivial by Lemma 1.5

𝔉_{Cl} = {A : (∃C ∈ 𝔐_{Cl} − {0}) [A ≥ C]} .

It is shown in [17] that 𝔉_{Cl} is not principal.^{3} We will see in Theorem 6.5 that the nonzero closed degrees themselves do not form a filter.

Lemma 4.6 If A and B are mass problems such that B is closed, and B ≰ A then, for every C,

B ≤ A ∨ C ⇒ C nowhere dense.

Proof. Let B ≰ A, with B closed. The claim follows from the proof of Theorem 2.8 in [19], which shows that if B is closed and D is dense then D → B ≡ B. Therefore it suffices to observe that if B ≤ A∨C and C is dense in some interval then there exists a dense D such that B ≤ A ∨ D (if C is dense in, say, [[α]], then D = {f : αˆ f ∈ C} is dense and C ≤ D), hence B ≡ D → B ≤ A, giving B ≤ A, a contradiction.

For the ease of the reader we include, however, a direct proof of the claim. Suppose that B ≤ A ∨ C via a Turing functional Ψ, where B is closed and C is dense in the basic neighborhood [[α]]. Consider the following Turing functional Φ: On input f, compute Φ(f)(x) by recursion as follows: suppose that Φ(f)(x − 1) ↓ (if x > 0) and we have already computed relatively to f a finite string α_{x−1} ⊇ α (with α_{−1} = α). Then look for the first pair β, α_{x} of finite strings (of the same length) such that β ⊂ f, α_{x−1} ⊆ α_{x} and Ψ(β ⊕ α_{x})(x) ↓. Define Φ(f)(x) = Ψ(β ⊕ α_{x})(x); otherwise Φ(f)(x) is undefined. Let now f ∈ A. Notice that by density of C in [[α]], for every x there is a function g ∈ C extending α_{x−1} such that Ψ(f ⊕ g)(x) ↓. Thus for every x we can find β, α_{x} as above, hence Φ(f) is total. On the other hand suppose that for every x we pick g_{x} ⊃ α_{x} with g_{x} ∈ C, and let h_{x} = Ψ(f ⊕ g_{x}): then h_{x} ∈ B, lim_{x} h_{x} = Φ(f), and thus Φ(f) ∈ B since B is closed. This shows that B ≤ A, a contradiction. □

Corollary 4.7 ([2]) 𝔉_{Cl} ⊆ 𝔉.

3Recently Paul Shafer has proved (personal communication) that 𝔉_{Cl} is not prime.

Proof. The inclusion 𝔉_{Cl} ⊆ 𝔉 follows by the previous lemma since we cannot have C ≤ D if D is dense and C ≠ 0 is closed. □

That strict inclusion holds in Corollary 4.7 has been shown in [2]. The proof given there uses another interesting filter of the Medvedev lattice, namely the filter generated by the nonzero discrete M-degrees. This filter will be denoted in this paper by 𝔉_{Di}. By Lemma 1.6, we have

𝔉_{Di} = {A : (∃C ∈ 𝔐_{Di} − {0}) [A ≥ C]} .

Dyment shows that if A does not contain computable functions and is discrete, then, for every B,

A ≤ B ⇒ B nowhere dense.

Hence, 𝔉_{Di} ⊆ 𝔉.

On the other hand, [2] shows

Theorem 4.8 ([2]) 𝔉_{Di} ⊈ 𝔉_{Cl}. Hence 𝔉 ⊈ 𝔉_{Cl}.

It is shown in [17] that 𝔉_{Di} is not prime and the corresponding quotient lattice has cardinality 2^{2^{ℵ_{0}}}. Dyment, [4], shows that 𝔉_{Di} is not principal. We will show in Theorem 8.6 that the nonzero discrete degrees do not form a filter.

Remark 4.9 The ideals and filters introduced in this section have, of course, corresponding versions in 𝔐^{01}. By virtually the same proofs, all the results and properties shown in this section remain unaltered if one replaces 𝔐 with 𝔐^{01}.

5 The ideal ℑ generated by the dense degrees

We define a perfect tree in the Baire space to be a function T : 2^{∗} ⟶ ω^{∗} such that for every σ, τ ∈ 2^{∗},

1. σ ⊆ τ ⇒ T (σ) ⊆ T (τ);

2. T (σˆ ⟨0⟩)|T (σˆ ⟨1⟩).

A perfect tree is computable if it is computable as a function. If T is a perfect tree, then we denote by [T] the set of infinite paths through T. The set [T] is a perfect (i.e. closed and without isolated points) subset of the Baire space. We also say that a string τ is on T, if τ ⊂ f for some f ∈ [T].

By abusing notation, we can also regard a tree T in the Baire space as a total mapping T : 2^{ω} ⟶ ω^{ω}, by letting

T (f) = ⋃_{σ⊂f} T (σ).

Then T is a homeomorphism of 2^{ω} onto [T]. Moreover if T is computable then the associated homeomorphism of 2^{ω} with [T], and its inverse T^{−1}, are Turing functionals. Notice that here T (f) ≡_{T} f.

Definition 5.1 A mass problem A is dense in a perfect tree T if it is dense in [T], i.e. [T] is contained in \overline{A}, the closure of A in the Baire space.

Notice that in the above definition we do not require that A ⊆ [T]. If T is computable, this additional property implies that the M-degree of A is dense: see Theorem 5.4.

If we require that the tree be a function T : 2^{∗} ⟶ 2^{∗}, then we get the definition of a perfect tree in the Cantor space. For perfect trees in the Cantor space, one can make observations similar to those made for trees in the Baire space. In particular, the set [T] of infinite paths is a perfect subset of 2^{ω}.

The following lemma relates trees in the Cantor space to trees in the Baire space. Given a string σ ∈ ω^{∗}, we define σ^{01} ∈ 2^{∗}: if σ = ⟨x_{0} ⋯ x_{n−1}⟩ then σ^{01} = ⟨1^{x_{0}}01^{x_{1}}0 ⋯ 1^{x_{n−1}}0⟩. Moreover, if σ ∈ 2^{∗} is a string whose final bit is 0, σ = ⟨1^{x_{0}}01^{x_{1}}0 ⋯ 1^{x_{n−1}}0⟩, then we define σ^{ω} ∈ ω^{∗}, σ^{ω} = ⟨x_{0} ⋯ x_{n−1}⟩. Finally, if T is a perfect tree in the Baire space, then define T^{01} : 2^{∗} ⟶ 2^{∗}, by T^{01}(σ) = (T (σ))^{01}, and if T is a perfect tree in the Cantor space such that for every nonempty σ, T (σ) ends with the bit 0, then define T^{ω} : 2^{∗} ⟶ ω^{∗}, by T^{ω}(σ) = (T (σ))^{ω}.

Lemma 5.2 Under the assumptions specified above, T^{01} is a perfect tree in the Cantor space, and T^{ω} is a perfect tree in the Baire space.

Proof. Obvious. □

The given proof of the following theorem works, modulo obvious modifications, both for 𝔐 and 𝔐^{01}. In addition to the usual caveats, one here has also to distinguish between trees in the Cantor space, or trees in the Baire space, depending on whether one is looking for a proof suitable to 𝔐^{01} or to 𝔐.

Theorem 5.3 For every mass problem A of non-zero M-degree, if deg_{M}(A) ∈ ℑ then A is dense in some computable perfect tree.

Proof. Suppose that A ≤ D via the Turing functional Φ, and D is dense; we are given that A does not contain computable functions. Define a computable perfect tree T as follows:

1. T (λ) = λ;

2. Suppose we have defined T (σ); find the least quintuple τ_{0}, τ_{1}, ρ_{0}, ρ_{1}, s where T (σ) ⊆ τ_{i}, ρ_{i} ⊆ Φ(τ_{i})[s], and ρ_{0}|ρ_{1}. (Here the appendix [s] denotes that we perform at most s − 1 steps in the computations). Then define T (σˆ ⟨i⟩) = τ_{i}.

Such a triple τ_{0}, τ_{1}, s exists, since otherwise, by density of D and by the fact that D ⊆ domain(Φ), we would have that for every f ⊃ T (σ) and f ∈ D,

Φ(f) = ⋃_{T (σ)⊆τ} Φ(τ) :

a contradiction since Φ would map all functions in D ∩ [[T (σ)]] to computable functions.

Moreover, we can think of Φ∘T as a computable perfect tree too, by letting Φ ∘ T (λ) = λ, and Φ ∘ T (σˆ ⟨i⟩) = ρ_{i}, where ρ_{i} and s are as in the definition of T (σˆ ⟨i⟩) above. We now conclude the proof of our claim, by showing that A is dense in Φ∘T. Let g ∈ [Φ ∘ T], and assume that τ ⊂ g. Let σ be the least string such that τ ⊆ Φ ∘ T (σ). By density, let h ∈ D, h ⊃ T (σ). Then Φ(h) ⊃ τ, and Φ(h) ∈ A. □

Note that the tree T built in the above proof is a Φ-splitting tree, i.e. for every σ there exists some x such that Φ(T (σˆ ⟨0⟩))(x) ↓≠ Φ(T (σˆ ⟨1⟩))(x) ↓. We also recall that a pair (σ_{0}, σ_{1}) of strings such that Φ(σ_{0})(x) ↓≠ Φ(σ_{1})(x) ↓ is called a Φ-splitting on x. (In the context of the Cantor space, see for instance [6] for details on Φ-splitting trees, and Φ-splittings.)

Theorem 5.4 If T is a computable perfect tree, A ⊆ [T] and A is dense in T then deg_{M}(A) is dense.

Proof. Suppose that A is dense in some computable perfect tree T, with A ⊆ [T]. Then A ≤ T^{−1}(A) (viewing T and T^{−1} as Turing functionals), and T^{−1}(A) is dense: if σ is any interval, then A ∩ [[T (σ)]] ≠ ∅, hence T^{−1}(A) ∩ [[σ]] ≠ ∅. □

Theorem 8.5 will show that there are M-degrees containing mass problems not in ℑ that are dense in some computable perfect tree.

One should not believe that all degrees in ℑ are dense. In fact:

Theorem 5.5 There exists an A ∈ ℑ such that A is not dense. So the dense degrees are not an ideal.

Proof. (First proof.) The result easily follows from Corollary 4.3 and Lemma 4.6. Indeed consider any mass problem A with deg_{M}(A) ∈ ℑ and any mass problem C such that deg_{M}(C) ∈ 𝔉 such that A ≰ C, hence A ≰ A ∧ C: for instance take A = B_{f} = {g : g / ≤_{T}f}, assume that f is not computable, and take C = {f}. Then deg_{M}(A ∧ C) ∈ ℑ, as A ∧ C ≤ A, but there is no dense D such that A ∧ C ≡ D, since for such a D we would have A ≰ D, hence C ≤ D^{−}, for some dense D^{−}, by the proof of Corollary 4.3, giving deg_{M}(C) ∈ ℑ.

(Second Proof.) For a different, but perhaps more interesting and useful proof, we present a direct construction of mass problems A and B such that B is dense, A ≤ B, but A ≢ D, for any dense D. In fact we construct A to be dense in the interval ⟨0⟩, but not equivalent to any dense mass problem, so that the mass problems A and B = {f : ⟨0⟩ˆ f ∈ A} satisfy the claim. Notice that we do not specify below whether we work in the Baire space or in the Cantor space, as the proofs for both cases are virtually identical.

The construction of A is by steps. At step n we define a finite mass problem A_{n}, and a sequence g_{0}, g_{1}, …, g_{h_{n}} of prohibited functions which are banned from the final A, together with a sequence σ_{0}, σ_{1}, …, σ_{k_{n}} of prohibited neighborhoods (all extending ⟨1⟩), for which we want to guarantee that A ∩ [[σ_{i}]] = ∅ for the final A. We guarantee that A_{n} ⊆ A_{n+1}, and that h_{n}, k_{n} are increasing in n. At the end of the construction we take A = ⋃_{n} A_{n}. We also guarantee that at the end of each step s, there are still available neighborhoods, i.e. neighborhoods σ extending ⟨1⟩ that are not comparable with prohibited ones, and such that A_{s} ∩ [[σ]] = ∅. At each step, each parameter keeps the same value as at the preceding step if not explicitly modified. Also let {σ_{i}^{0}}_{i∈ω} be a listing of the neighborhoods extending ⟨0⟩. Finally, we fix some listing {(Ψ_{n}, Φ_{n})}_{n∈ω} of all pairs of Turing functionals.

Step 0: Let A_{0} = ∅, and h_{0} = k_{0} = −1.

Step n + 1: Let (Ψ, Φ) = (Ψ_{n}, Φ_{n}). The idea is to diagonalize against possible reductions Φ(A) ⊆ D and Ψ(D) ⊆ A, with D dense. Pick an available neighborhood ρ ⊇ ⟨1⟩, and let σ = ρˆ ⟨0⟩: the choice of σ is motivated by the fact that if we prohibit σ, then ρˆ ⟨1⟩ will still be available.

We distinguish the following cases:

1. (∃^{∞}f)[f not computable, Ψ(Φ(f)) ∉ A_{n}, and Ψ(Φ(f)) ≠ f]. In this case pick such an f ≠ g_{0}, g_{1}, …, g_{h_{n}}: let f ∈ A_{n+1}, prohibit Ψ(Φ(f)), by letting h_{n+1} = h_{n} + 1 and g_{h_{n+1}} = Ψ(Φ(f)). Then the pair (Ψ, Φ) cannot be used in any equivalence D ≡ A.

2. (∃τ ⊇ σ)(∀f ⊃ τ)[f noncomputable ⇒ Ψ(Φ(f)) ↑]. In this case choose such a τ and pick a noncomputable f ⊇ τ, f ≠ g_{0}, g_{1}, …, g_{h_{n}}, and let f ∈ A_{n+1}. Then the pair (Ψ, Φ) cannot be used in any equivalence D ≡ A.

3. If neither of these first two cases hold and there exists a string τ ⊇ σ with no Ψ∘Φ-splittings above it, then we can choose τ̂ ⊇ τ such that {g_{0}, g_{1}, …, g_{h_{n}}}∩ [[τ̂]] = ∅, pick a noncomputable f ⊃ τ̂ such that Ψ(Φ(f)) ↓, and let f ∈ A_{n+1}. Then the pair (Ψ, Φ) cannot be used in any equivalence D ≡ A, since by construction eventually A will not contain any computable function, whereas by the absence of splittings, on the neighborhood [[τ̂]], Ψ ∘ Φ when defined outputs computable functions, and thus Ψ(Φ(f)) is computable.

4. Otherwise, prohibit σ, by defining k_{n+1} = k_{n}+1 and σ_{k_{n+1}} = σ. In this case, we use the density of D to show that (Ψ, Φ) cannot witness an equivalence D ≡ A:

We can build a computable perfect tree T, with T (λ) = σ, which is Ψ ∘ Φsplitting. For almost all noncomputable f ∈ [T] we have that either Ψ(Φ(f)) ∈ A_{n} or Ψ(Φ(f)) = f. Thus by cardinality, in [T] there are noncomputable functions f such that Ψ(Φ(f)) = f. Pick such an f, and let τ ⊂ f be such that Ψ(Φ(τ)) ⊇ σ (without loss of generality we may assume that Φ(τ) is in fact a string). By the density of D there exists a g ∈ D such that g ⊃ Φ(τ), but then Ψ(g) ⊇ σ, thus Ψ(g) ∉ A, since σ is prohibited.

At the end of Step n + 1, take a noncomputable function f ⊃ σ_{n}^{0} which has not been prohibited so far, and let f ∈ A_{n+1}.

The observations made throughout the construction should make it clear that the mass problems A and B = {f : ⟨0⟩ˆ f ∈ A} have the required properties. □

Remark 5.6 The first proof of the previous theorem shows in fact that if A ∈ ℑ, C ∈ 𝔉, and A ≰ C then

(∀D)[D dense and A ∧ C < D ⇒ A ≤ D];

in particular, if A is dense then,

A = min {D : D dense and A ∧ C < D} .

Remark 5.7 How does one transfer proofs from the Cantor space to the Baire space, and conversely? Often, proving either case is enough to get the remaining case as an immediate consequence of the isomorphism given in Theorem 1.7. As observed in Remark 1.8 a somewhat careful analysis should be made when closed mass problems and perfect trees are concerned. For instance one can argue that proving Theorem 5.3 for the Baire space immediately yields the result for the Cantor space since T^{01} is a computable perfect tree in the Cantor space if T is a computable perfect tree in the Baire space. To get the result for the Baire space as a consequence of the result for the Cantor space, one has to slightly modify the proof for the Cantor space, and build a computable perfect tree T such that for every nonempty σ, T (σ) ends with the bit 0. But this can be easily done, by defining T (λ) = λ, and in the inductive step, T (σˆ ⟨i⟩) = T (σ)ˆ τ_{i}ˆ ⟨0⟩, where τ_{i} is as in the proof of Theorem 5.3. This guarantees that T^{ω} is a computable perfect tree in the Baire space. The argument then goes like this: if A ≤ D and D is dense in the Baire space, then A^{01} ≤ D^{01} and D^{01} is dense in the Cantor space. Therefore there exists a tree T in the Cantor space such that for every nonempty string σ, T (σ) ends with the bit 0, and A^{01} is dense in T; it is then easy to conclude that A is dense in T^{ω}.

Definition 5.8 A mass problem X is said to be ≡_{T}-closed if

f ∈ X and f ≡_{T} g ⇒ g ∈ X .

Examples of ≡_{T}-closed mass problems are mass problems that are upwards ≤_{T} - closed (whose M-degrees are called Muchnik degrees), and the Turing degrees (regarded as mass problems).

Theorem 5.9 If A and B are mass problems that are ≡_{T}-closed and A is of nonzero M-degree, then

A ≤ B ⇔ B ⊆ A.

Proof. Suppose first that we work in the Cantor space, and A, B ⊆ 2^{ω} are mass problems that are ≡_{T}-closed, A does not contain computable functions, and A ≤ B, via the Turing functional Φ. Let T be a computable perfect tree associated with B (which is dense) and Φ as in the proof of Theorem 5.3. Let f ∈ B: then T (f) ≡_{T} f, i.e. T (f) ∈ B, and since T is Φ-splitting, we have that Φ(T (f)) ≡_{T} T (f) (see for instance [6]), and thus f ∈ A since Φ(T (f)) ∈ A and A is ≡_{T}-closed.

Next, we give the proof for the Medvedev lattice on the Baire space. Suppose that A, B are as above, but A, B ⊆ ω^{ω}. Thus A^{01} ≤ B^{01}, hence B^{01} ⊆ A^{01} by the Cantor space case. If now f ∈ B then f^{01} ∈ B^{01}, hence f^{01} ∈ A^{01} ⊆ A, but f ≡_{T} f^{01}, then by T-closure, f ∈ A. This shows that B ⊆ A. □

Remark 5.10 Notice that in the Cantor space, since T (f) ≡_{tt} f and Φ(T (f)) ≡_{tt} T (f) in the above proof, this shows that the claim is true also for mass problems that are ≡_{tt}-closed, i.e. if A, B ⊆ 2^{ω} are ≡_{tt}-closed, then

A ≤ B ⇔ B ⊆ A.

Let 𝔐_{T} be the sublattice of 𝔐 generated by the M-degrees containing Turing degrees (regarded as mass problems).

Theorem 5.11 For every n ≤ 2^{ℵ_{0}} the free distributive lattice with 0, 1 on n generators is embeddable in 𝔐_{T}.

Proof. It is enough to consider the case n = 2^{ℵ_{0}}. Let 𝔏 = ⟨L, ∨, ∧, 0, 1 ≤⟩ be the free distributive lattice with 0, 1 on the generators {a_{i}}_{i∈2^{ℵ_{0}}}. Choose a set of functions {t_{i}}_{i∈2^{ℵ_{0}}} whose T-degrees are independent, i.e. for every i ∈ 2^{ℵ_{0}} and finite F ⊆ 2^{ℵ_{0}}, t_{i} ≤_{T} ⋁_{j∈F} t_{j} implies i ∈ F: see [13] for the existence of such an independent set of T-degrees. For every i ∈ 2^{ℵ_{0}} let T_{i} = {g : g ≡_{T} t_{i}}, and T_{i} = deg_{M}(T_{i}). We claim that the embedding a_{i} ↦ T_{i} extends to a lattice theoretic embedding. The crucial point is to show that

⋀_{i∈I^{0}}( ⋁_{j∈J_{i}^{0}} a_{i,j}) ≤ ⋀_{i∈I^{1}}( ⋁_{j∈J_{i}^{1}} a_{i,j}) ⇔ ⋀_{i∈I^{0}}( ⋁_{j∈J_{i}^{0}} T_{i,j}) ≤ ⋀_{i∈I^{1}}( ⋁_{j∈J_{i}^{1}} T_{i,j})

where I^{0}, I^{1}, {J_{i}^{0}}_{i∈I^{0}} , {J_{i}^{1}}_{i∈I^{1}} are finite subsets of 2^{ℵ_{0}} whose elements are in this particular case identified with numbers, the a_{i,j}’s are generators, and the mass problems T_{i,j} lie in {T_{i}}_{i∈2^{ℵ_{0}}}. If I is a finite set, whose elements are identified with numbers, then we can identify a mass problem of the form ⋀_{i∈I} C_{i} (with the obvious meaning by associativity) with ⋃_{i∈I}⟨i⟩ˆ C_{i}.

The nontrivial part is to show ⇐. So assume that

⋀_{i∈I^{0}}( ⋁_{j∈J_{i}^{0}} T_{i,j}) ≤ ⋀_{i∈I^{1}}( ⋁_{j∈J_{i}^{1}} T_{i,j}).

First we want to show that

(∀i ∈ I^{1})(∃r ∈ I^{0})[J_{r}^{0} ⊆ J_{i}^{1}].

Assume i ∈ I^{1}, then there is a Turing functional Ψ which reduces ⋁_{j∈J_{i}^{1}} T_{i,j} to ⋀_{i∈I^{0}}(⋁_{j∈J_{i}^{0}} T_{i,j}). Let r ∈ I^{0} be such that there is some function f ∈ ⋁_{j∈J_{i}^{1}} T_{i,j} with Ψ(f) ∈ ⟨r⟩ˆ (⋁_{j∈J_{r}^{0}} T_{r,j}). As Ψ(f) ≡_{T} ⨁_{j∈J_{r}^{0}} t_{r,j}, it follows that ⨁_{j∈J_{r}^{0}} t_{r,j} ≤_{T} ⨁_{j∈J_{i}^{1}} t_{i,j}. Thus, by independence, J_{r}^{0} ⊆ J_{j}^{1}. But then ⋁_{j∈J_{r}^{0}} a_{r,j} ≤ ⋁_{j∈J_{i}^{1}} a_{i,j}. Since i is arbitrary, this shows that ⋀_{i∈I^{0}}(⋁_{j∈J_{i}^{0}} a_{i,j}) ≤ ⋀_{i∈I^{1}}(⋁_{j∈J_{i}^{1}} a_{i,j}), as desired. □

6 The filter 𝔉

An obvious consequence of Theorem 5.3 is:

Theorem 6.1 If A is non-zero and contains some mass problem that is not dense in any computable perfect tree then A ∈ 𝔉.

Also, by Lemma 4.6,

Corollary 6.2 For every mass problem A, if deg_{M}(A) ∈ 𝔉_{Cl} then A is nowhere dense.

The following result uses the condition on the elements of 𝔉 given in Theorem 6.1 to construct a degree that is in 𝔉 but not in 𝔉_{Cl}. For a different construction see [2, Corollary 3.7].

Theorem 6.3 There exists a countable mass problem A, of non-zero degree, such that A is not dense in any computable perfect tree, and A ≱ C for any closed C unless C contains computable functions.

Proof. Let {T_{e}}_{e∈ω} be a listing of all computable perfect trees. We build a mass problem A of noncomputable functions, satisfying, for all e, the requirements:

P_{e} : Ψ_{e}(A) closed ⇒ Ψ_{e}(A) contains a computable function
N_{e} : A not dense in [T_{e}].

At stage s > 0 we define an approximation A_{s} to A, such that the closure \overline{A_{s}} is countable; moreover we define a neighborhood τ to be available if τ is not comparable with any neighborhood that has been declared prohibited so far, and [[τ]]∩A_{s−1} = ∅. At the end of each stage we guarantee that there remain available neighborhoods.

Stage s = 0: do nothing.

Stage 2e + 1: Take the least available σ. If there exists a string τ ⊇ σ such that for some noncomputable f ⊃ τ, Ψ_{e}(f) ↑, then let f ∈ A_{2e+1} for some such f ⊃ τ.

Otherwise, define by recursion three sequences τ_{n}, σ_{n} (of strings) and f_{n} of functions as follows:

1. let τ_{0} be the first string τ ⊇ σ for which Ψ_{e}(τ)(0) ↓, let σ_{0} = τ_{0}ˆ ⟨1⟩ and choose a noncomputable function f_{0} ⊃ τ_{0}ˆ ⟨0⟩;

2. let τ_{n+1} be the first string τ ⊇ σ_{n} for which Ψ_{e}(τ)(n) ↓, let σ_{n+1} = τ_{n+1}ˆ ⟨1⟩ and choose a noncomputable function f_{n+1} ⊃ τ_{n+1}ˆ ⟨0⟩;

Let f_{n} ∈ A_{2e+1} for all n. Notice that A_{2e+1} has countable closure if A_{2e} has. Stage 2e+2: Assume that we have already defined A_{2e+1}, with countable closure.

Pick a neighborhood τ such that τ is on T_{e} and [[τ]]∩A_{2e+1} = ∅: such a neighborhood exists since by cardinality we cannot have [T_{e}] ⊆ \overline{A_{2e}}. Suppose that σ is the least string such that τ ⊆ T_{e}(σ). Define T_{e}(σˆ ⟨0⟩) to be prohibited. Notice that at next stage there will be available neighborhoods, e.g. those extending T_{e}(σˆ ⟨1⟩). Notice also that A_{2e+2} = A_{2e+1}.

Finally take A = ⋃_{s} A_{s}. This ends the construction. We now check that the construction works.

To see that P_{e} is satisfied, consider the least available string σ at stage 2e+1, and assume that Ψ_{e} is defined on all noncomputable functions f ⊃ σ. Then we define the sequence f_{n} ⊃ σ, with f_{n} ∈ domain(Ψ_{e}) whose limit is ⋃_{n} σ_{n} ∈ domain(Ψ_{e}). But then lim_{n} Ψ_{e}(f_{n}) converges to the computable function Ψ_{e}(⋃_{n} σ_{n}): thus if C ≤ A via Ψ_{e} and C is closed, then C contains a computable function.

To show that N_{e} is satisfied, we observe that our action at stage 2e + 2 picks a τ on T_{e} and guarantees that A ∩ [[τ]] = ∅. □

The above theorem provides also another proof, in addition to Theorem 4.8, that 𝔉_{Cl} is strictly included in 𝔉.

Finally, Theorem 6.5 below shows that the nonzero closed degrees do not form a filter, in other words the nonzero closed degrees are properly contained in 𝔉_{Cl}. We first need the following lemma:

Lemma 6.4 If B ≡ C and C is closed then B is either of countable degree or contains a perfect set.

Proof. Suppose Φ(C) ⊆ B. If Φ(C) is countable then C ≥ Φ(C) ≥ B ≥ C and thus B is of countable degree. If not then, as Φ(C) = {g : (∃f)[f ∈ C and Φ(f) = g]} is analytic and uncountable, by a classical theorem due to Suslin (see for instance [5]) Φ(C) contains a perfect set, and thus so does B ⊇ Φ(C). □

Theorem 6.5 There is a closed A of nonzero degree, and a B ≥ A with B not of closed degree.

Proof. By the Lemma, it suffices to construct a closed A not containing computable functions, and a subset B ⊆ A which is not of countable degree and contains no perfect subset. Suppose A is perfect and every member is of minimal Turing degree (see for instance [6]). We build B in 2^{ℵ_{0}} many stages (at stage α we define B_{α}) with the condition that by the end of each stage we have put put fewer than 2^{ℵ_{0}} many elements of A into B, and have guaranteed that fewer than 2^{ℵ_{0}} many (prohibited) specified elements of A will never go into B.

As there are only 2^{ℵ_{0}} many perfect sets P_{α} we may at stage α < 2^{ℵ_{0}} guarantee that P_{α} ⊈ B: If P_{α} ⊈ A then there is nothing to worry about. Otherwise, there is an element f of P_{α} not yet in B_{α} and we satisfy the requirement by prohibiting f from ever entering B, guaranteeing that f ∉ B.

Similarly there are only 2^{ℵ_{0}} many countable sets. Let {(C_{α}, Φ_{α})}_{α<2^{ℵ_{0}}} be an enumeration of all pairs consisting of a countable set, and a Turing functional. Without loss of generality we may assume that the C_{α} do not contain any computable function. We act at stage α to guarantee that Φ_{α}(B) ⊈ C_{α}. If Φ_{α}(A) = {g : (∃f)[f ∈ A and Φ_{α}(f) = g]} is not countable, by Suslin’s theorem it contains a perfect subset and so there are 2^{ℵ_{0}} many elements of A on which Φ_{α} is one-one. We may choose one of these f (that have not been prohibited so far from entering B) with Φ_{α}(f) ∉ C_{α}, such that we can put f into B. This guarantees that Φ_{α}(B) ⊈ C_{α}. On the other hand, if Φ_{α}(A) is countable, then there are 2^{ℵ_{0}} many elements f_{β} of A such that Φ_{α}(f_{β}) is partial for all β or there is an f such that Φ_{α}(f_{β}) = f for all β. In the second case, as the f_{β} are of minimal degree, f is computable. If we now put one of these f_{β} into B then we also guarantee that Φ_{α}(B) ⊈ C_{α}. This shows that B ≱ C for every countable C not containing computable functions, thus B is not of countable degree. □

7 Quotient lattices

Let 𝔐_{/ℑ} denote the quotient lattice obtained dividing 𝔐 by the ideal ℑ.

The equivalence class of a degree A will be denoted by A_{/ℑ}. We recall (see e.g. [1]) that the partial ordering relation in 𝔐_{/ℑ}, denoted by ≤_{/ℑ}, is given by

A_{/ℑ} ≤_{/ℑ} B_{/ℑ} ⇔ (∃D ∈ ℑ)[A ≤ B ∨ D].

The following is an immediate consequence of Lemma 4.6:

Theorem 7.1 𝔐_{Cl} embeds into 𝔐_{/ℑ} as a sublattice.

The next theorem shows that the congruence provided by ℑ is not the identity on the elements of 𝔉.

Theorem 7.2 There exist M-degrees A B in 𝔉 such that B ≰ A but in the quotient 𝔐_{/ℑ}, [B]_{/ℑ} ≤_{/ℑ} A_{/ℑ}.

Proof. We show that there exist mass problems B, D and a singleton {T } such that B does not contain any computable function and is not dense in any computable perfect tree (hence its M-degree is in 𝔉), D is dense, B ≰ {T } (where we identify T with its characteristic function), and

B ≤ {T } ∨ D.

First define a perfect tree T by induction on the length of the input string as follows:

1. T (λ) = λ:

2. Suppose that we have defined T (σ) for all strings σ such that |σ| = e. Suppose also that all T (σ) have the same length, say k. We define T (σˆ ⟨i⟩): pick a function f ∈ [T_{e}], with say f(k) = j; then define T (σˆ ⟨i⟩) = T (σ)ˆ ⟨u_{j}⟩ˆ ⟨i⟩, where u_{j} = 0 if j ≠ 0, and u_{j} = 1 if j = 0.

Notice that [T] (which is in fact a tree in the Cantor space) is not dense in any computable perfect tree. Indeed, if T_{e} is a computable perfect tree then there is an f ∈ [T_{e}] (the one we pick in the construction at the relevant stage) such that f ↾ e+1 is incomparable with all T (τ) with |τ| = e + 1. Now take D = {f : f ≡_{T} T′} (where T′ is the jump of T), and let B = T (D): indeed it suffices to take any dense D whose elements are not ≤_{T} T. We have that D is dense, B is dense in no computable perfect tree, and B ≰ {T }: the last claim follows from the observation that f ≤_{T} T ⊕ T (f), and thus T (f) ≤_{T} T for no f ∈ D. Finally B ≤ {T } ∨ D, as desired. □

Let now 𝔐_{/𝔉} denote the quotient lattice obtained dividing 𝔐 by the filter 𝔉. It is known ([2]) that the cardinality of 𝔐_{/𝔉} is 2^{2^{ℵ_{0}}}.

The equivalence class of a degree A will be denoted by A_{/𝔉}. We recall that the partial ordering relation in 𝔐_{/𝔉}, denoted by ≤_{/𝔉}, is given by

A_{/𝔉} ≤_{/𝔉} B_{/𝔉} ⇔ (∃C ∈ 𝔉)[A ∧ C ≤ B].

It is possible to show that the congruence associated with the filter is not the identity on the elements of ℑ.

Theorem 7.3 There exist M-degrees A and B in ℑ such that B ≰ A but in the quotient 𝔐_{/𝔉}, [B]_{/𝔉} ≤_{/𝔉} A_{/𝔉}.

Proof. Take B = B_{f} and A = B_{f} ∧ deg_{M}({f}), where f is not computable. Then B ∧ deg_{M}({f}) ≤ A, and deg_{M}({f}) ∈ 𝔉_{Cl} ⊆ 𝔉. □

Question 7.4 What is the cardinality of 𝔐_{/ℑ}?

8 A few remarks on degrees of enumerability

A set A is of quasi-minimal e-degree if A is not c.e. and for every total function f, if f ≤_{e} A then f is computable. Moreover, A is of nontotal e-degree if there is no total function f such that f ≡_{e} A.

Lemma 8.1 ([4]) If A ≤ E_{A} and A is countable then there exists f ∈ A such that f ≤_{e} A. Thus if A has nontotal e-degree then E_{A} does not contain any countable mass problem.

Theorem 8.2 ([2]) If A is immune then E_{A} ∈ 𝔉_{Cl}.

Proof. If A is immune then

E_{A} ≥ {f : f 1 − 1 and range(f) ⊆ A} ,

while the latter mass problem is clearly closed and of non-zero degree. □

There are quite natural classes of dense M-degrees that are bounded above by degrees of enumerability. For instance, given any A let E_{A}^{≥_{e}} = {f : A ≤_{e} f}: clearly E_{A}^{≥_{e}} is dense and E_{A}^{≥_{e}} ≤ E_{A}. It is known ([11]) that E_{A}^{≥_{e}} ≤ E_{B}^{≥_{e}} if and only if A ≤_{e} B. For another example of dense degrees below degrees of enumerability, define E_{A}^{∗} = {f : range(f) =^{∗} A}, where =^{∗} denotes equality modulo a finite set.

Theorem 8.3 For every nonempty A, E_{A}^{∗} is dense and if A is not c.e. then E_{A}^{∗} < E_{A}.

Proof. The only nontrivial part is to show that E_{A} ≰ E_{A}^{∗} if A is not c.e.: if E_{A} ≤ E_{A}^{∗} via the Turing functional Ψ then A = ⋃_{σ∈ω^{∗}} Ψ(σ), giving that A is c.e. . □

The degrees of enumerability turn out to be useful to derive easy observations on ℑ and 𝔉. We have already recalled that 𝔉_{Cl} ⊈ 𝔉_{Di} ([2]). The converse inclusion does not hold either:

Corollary 8.4 𝔉_{Di} ⊈ 𝔉_{Cl} Proof. Let A be an immune set of quasiminimal e-degree (see for instance [12]). Then E_{A} ∈ 𝔉_{Cl} by Theorem 8.2. On the other hand by Lemma 8.1, there cannot be any nonzero countable (hence any nonzero discrete) M-degree C such that C ≤ E_{A}. □

Finally, we show that there are mass problems that are dense in some computable perfect tree, but with M-degree not in ℑ: see Theorem 5.3.

Theorem 8.5 There exists a mass problem A which is dense in some computable perfect tree, but deg_{M}(A) ∉ ℑ.

Proof. Let A be an immune set. Let x, y ∈ A, with x ≠ y. We are going to show that E_{A} is dense in some computable perfect tree T, but on the other hand deg_{M}(E_{A}) ∉ ℑ since by Theorem 8.2, E_{A} ∈ 𝔉.

We define T as follows:

1. T (λ) = λ;

2. Suppose that we have defined T (σ). Then define:

T (σˆ ⟨0⟩) = T (σ)ˆ ⟨x⟩,
T (σˆ ⟨1⟩) = T (σ)ˆ ⟨y⟩.

Then T (σˆ ⟨0⟩)|T (σˆ ⟨1⟩) for every σ, and for every g ∈ [T], range(g) ⊆ A, thus [T] ⊆ \overline{E_{A}}. □

Finally:

Theorem 8.6 There exist degrees A and B such that A ≠ 0, A < B, and A is discrete, but B is not discrete. Thus the nonzero discrete degrees are properly contained in 𝔉_{Di}.

Proof. Let f be a noncomputable total function, and let A be such that f <_{e} A, but deg_{e}(A) is not total. (In fact for every f there is such a set A, by relativizing the construction of a quasiminimal e-degree.) Then {f} < E_{A}, but by Lemma 8.1, we have that deg(E_{A}) does not contain any countable mass problem. □

References

[1] R. Balbes and P. Dwinger. Distributive Lattices. University of Missouri Press, Columbia, 1974.

[2] C. Bianchini and A. Sorbi. A note on closed degrees of difficulty of the Medvedev lattice. Math. Logic Quarterly, 42:127–133, 1996.

[3] S. B. Cooper. Computability Theory. Chapman & Hall/CRC Mathematics, Boca Raton, London, New York, Washington, DC, 2003.

[4] E. Z. Dyment. Certain properties of the Medvedev lattice. Mathematics of the USSR Sbornik, 30:321–340, 1976. English Translation.

[5] A. S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer–Verlag, Heidelberg, 1995.

[6] M. Lerman. Degrees of Unsolvability. Perspectives in Mathematical Logic. Springer–Verlag, Heidelberg, 1983.

[7] Y. T. Medevdev. Degrees of difficulty of the mass problems. Dokl. Nauk. SSSR, 104:501–504, 1955.

[8] A. A. Muchnik. On strong and weak reducibility of algorithmic problems. Sibirskii Matematicheskii Zhurnal, 4:1328–1341, 1963. Russian.

[9] R. A. Platek. A note on the cardinality of the Medvedev lattice. Proc. Amer. Math. Soc., 25:917, 1970.

[10] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

[11] M. Rozinas. The semilattice of e-degrees. In Recursive Functions, pages 71–84. Ivanov. Gos. Univ., Ivanovo, 1978. (Russian) MR 82i:03057.

[12] M. G. Rozinas. Partial degrees of immune and hyperimmune sets. Siberian Math. J., 19:613–616, 1978.

[13] G. E. Sacks. On suborderings of degrees of recursive unsolvability. Z. Math. Logik Grundlag. Math., 17:46–56, 1961.

[14] S. G. Simpson. Mass problems and intuitionism. Notre Dame J. Formal Logic, 49(2):127–136, 2008.

[15] E. Z. Skvortsova. Faithful interpretation of the intitionistic prpositional calculus by an initial segment of the Medvedev lattice. Sibirsk. Mat. Zh., 29:171–178, 1988. Russian.

[16] R. I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series. Springer–Verlag, Heidelberg, 1987.

[17] A. Sorbi. On some filters and ideals of the Medvedev lattice. Arch. Math. Logic, 30:29–48, 1990.

[18] A. Sorbi. Embedding Brouwer algebras in the Medvedev lattice. Notre Dame J. Formal Logic, 32(2):266–275, 1991.

[19] A. Sorbi. Some quotient lattices of the Medvedev lattice. Z. Math. Logik Grundlag. Math., 37:167–182, 1991.

[20] A. Sorbi and S. Terwijn. Intermediate logics and factors of the Medvedev lattice. Ann. Pure Appl. Logic, 155(2):69–86, 2008.