Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes

Stephen Binns^{∗} Stephen G. Simpson^{†}

Department of Mathematics Pennsylvania State University State College, PA 16802, USA

December 17, 2003 Originally submitted August 5, 2003 Archive for Mathematical Logic

Abstract

Let P_{w} and P_{M} be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π_{1}^{0} subsets of 2^{ω}, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of P_{w}. We show that many countable distributive lattices are lattice-embeddable below any non-zero element of P_{M}.

1 Introduction

In this paper ω denotes the set of natural numbers, ω^{ω} denotes the set of total functions from ω to ω, and 2^{ω} denotes the set of total functions from ω to {0, 1}.

The concepts of Medvedev reducibility and Muchnik reducibility have been defined and investigated in [11], [22], [12] and [13]. A set P ⊆ ω^{ω} is Medvedev reducible to Q ⊆ ω^{ω}, written P ≤_{M} Q, if there exists some recursive functional, Φ : Q → P. That is, there exists e ∈ ω such that {e}^{f} ∈ P for all f ∈ Q. Muchnik reducibility is a non-uniform version of Medvedev reducibility. P is said to be Muchnik reducible to Q, written P ≤_{w} Q, if for each f ∈ Q there is a recursive functional Φ such that Φ(f) ∈ P.

∗binns@math.psu.edu, http://www.math.psu.edu/binns/.

†simpson@math.psu.edu, http://www.math.psu.edu/simpson/. Simpson’s research was partially supported by NSF Grant DMS-0070718. We thank the anonymous referee for a careful reading of this paper and helpful comments.

In this paper we will restrict these reducibilities to Π_{1}^{0} classes, i.e., Π_{1}^{0} subsets of 2^{ω}. P is said to be a Π_{1}^{0} class if there is some recursive relation R ⊆ ω × 2^{ω} such that

f ∈ P ↔ ∀n R(n, f).

Π_{1}^{0} classes have an alternative characterisation which is both instructive and useful: P is a Π_{1}^{0} class if and only if P is the set of infinite paths through some recursive binary tree. For technical reasons we restrict attention to non-empty Π_{1}^{0} classes, i.e., P ≠ ∅.

Two non-empty Π_{1}^{0} classes, P and Q, are Medvedev (Muchnik) equivalent, P ≡_{M} Q (P ≡_{w} Q), if P ≤_{M} Q and Q ≤_{M} P (P ≤_{w} Q and Q ≤_{w} P). The set of equivalence classes (Medvedev (Muchnik) degrees) with the induced partial order forms a countable distributive lattice with a top and bottom element. These lattices will be denoted P_{M} and P_{w} respectively. The top element of P_{M} (P_{w}) is the Medvedev (Muchnik) degree of the set of completions of Peano Arithmetic, and the bottom element, i.e., zero, is the Medvedev (Muchnik) degree of any Π_{1}^{0} set containing a recursive member. The least upper bound operation in P_{M} and P_{w} is given by

P ∨ Q = {f ⊕ g | f ∈ P, g ∈ Q}

where (f ⊕ g)(2n) = f(n) and (f ⊕ g)(2n + 1) = g(n) for all n. The greatest lower bound operation in P_{M} and P_{w} is given by

P ∧ Q = {⟨0⟩^{⌢}f | f ∈ P } ∪ {⟨1⟩^{⌢}g | g ∈ Q}.

See [16]. The study of P_{M} and P_{w} was initiated in Simpson [17]. Introductions to and some basic results about P_{M} and P_{w} can be found in [2], [16], [3], [19],

[4] and [20].

In this paper we prove the existence of certain sublattices of the lattices P_{w} and P_{M}. Our main results are, in essence, as follows:

1. The free countable Boolean Algebra, F B(ω), is embeddable into P_{w}.

2. The free countable distributive lattice, F D(ω), is embeddable into P_{M}.

3. If L_{1} (L_{2}) denotes the lattice of finite (co-finite) subsets of ω, then L_{1} ×L_{2} is embeddable into P_{M}.

Here, and in the rest of the paper, an “embedding” is a lattice embedding.

Result 1 is as general as possible, as every countable distributive lattice is embeddable into F B(ω). We conjecture that F B(ω) is embeddable into P_{M}, but we have been unable to prove this. Result 2 implies that every finite distributive lattice can be embedded into P_{M}, as every such lattice can be embedded into F D(ω). Result 3 is not implied by result 2, as neither L_{1} nor L_{2} is embeddable into F D(ω). Below we shall give references for the relevant lattice-theoretic facts.

In addition, we show that results 1 through 3 are relativised in the sense that the embeddings can be made below any non-zero element of P_{w} and P_{M}, respectively.

This paper is in four sections. Section 2 consists of two priority arguments. These construct Π_{1}^{0} subsets of 2^{ω} that have certain useful independence properties. Both build on the constructions in [9], and use a Sacks preservation argument (see [21], Section VII.3). The second argument is only sketched. If, at first, the reader wishes only to skim Section 2 and accept Theorems 2.1 and 2.7, he or she should still find Sections 3 and 4 completely accessible. Results 1 through 3 above are proved in Sections 3 and 4.

Notation and Preliminaries

We will first establish some standard notation. A binary string is a finite sequence of 0’s and 1’s. The set of binary strings is denoted 2^{<ω}. We use σ, τ, ρ and λ to denote binary strings. The length of σ will be written |σ|. The concatenation of σ and τ is denoted σ^{⌢}τ. The notation {e}_{s}^{σ}(n) = m means that the Turing machine with Gödel number e using oracle information σ started with input n halts in ≤ s steps with output m. {e}_{s}^{σ} denotes the longest binary string, τ, such that |τ| ≤ s and {e}_{s}^{σ}(n) = τ(n) for all n < |τ|. The empty string is denoted by ⟨⟩, and {e}^{σ} is short for {e}_{|σ|}^{σ}. Thus for f ∈ 2^{ω} and m, n ∈ ω we have {e}^{f}(m) = n if and only if there exists σ ⊂ f such that {e}^{σ}(m) = n. All of this is standard recursion-theoretic notation from Rogers [13] and Soare [21]. The restriction of σ to {0, 1, 2, …, n − 1} is denoted σ|_{n}.

A binary tree is a subset of 2^{<ω} that is closed under taking initial segments. If T is a binary tree, then [T] ⊆ 2^{ω} denotes the set of infinite paths through T, i.e., [T] = {f ∈ 2^{ω} : ∀n f|_{n} ∈ T }. It is well known that P ⊆ 2^{ω} is a Π_{1}^{0} class if and only if P = [T] for some recursive binary tree. Furthermore, if P ⊆ 2^{ω} is a Π_{1}^{0} class, then P = [Ext(P)], where Ext(P) ⊆ 2^{<ω} is defined to be the set of extendible nodes of P, i.e.,

Ext(P) = {σ : ∃f ∈ P σ ⊂ f}.

Note that Ext(P) is a binary tree, but is not necessarily recursive. The advantage of Ext(P) over T is that Ext(P) has no end nodes.

The following notation is introduced specifically for our purposes. Let S be the class of finite sequences of finite strings. The uppercase Greek letters, Σ, Γ and Λ will be used to denote elements of S. For ease of notation, a sequence of strings will sometimes be identified with its range, so that σ ∈ Σ means σ ∈ rng(Σ); Σ ⊆ Γ means Σ is a subsequence of Γ, and σ ∈ Σ ∖ Γ that σ ∈ rng(Σ) ∖ rng(Γ). We will reserve the symbol Σ^{m} to mean the sequence of all binary strings of length m in lexicographical order.

If Σ = ⟨σ_{i}⟩_{i=1}^{n} and Γ = ⟨γ_{i}⟩_{i=1}^{m}, we will say Σ extends Γ if m = n and σ_{i} ⊇ γ_{i} for all i ≤ n. Σ properly extends Γ if, in addition, σ_{k} ⊋ γ_{k} for at least one k ≤ n. If f_{1}, f_{2}, … f_{n} are members of 2^{ω}, then ⟨f_{1}, f_{2}, … f_{n}⟩ extends Σ is defined similarly. We sometimes identify the finite sequence ⟨f_{i}⟩_{i=1}^{n} = ⟨f_{1}, …, f_{n}⟩ with its range.

If Σ = ⟨σ_{i}⟩_{i=1}^{n} ⊆ Σ^{m} and f ∈ 2^{ω}, we will make the following definitions:

• f^{−} ∈ 2^{ω} is such that, for all n ∈ ω, f^{−}(n) = f(n + 1).

• ⨁ Σ = ⨁_{i=1}^{n} σ_{i} ∈ 2^{<ω} is such that

(⨁ Σ) (k) = σ_{i}(j),

for all k = nj + i − 1, 1 ≤ i ≤ n, 0 ≤ j ≤ m − 1. That is,

⨁ Σ = ⨁_{i=1}^{n} σ_{i} = ⟨σ_{1}(0), …, σ_{n}(0), …, σ_{1}(m − 1), …, σ_{n}(m − 1)⟩.

• If ⟨f_{i}⟩_{i=1}^{n} is a sequence of members of 2^{ω}. Then ⨁_{i=1}^{n} f_{i} ∈ 2^{ω} is defined to be such that, for all j,

(⨁_{i=1}^{n} f_{i}) (k) = f_{i}(j),

where, as before, k = nj + i − 1.

• For an arbitrary Γ = ⟨γ_{i}⟩_{i=1}^{n} ∈ S (with the γ_{i} of possibly different lengths), we define

⨁ Γ = ⨁_{i=1}^{n} γ_{i} = ⨁_{i=1}^{n} γ_{i}|_{l},

where l = min{|γ_{i}| : 1 ≤ i ≤ n}.

Although ⨁ is not associative, it does have the useful property that if ⟨f_{1}, f_{2}, … f_{n}⟩ extends Σ ⊆ Σ^{m}, then ⨁_{i=1}^{n} f_{i} ⊃ ⨁ Σ. If no confusion can result, we will write ⨁ f_{i} for ⨁_{i=1}^{n} f_{i}.

2 Two Constructions

A Π_{1}^{0} class P is said to be special if it is non-empty and contains no recursive member.

Theorem 2.1. For any special Π_{1}^{0} class, P, there is a non-empty Π_{1}^{0} set Q ⊆ 2^{ω}, with the properties, for all sequences, ⟨f_{i}⟩_{i=1}^{n} ⊂ Q,

I. ∀f ∈ Q ∖ ⟨f_{i}⟩_{i=1}^{n}, f ≰_{T} ⨁ f_{i},

II. ∀f ∈ P, f ≰_{T} ⨁ f_{i}.

Proof. The proof will closely follow the proof of Theorem 4.7 in [9]. A recursive sequence, ⟨ψ_{s}⟩_{s∈ω}, of recursive functions from 2^{<ω} to 2^{<ω} will be constructed with the properties that, for all σ ∈ 2^{<ω} and s ∈ ω,

1. ψ_{s}(σ^{⌢}⟨0⟩) and ψ_{s}(σ^{⌢}⟨1⟩) are incompatible extensions of ψ_{s}(σ),

2. range(ψ_{s+1}) ⊆ range(ψ_{s}),

3. ψ(σ) = lim_{t} ψ_{t}(σ) exists.

Each ψ_{s} determines a recursive tree, namely,

T_{s} = {τ : for some σ, ψ_{s}(σ) ⊇ τ}.

The required Q will then be ⋂_{s∈ω}[T_{s}]. Q will be non-empty as ⟨[T_{s}]⟩_{s∈ω} is a nested sequence of nonempty closed subsets of 2^{ω}. It will be a Π_{1}^{0} set because,

f ∈ Q ≡ ∀sf ∈ [T_{s}] ≡ ∀s∀n∃σ[|σ| = n ∧ ψ_{s}(σ) ⊂ f],

and ∃σ[|σ| = n ∧ ψ_{s}(σ) ⊂ f] is a recursive predicate.

Each ψ_{s} will induce a mapping, Ψ_{s} : S → S, defined by

Ψ_{s}(Γ) = ⟨ψ_{s}(γ_{i})⟩_{i=1}^{n},

where Γ = ⟨γ_{i}⟩_{i=1}^{n}. When it is proved that ψ(σ) exists for all σ, it will be clear that Ψ(Σ) = lim_{s} Ψ_{s}(Σ) exists for all Σ ∈ S.

We will define ⟨ψ_{s}⟩_{s∈ω} so that, for every m ∈ ω, Γ ⊆ Σ^{m} and e ≤ m, Q satisfies the requirements:

P_{Γ,e}^{m} ≡ for all ⟨f_{i}⟩_{i=1}^{n} extending Ψ(Γ), {e}^{⨁ f_{i}} ∉ P,

R_{Γ,e}^{m} ≡ for all ⟨f_{i}⟩_{i=1}^{n} extending Ψ(Γ), and for all σ ∈ Σ^{m} ∖ Γ, {e}^{⨁ f_{i}} ⊅

ψ(σ).

The P requirements guarantees that Q has property II. of the theorem, and the R requirements guarantee property I. The set of requirements can be ordered lexicographically, first on m, then on e and finally with the conventions that, for all m, and Γ, Γ′ ∈ Σ^{m},

i. P_{Γ,e}^{m} precedes R_{Γ′,e}^{m}, and,

ii. P_{Γ,e}^{m} precedes P_{Γ′,e}^{m} and R_{Γ,e}^{m} precedes R_{Γ′,e}^{m} whenever Γ precedes Γ′ in the lexicographical ordering on Σ^{m}.

Priority is given to the requirements in reverse lexicographical order so that reqirement S_{0} has higher priority than requirement S_{1} if it precedes it in the ordering.

Let T_{P} be some fixed recursive binary tree such that P = [T_{P}]. P_{Γ,e}^{m} is said to be satisfied at stage s if

{e}^{⨁ Ψ_{s}(Γ)} ∉ T_{P} .

R_{Γ,e}^{m} is said to be satisfied at stage s if, for all σ ∈ Σ^{m} ∖ Γ,

{e}^{⨁ Ψ_{s}(Γ)} ⊉ ψ_{s}(σ).

We now define ψ_{s} as follows:

Stage s = 0: ψ_{0}(σ) = σ for all σ ∈ 2^{<ω}.

Stage s+1: We say P_{Γ,e}^{m} requires attention at stage s + 1 if P_{Γ,e}^{m} is not satisfied at stage s + 1 and there is a Λ = ⟨λ_{i}⟩_{i=1}^{n} properly extending Γ such that max{|λ_{j}| : λ_{j} ∈ Λ} ≤ s + 1 and, i. {e}^{⨁ Ψ_{s}(Λ)} ∈ T_{P},

ii. {e}^{⨁ Ψ_{s}(Λ)} ⊋ {e}^{⨁ Ψ_{s}(Γ)}.

We say R_{Γ,e}^{m} requires attention at stage s+1 if R_{Γ,e}^{m} is not satisfied at stage s+1 and there is a Λ = ⟨λ_{i}⟩_{i=1}^{n}, properly extending Γ, such that max{|λ_{j}| : λ_{j} ∈ Λ} ≤ s + 1 and,

{e}^{⨁ Ψ_{s}(Λ)} ⊇ ψ_{s}(σ^{⌢}⟨x⟩), for some x ∈ {0, 1} and σ ∈ Σ^{m} ∖ Γ.

If P_{Γ,e}^{m} has priority greater than the priority of P_{Σ^{s},s}^{s} and is the highest priority requirement requiring attention at stage s+1, let Λ witness this fact and define,

ψ_{s+1}(ν) = \begin{cases}ψ_{s}(λ_{i}^{⌢}ν′) & if ν = γ_{i}^{⌢}ν′ for some γ_{i} ∈ Γ \\ ψ_{s}(ν) & if ν ⊉ γ_{i} for any γ_{i} ∈ Γ. \end{cases}

If R_{m,e}^{X} has priority greater than the priority of P_{Σ^{s},s}^{s} and is the highest priority requirement requiring attention at stage s + 1, let Λ, σ and x witness this and define,

ψ_{s+1}(ν) = \begin{cases}ψ_{s}(λ_{i}^{⌢}ν′) & if ν = γ_{i}^{⌢}ν′ for some γ_{i} ∈ Γ, \\ ψ_{s}(σ^{⌢}⟨1 − x⟩^{⌢}ν′) & if ν = σ^{⌢}ν′, \\ ψ_{s}(ν) & if ν ⊉ τ for any τ ∈ Γ ∪ \{σ\} . \end{cases}

If no requirement of priority greater than the priority of P_{Σ^{s},s}^{s} requires attention at stage s + 1, then let ψ_{s+1} = ψ_{s}.

The following lemmas establish the theorem.

Lemma 2.2. For any requirement, S, there is a stage, s_{0}, such that S does not require attention at any stage t > s_{0}.

Proof. Assume not and let S be the highest priority requirement requiring attention infinitely often. If S = P_{Γ,e}^{m}, then let t be a stage such that P_{Γ,e}^{m} has priority greater than P_{Σ^{t},t}^{t} and such that all higher priority requirements are satisfied for all stages ≥ t. Let s_{1}, s_{2}, s_{3}, … be an infinite increasing sequence of stages greater than t at which S requires attention. At each of these stages S will be the highest priority requirement requiring attention and so s_{1}, s_{2}, s_{3}, … will generate a recursive sequence,

{e}^{⨁ Ψ_{s_{1}} (Γ)} ⊊ {e}^{⨁ Ψ_{s_{2}} (Γ)} ⊊ {e}^{⨁ Ψ_{s_{3}} (Γ)} ⊊ …,

of elements of T_{P}. But then ⋃_{i}{e}^{⨁ Ψ_{s_{i}} (Γ)} is a recursive infinite path through T_{P}, contradicting the original assumption that P is special.

Next suppose S = R_{Γ,e}^{m}. If t is such that the priority of R_{Γ,e}^{m} is greater than P_{Σ^{t},t}^{t}, all higher priority requirements are permanently satisfied at stage t, and S requires attention at stage t, then S will be satisfied at stage t + 1. Suppose, at some stage u > t, a lower priority requirement, T, requires attention. If T = P_{Λ,e′}^{m′} or T = R_{Λ,e′}^{m′} with m′ > m, and any Λ and e′, then Ψ_{u+1}(Γ) = Ψ_{u}(Γ) and S will remain satisfied at stage u + 1. If T = R_{Λ,e′}^{m} or T = P_{Λ,e′}^{m}, then Ψ_{u+1}(Γ) ⊇ Ψ_{u}(Γ) and so S will remain satisfied at stage u + 1. We then argue by induction that S will remain satisfied, and hence not require attention, at all stages u ≥ t, contradicting the assumption.

Lemma 2.3. ψ(σ) = lim_{s} ψ_{s}(σ) exists for all σ.

Proof. Let σ ∈ 2^{<ω} be arbitrary. By Lemma 2.2, there exists a stage, t, such that for all m ≤ |σ|, and all Γ ⊆ Σ^{m}, the requirements R_{Γ,e}^{m} and P_{Γ,e}^{m} do not require attention after stage t. Then ψ_{t_{1}}(σ) = ψ_{t_{2}}(σ) for all t_{1}, t_{2} > t.

Lemma 2.4. If m ∈ ω, e ≤ m and Γ ⊆ Σ^{m} are such that {e}^{⨁ Ψ(Γ)} ∈ T_{P}, then there does not exist a Λ properly extending Γ such that {e}^{⨁ Ψ(Λ)} ∈ T_{P} and {e}^{⨁ Ψ(Λ)} ⊋ {e}^{⨁ Ψ(Γ)}.

Proof. Suppose such a Λ existed for m, e and Γ. Take t so large that Ψ_{t}(Γ) = Ψ(Γ) and Ψ_{t}(Λ) = Ψ(Λ). Then,

{e}^{⨁ Ψ_{t}(Λ)} = {e}^{⨁ Ψ(Λ)} ⊋ {e}^{⨁ Ψ(Γ)} = {e}^{⨁ Ψ_{t}(Γ)},

and so, at some stage u ≥ t, P_{Γ,e}^{m} would be the highest priority requirement requiring attention, implying,

{e}^{⨁ Ψ_{u+1}(Γ)} ⊋ {e}^{⨁ Ψ_{u}(Γ)} = {e}^{⨁ Ψ_{t}(Γ)} = {e}^{⨁ Ψ(Γ)},

contradicting the fact that Ψ_{u+1}(Γ) = Ψ(Γ).

Lemma 2.5. If ⟨f_{i}⟩_{i=1}^{n} ⊆ Q then, for all f ∈ P, f ≰_{T} ⨁ f_{i}.

Proof. We can assume without losing generality that ⟨f_{i}⟩_{i=1}^{n} is in lexicographic order. Suppose the lemma is false and let {e}^{⨁ f_{i}} ∈ P. Let m ∈ ω and Γ ⊆ Σ^{m} be such that,

i. e ≤ m,

ii. ⟨f_{i}⟩_{i=1}^{n} extends Ψ(Γ)

Such a Γ can be found because ⟨f_{i}⟩_{i=1}^{n} is in lexicographic order. But {e}^{⨁ Ψ(Γ)} ∈ T_{P}, so there must be a Λ ⊋ Γ such that {e}^{⨁ Ψ(Λ)} ∈ T_{P} and {e}^{⨁ Ψ(Λ)} ⊋ {e}^{⨁ Ψ(Γ)}, contradicting Lemma 2.4.

Lemma 2.6. For all ⟨f_{i}⟩_{i=1}^{n} ⊆ Q and all f ∈ Q ∖ ⟨f_{i}⟩_{i=1}^{n},

f ≰_{T} ⨁ f_{i}

Proof. Suppose not and let {e}^{⨁ f_{i}} = f ∈ Q. Let m ∈ ω, Γ ⊆ Σ^{m} and σ ∈ Σ^{m} ∖ Γ be such that,

i. e ≤ m,

ii. ⟨f_{i}⟩_{i=1}^{n} extends Ψ(Γ),

iii. f ⊃ ψ(σ), (again we are assuming ⟨f_{i}⟩_{i=1}^{n} is in lexicographic order).

Let t be such that Ψ_{u}(Γ) = Ψ(Γ) and ψ_{u}(σ^{⌢}⟨x⟩) = ψ(σ^{⌢}⟨x⟩) for all u ≥ t and x ∈ {0, 1}. By the supposition, there must be a stage, s ≥ t and a Λ extending Γ such that

{e}^{Ψ_{s}(Λ)} ⊇ ψ_{s}(σ^{⌢}⟨x⟩) for some x ∈ {0, 1}.

So there will be a stage, v ≥ s, at which R_{Γ,e}^{m} requires attention and is, in fact, the highest priority requirement requiring attention. But then,

Ψ_{v+1}(Γ) ≠ Ψ_{v}(Γ) = Ψ(Γ),

contradicting the fact that v ≥ u.

To finish the proof of Theorem 2.1, note that Lemmas 2.5 and 2.6 prove that Q has properties I. and II. as required.

Theorem 2.7. Given any special Π_{1}^{0} class, P, there is an infinite recursive sequence of Π_{1}^{0} sets, ⟨Q_{i} : i ∈ ω⟩, with the properties, for all i, j ∈ ω such that i ≠ j,

I. ∀f ∈ Q_{i} ∀g ∈ Q_{j} f ≰_{T} g,

II. ∀f ∈ Q_{i} ∀g ∈ P g ≰_{T} f.

Proof (sketch). A recursive sequence of recursive functions, ψ^{i} : 2^{<ω} → 2^{<ω}, is constructed, the range of each function is the tree T_{i} and then Q_{i} will be [T_{i}]. Each ψ^{i} is constructed as the limit of a recursive sequence of recursive functions, ⟨ψ_{s}^{i}⟩_{s} and will be defined so that, for every m ∈ ω, ψ^{i} satisfies the requirements:

for all e ≤ m; j ≤ m; σ ∈ Σ^{m} and for all f extending ψ^{i}(σ),
P^{m} ≡ {e}^{f} ∉ P,
R^{m} ≡ j ≠ i ⇒ {e}^{f} ⊉ ψ^{j}(σ).

These requirements are then further specified by indexing them according to i, j, σ and e (bounded as above), and an exhaustive priority ordering is given to them. The same method as in Theorem 2 is then used to ensure all are satisfied. If at any stage of construction an R^{m} requirement is the highest priority requirement requiring attention then the requirement is satisfied (permanently) at the next stage.

If at some stage of the construction a P^{m} requirement is the highest priority requirement requiring attention, then the function being constructed is adapted to keep the requirement unsatisfied (as per Sacks’ preservation strategy, see [21] Section VII.3). A (nonconstructive) argument is then made to show that this strategy will eventually fail (because P has no recursive members) and P_{m} will eventually be satisfied. These are essentially the arguments of Lemmas 2.5 and 2.6.

3 F D(ω) ↪ P_{M}

The following is result 2 of the Introduction. Recall that F D(ω) is the free distributive lattice on ω generators.

Theorem 3.1. Given any special Π_{1}^{0} class, P, F D(ω) can be embedded into P_{M} below P.

Proof. Let P be any special Π_{1}^{0} class and suppose Q and ψ are as in Theorem 2.1. Let {σ_{i} : i ∈ ω} be a set of binary strings defined by:

i. |σ_{i}| = i + 1,

ii. σ_{i}(n) = \begin{cases}1 & if n = i, \\ 0 & otherwise. \end{cases}

Then {σ_{i} : i ∈ ω} is a pairwise incomparable set of strings and hence so is {ψ(σ_{i}) : i ∈ ω}. Denote by Q_{i} the set of members of Q extending ψ(σ_{i}), and let P_{i} = P ∧ Q_{i}. The set {P_{i} : i ∈ ω} then generates a sublattice of P_{M} strictly below P. To see this note that if X is a non-empty finite subset of ω,

⋁_{i∈X} P_{i} <_{M} P,

because ⋁_{i∈X} P_{i} ≤_{M} P, and if ⋁_{i∈X} P_{i} ≥_{M} P then P ∧ ⋁_{i∈X} Q_{i} ≥_{M} P and some member of ⋁_{i∈X} Q_{i} would compute an member of P, contradicting property II. of Theorem 2.1. This is enough to show that all elements of the generated sublattice are strictly below P.

We shall show that the lattice generated by the P_{i}’s is free. By a standard lattice-theoretic result – Theorem II.2.3 in [8] – it suffices to prove the following claim: For all finite sets X, Y ⊆ ω, if ⋀_{i∈X} P_{i} ≤_{M} ⋁_{i∈Y} P_{i} then X ∩ Y ≠ ∅. To prove the claim, note that

⋀_{i∈X} P_{i} ≤_{M} ⋁_{i∈Y} P_{i},
⇒ P ∧ ⋀_{i∈X} Q_{i} ≤_{M} P ∧ ⋁_{i∈Y} Q_{i},
⇒ P ∧ ⋀_{i∈X} Q_{i} ≤_{M} ⋁_{i∈Y} Q_{i}.

Fix ⨁_{i∈Y} f_{j} ∈ ⋁_{i∈Y} Q_{i}. Then there is g ≤_{T} ⨁_{i∈Y} f_{i} such that either g ∈ P or g ∈ Q_{i} for some i ∈ X. But g ∉ P by property II. of Theorem 2.1. So let i ∈ X be such that g ∈ Q_{i}. By property I. of Theorem 2.1 we have that i ∈ Y. Thus X ∩ Y ≠ ∅ as was to be shown.

Corollary 3.2. Every finite distributive lattice can be embedded into P_{M}.

Proof. This follows immediately from Theorem 3.1 and the fact that every finite distributive lattice is embeddable in F D(ω). This seems to have first been observed by Simpson [18]. The proof is presented in [3], along with a different proof of this corollary.

4 F B(ω) ↪ P_{w}

In the section we give the second principal embedding theorem – that the free Boolean algebra on ω generators, F B(ω), is embeddable into P_{w}, the lattice of Muchnik degrees. This is result 1 of the Introduction. We represent F B(ω) as an algebra of recursive sets and then give an explicit embedding into P_{w}. As before, the argument will use Π_{1}^{0} sets constucted using a priority argument, this time on the Π_{1}^{0} sets of Theorem 2.7. Then we show that all countable distributive lattices embed into F B(ω). Finally we establish result 3 of the Introduction.

We require the following definitions. Let ⟨P_{i} : i ∈ ω⟩ be a recursive sequence of Π_{1}^{0} classes. This means that each P_{i} is a Π_{1}^{0} class and furthermore {(x, i) : x ∈ P_{i}} is Π_{1}^{0} subset of 2^{ω} × ω. Let ∅ ≠ A ⊆ ω be recursive. Let (·, ·) : ω × ω → ω be a recursive bijection.

Definition 4.1. If x ∈ 2^{ω}, we define (x)_{i} ∈ 2^{ω} by

(x)_{i}(n) = x((i, n)).

The recursive join of ⟨P_{i} : i ∈ A⟩, denoted ⋁_{i∈A} P_{i}, is given by

x ∈ ⋁_{i∈A} P_{i} ⇔ (x)_{i} ∈ P_{i} for all i ∈ A.

Clearly ⋁_{i∈A} P_{i} is a Π_{1}^{0} class, as

x ∈ ⋁_{i∈A} P_{i} ≡ ∀i (i ∈ A ⇒ (x)_{i} ∈ P_{i}) .

Also, note that there is no restriction on (x)_{i} if i ∉ A.

We will now define a recursive meet. Let A and ⟨P_{i} : i ∈ ω⟩ be as above and, for each i ∈ ω, let T_{i} be a recursive tree such that [T_{i}] = P_{i}. In addition, fix a nonempty Π_{1}^{0} class P which is Medvedev complete, i.e., Q ≤_{M} P for all nonempty Π_{1}^{0} classes Q. (For example, we may take P to be the set of completions of Peano arithmetic.) Fix a recursive tree T such that [T] = P. Let ⟨σ_{j} : j ∈ ω⟩ be the sequence, in lexicographical order, of all binary strings σ such that σ ∈ T but σ^{⌢}⟨0⟩, σ^{⌢}⟨1⟩ ∉ T. The sequence will be infinite as [T] has no recursive member. Define

T^{∗} = T ∪ {σ_{i}^{⌢}τ : i ∈ A, τ ∈ T_{i}}.

Definition 4.2. The recursive meet of ⟨P_{i} : i ∈ A⟩, denoted ⋀_{i∈A} P_{i}, is [T^{∗}], the set of infinite paths through T^{∗}.

Note that if A is finite, the recursive meet and join are Medvedev equivalent to the standard, lattice-theoretic meet and join respectively, allowing us some ambiguity of notation. However, it is not to be assumed that these constructions necessarily give the greatest lower or least upper bounds when A is infinite.

Now let ⟨Q_{i} : i ∈ ω⟩ be as in Theorem 2.7 (with P arbitrary). Define

Q̂_{i} = ⋀_{j≠i} Q_{j},

and, for any recursive, non-empty set, A, let

Q̂(A) = ⋁_{i∈A} Q̂_{i}.

Lemma 4.3. If A, B ≠ ∅ and A ≠ B, then Q̂(A) ≢_{w} Q̂(B) (and therefore Q̂(A) ≢_{M} Q̂(B)).

Proof. Suppose that A and B are as above and that, without losing generality, j ∈ B ∖ A. Choose any x ∈ Q_{j} and define x̄ by,

(x̄)_{i} = σ_{j}^{⌢}x for all i ∈ ω.

Then x̄ ∈ Q̂(A) as σ_{j}^{⌢}x ∈ Q̂_{i} for all i ≠ j and, in particular, for all i ∈ A. Now let y ∈ Q̂_{j} be arbitrary. There are two cases.

Case 1. y = σ_{i}^{⌢}z for some i ≠ j and z ∈ Q_{i}. Then,

y ≡_{T} z ≰_{T} x ≡_{T} x̄,

(z ≰_{T} x as z ∈ Q_{i} and x ∈ Q_{j}, with i ≠ j).

Case 2. y ∈ [T], where [T] is the Medvedev complete Π_{1}^{0} class used in the construction of the recursive meet. Then for any i ∈ ω, there is a z ∈ Q_{i} such that y ≥_{T} z. We choose some i ≠ j, and then fix z. If x̄ ≥_{T} y, we would have,

Q_{j} ∋ x ≡_{T} x̄ ≥_{T} y ≥_{T} z ∈ Q_{i}, with i ≠ j,

contrary to construction of ⟨Q_{i} : i ∈ ω⟩.

Therefore, in both cases we have y ≰_{T} x̄. As y was arbitrary, Q̂_{j} ≰_{w} Q̂(A). But Q̂_{j} ≤_{w} Q̂(B) via the map x ↦ (x)_{j} so it must be that Q̂(B) ≰_{w} Q̂(A) and

therefore that Q̂(B) ≢_{w} Q̂(A), as required.

Lemma 4.4. If A and B are non-empty and recursive, then

Q̂(A ∪ B) ≡_{M} Q̂(A) ∨ Q̂(B).

Proof.

Q̂(A ∪ B) = {x : ∀i ∈ A ∪ B, (x)_{i} ∈ Q̂_{i}},
= {x : ∀i ∈ A, (x)_{i} ∈ Q̂_{i}} ∩ {x : ∀i ∈ B, (x)_{i} ∈ Q̂_{i}},
= Q̂(A) ∩ Q̂(B).

So, x ↦ x ⊕ x, is a map from Q̂(A ∪ B) to Q̂(A) ∨ Q̂(B), and therefore, Q̂(A ∪ B) ≥_{M} Q̂(A) ∨ Q̂(B) . Conversely, let x ⊕ y ∈ Q̂(A) ∨ Q̂(B). Define, z ∈ 2^{ω} by,

(z)_{i} = \begin{cases}(x)_{i} & if i ∈ A \\ (y)_{i} & if i ∈ ω ∖ A. \end{cases}

Then z ≤_{T} x ⊕ y and for all i ∈ A ∪ B, (z)_{i} ∈ Q̂_{i}, so z ∈ Q̂(A ∪ B). Therefore, Q̂(A ∪ B) ≤_{M} Q̂(A) ∨ Q̂(B) as required.

Lemma 4.5. If A and B are recursive and A ∩ B ≠ ∅, then

Q̂(A ∩ B) ≡_{w} Q̂(A) ∧ Q̂(B).

Proof. First, Q̂(A ∩ B) ≤_{w} Q̂(A) ∧ Q̂(B) (in fact, ≤_{M}). If x ∈ Q̂(A) ∧ Q̂(B), then define z ∈ Q̂(A ∩ B) by,

(z)_{i} = (x^{−})_{i} for all i ∈ ω.

If (x)_{i}(0) = 0, then, for all i ∈ A, (z)_{i} ∈ Q̂_{i}, and, a fortiori, for all i ∈ A ∩ B, (z)_{i} ∈ Q̂_{i}. So z ∈ Q̂(A ∩ B). There is a similar argument if (x)_{i}(0) = 1.

Next, Q̂(A ∩ B) ≥_{w} Q̂(A) ∧ Q̂(B). Modulo the following two claims, the argument will be:

Q̂(A ∩ B) = ⋁_{i∈A∩B} Q̂_{i},
≥_{w} ⋁_{i∈A} ⋁_{j∈B} Q̂_{i} ∧ Q̂_{j} (in fact, ≥_{M}; this is Claim 1),
≥_{w} ⋁_{i∈A} Q̂_{i} ∧ ⋁_{j∈B} Q̂_{j} (this is Claim 2),
= Q̂(A) ∧ Q̂(B).

Proof of Claim 1. Let x ∈ ⋁_{i∈A∩B} Q̂_{i} and take any k ∈ A∩B. So (x)_{k} ∈ Q̂_{k}. We define (recursively in x) z ∈ ⋁_{i∈A} ⋁_{j∈B} Q̂_{i} ∧ Q̂_{j} by defining ((z)_{i})_{j} for all i, j ∈ ω, such that,

((z)_{i})_{j} ∈ Q̂_{i} ∧ Q̂_{j} for all i ∈ A and j ∈ B.

To this end, let,

((z)_{i})_{j} = \begin{cases}⟨0⟩^{⌢}(x)_{i} & if i = j, \\ ⟨0⟩^{⌢}(x)_{k} & if i ≠ j and (x)_{k} ⊉ σ_{i}, \\ ⟨1⟩^{⌢}(x)_{k} & if i ≠ j and (x)_{k} ⊇ σ_{i}. \end{cases}

So, suppose that i ∈ A and j ∈ B. If i = j, then i ∈ A ∩ B and ((z)_{i})_{j} = ⟨0⟩^{⌢}(x)_{i} ∈ Q̂_{i} ∧ Q̂_{j}. If i ≠ j and (x)_{k} ⊉ σ_{i}, then (x)_{k} ∈ Q̂_{i}, and ((z)_{i})_{j} = ⟨0⟩^{⌢}(x)_{k} ∈ Q̂_{i} ∧ Q̂_{j}. If i ≠ j and (x)_{k} ⊇ σ_{i}, then (x)_{k} ∈ Q̂_{j} and ((z)_{i})_{j} = ⟨1⟩^{⌢}(x)_{k} ∈ Q̂_{i} ∧ Q̂_{j}. These three cases are exhaustive and so Claim 1 is established. Note that the above is a uniform procedure for computing z from an arbitrary x, and so the stronger, Medvedev reducibility has been shown.

Proof of Claim 2. Let x ∈ ⋁_{i∈A} ⋁_{j∈B} Q̂_{i} ∧ Q̂_{j}. We will construct z ≤_{T} x such that z ∈ ⋁_{i∈A} Q̂_{i} ∧ ⋁_{j∈B} Q̂_{j}. There are two cases.

Case 1. ∃i ∈ A ∖ B ∀j ∈ B ∖ A ((x)_{i})_{j}(0) = 1.

Fix such an i, set z(0) = 1 and let,

(z^{−})_{k} = \begin{cases}((x)_{i})_{k}^{−} & if k ∉ A ∩ B, \\ ((x)_{k})_{k}^{−} & if k ∈ A ∩ B. \end{cases}

Then, if k ∈ B ∖ A, (z^{−})_{k} = ((x)_{i})_{k}^{−} ∈ Q̂_{k} and if k ∈ B ∩ A, (z^{−})_{k} = ((x)_{k})_{k}^{−} ∈ Q̂_{k}. So, for all k ∈ B, (z^{−})_{k} ∈ Q̂_{k}, giving z^{−} ∈ ⋁_{j∈B} Q̂_{j} and z ∈ ⋁_{i∈A} Q̂_{i} ∧ ⋁_{j∈B} Q̂_{j}.

Case 2. ∀i ∈ A ∖ B ∃j ∈ B ∖ A ((x)_{i})_{j}(0) = 0.

Let z(0) = 0 and define,

f(i) = \begin{cases}the least such j & if i ∈ A ∖ B, \\ 0 & otherwise. \end{cases}

Then f ≤_{T} x, and ((x)_{i})_{f(i)}^{−} ∈ Q̂_{i} for all i ∈ A ∖ B. We can then define,

(z^{−})_{k} = \begin{cases}((x)_{k})_{f(k)}^{−} & if k ∉ A ∩ B, \\ ((x)_{k})_{k}^{−} & if k ∈ A ∩ B. \end{cases}

As above we have (z^{−})_{k} ∈ Q̂_{k}, if k ∈ A ∩ B and if k ∈ A ∖ B then (z^{−})_{k} = ((x)_{k})_{f(k)}^{−} ∈ Q̂_{k}. So z^{−} ∈ ⋁_{i∈A} Q̂_{i}, and z ∈ ⋁_{i∈A} Q̂_{i}∧⋁_{j∈B} Q̂_{j}, as required.

We would like to improve Lemma 4.5 by showing that Q̂(A ∩ B) ≡_{M} Q̂(A) ∧ Q̂(B), but the division into cases in the proof of Claim 2 is non-effective and we have only been able to show the weaker result. However, we can improve the result under the stricter conditions of the following lemma.

Lemma 4.6. If A and B are recursive and A ∩ B ≠ ∅ and their symmetric difference

A△B = (A ∖ B) ∪ (B ∖ A)

is finite, then

Q̂(A ∩ B) ≡_{M} Q̂(A) ∧ Q̂(B).

Proof. The proof is identical with the proof of 4.5 noting that, in the proof of Claim 2, the division into two cases is now effective as both A ∖ B and B ∖ A are finite.

We are now in a position to prove the theorem in the title of the section.

Theorem 4.7. The free Boolean algebra on countably many generators, F B(ω), is lattice-embeddable into P_{w}.

Proof. Consider the mapping A ↦ Q̂(A). Lemmas 4.3, 4.4 and 4.5 prove that this is an embedding of the lattice of non-empty, recursive subsets of ω under ∩ and ∪ into P_{w}. So to prove the theorem it is sufficient to show that F B(ω) can be represented by a collection of non-empty, recursive subsets of ω.

Let p_{j} be the j^{th} prime number and let B_{j} = {np_{j} : n ∈ ω}. Define B̃_{j} = (ω ∖ B_{j}) ∪ {0}. The set {B_{j} : j ∈ ω} generates a distributive lattice under operations of intersection and union. Further, this lattice can be extended to a Boolean algebra with 1 represented by ω, 0 represented by {0} and B̃_{j} the Boolean complement of B_{j}. It would, perhaps, seem more natural to have ∅ as the minimum element and ω ∖ B_{j} as the Boolean complement. However, the text definition ensures that each element of the Boolean algebra is non-empty. This Boolean algebra is in fact free and therefore a representation of F B(ω). To show this it is sufficient to show (Exercise II.3.43 [8]) that for all finite X, Y ⊆ ω,

⋂_{i∈X} B_{i} ⊆ ⋃_{j∈Y} B_{j} ⇒ X ∩ Y ≠ ∅.

But this is easily seen as ∏_{i∈X} p_{i} ∈ ⋂_{i∈X} B_{i} and so, if the antecedent holds, ∏_{i∈X} p_{i} ∈ B_{j} for some j ∈ Y. By primality, this means p_{j} = p_{i} for some i ∈ X, giving X ∩ Y ≠ ∅.

Corollary 4.8. F B(ω) is lattice-embeddable into P_{w} below any given special Π_{1}^{0} class, P.

Proof. Let such a P be given and let ⟨Q_{i} : i ∈ ω⟩ be as in Theorem 2.7. The required embedding will be,

A ↦ P ∧ Q̂(A).

The fact that this is a homomorphism follows from the lattice-theoretic identities:

(P ∧ ⋀_{i∈A} Q̂_{i}) ∧ (P ∧ ⋀_{i∈B} Q̂_{i}) = P ∧ ( ⋀_{i∈A} Q̂_{i} ∧ ⋀_{i∈B} Q̂_{i}),

(P ∧ ⋀_{i∈A} Q̂_{i}) ∨ (P ∧ ⋀_{i∈B} Q̂_{i}) = P ∧ ( ⋀_{i∈A} Q̂_{i} ∨ ⋀_{i∈B} Q̂_{i}),

and the fact that A ↦ Q̂(A) describes a lattice homomorphism. To see that it’s an embedding, suppose that A ≠ B and take j ∈ B ∖ A, x ∈ Q_{j} and x̄ ∈ Q̂(A) as in the proof of Lemma 4.3. Let x̄_{1} = ⟨1⟩^{⌢}x̄ ∈ P ∧ Q̂(A). Suppose that there is a y ∈ P ∧ Q̂(B) such that y ≤_{T} x̄_{1}. By the proof of Lemma 4.3 we know that y^{−} ∉ Q̂(B) (or else x̄ ≡_{T} x̄_{1} ≥_{T} y ≡_{T} y^{−} ∈ Q̂(B), contradiction). But, if y^{−} ∈ P, then,

P ∋ y^{−} ≤_{T} x̄_{1} ≡_{T} x ∈ Q_{j},

contrary to the construction of ⟨Q_{i} : i ∈ ω⟩. So there is no y ∈ P ∧ Q̂(B), such that y ≤_{T} x̄_{1}. Therefore, P ∧ Q̂(B) ≰_{M} P ∧ Q̂(A), as required.

Theorem 4.9. Every countable distributive lattice can be embedded into P_{w} below any given special Π_{1}^{0} class.

To prove Theorem 4.9, we show that every countable distributive lattice embeds into F B(ω) and then apply Theorem 4.7. It suffices to prove the following lemma. Although this lemma is surely well known, we have not found it in the literature.

Lemma 4.10. Every countable distributive lattice is isomorphic to a sublattice of F B(ω).

Proof. All the lattice-theoretic background can be found in [8] or [10]. Stone’s Representation Theorem says that every distributive lattice is isomorphic to a lattice of sets under ∪, ∩. It follows immediately that every countable distributive lattice is a sublattice of a countable Boolean algebra. Thus, it suffices to show that for every countable Boolean algebra B there exists a Boolean injection of B into F B(ω).

We find it convenient to work with the Stone spaces of our Boolean algebras. Recall that, under Stone duality, Boolean homomorphisms correspond to continuous mappings. In particular, Boolean injections correspond to continuous surjections, and Boolean surjections correspond to continuous injections. Since the Stone space of F B(ω) is homeomorphic to 2^{ω}, the Stone space of any countable Boolean algebra is homeomorphic to a nonempty closed subset of 2^{ω}.

Thus, it suffices to prove the following lemma (attributed to Sierpiński in [14] page 46):

Lemma 4.11. For every nonempty closed set K ⊆ 2^{ω} there exists a continuous surjection ψ : 2^{ω} ⟶ K.

Proof. Recall that Ext(K) = {σ ∈ 2^{<ω} : ∃f ∈ K f ⊃ σ}. We will define a surjection ϕ : 2^{<ω} ⟶ Ext(K), which will then induce the required map ψ : 2^{ω} → K. Let

ϕ(⟨⟩) = ⟨⟩,

and, for i ∈ {0, 1},

ϕ(σ^{⌢}⟨i⟩) = \begin{cases}ϕ(σ)^{⌢}⟨i⟩ & if ϕ(σ)^{⌢}⟨i⟩ ∈ Ext(K), \\ ϕ(σ)^{⌢}⟨1 − i⟩ & otherwise. \end{cases}

It is clear that ϕ induces a continuous surjection ψ : 2^{ω} → K defined by ψ(f) = ⋃{ϕ(σ) : σ ⊂ f}. This ψ is in fact a retraction of 2^{ω} onto K, i.e., ψ(f) = f for all f ∈ K. See also [14] page 46.

The proofs of Lemma 4.10 and Theorem 4.9 are now complete.

The next theorem is result 3 of the Introduction.

Theorem 4.12. Let L_{1} (L_{2}) be the lattice of finite (co-finite) subsets of ω under ∩ and ∪. Then, for any special Π_{1}^{0} class, P, there is an embedding of L_{1} × L_{2} into P_{M} below P.

Proof. Let E be any infinite, co-infinite recursive subset of ω (for example the even numbers). Let K be the distributive lattice {X ⊆ ω : X△E is finite} with the operations of ∩ and ∪. Then K ≅ L_{1} × L_{2} . (Represent L_{1} by finite subsets of odd numbers and L_{2} by (relatively) co-finite sets of even numbers. The isomorphism is given by (X, Y) ↦ X ∪Y.) The symmetric difference of any two elements of K is finite, so Lemmas 4.3, 4.4, 4.6 and the proof of Corollary 4.8 give the result.

Corollary 4.13. L_{1} and L_{2} are embeddable in P_{M} below any special Π_{1}^{0} class.

Proof. Immediate, as L_{1} and L_{2} are sublattices of K, above.

Note that Theorem 4.12 and Corollary 4.13 are not immediate consequences of Theorem 3.1, because by Balbes [1, Theorem 4.6] neither L_{1} nor L_{2} is embeddable in F D(ω).

References

[1] Raymond Balbes. Projective and injective distributive lattices. Pacific Journal of Mathematics, 21:405–420, 1967.

[2] Stephen E. Binns. The Medvedev and Muchnik Lattices of Π_{1}^{0} Classes. PhD thesis, Pennsylvania State University, August 2003. V + 80 pages.

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

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

[5] COMP-THY e-mail list. http://listserv.nd.edu/archives/comp-thy.html,

September 1995 to the present.

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

[7] FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/,

September 1997 to the present.

[8] George A. Grätzer. General Lattice Theory. Birkhäuser-Verlag, 2nd edition, 1998. XIX + 663 pages.

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

[10] Ralph McKenzie, George F. McNulty, and Walter F. Taylor. Algebras, Lattices, Varieties, volume 1. Wadsworth and Brooks/Cole, 1987. XI + 361 pages.

[11] Yuri T. Medvedev. Degrees of difficulty of mass problems. Doklady Akademii Nauk SSSR, n.s., 104:501–504, 1955. In Russian.

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

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

[14] Roman Sikorski. Boolean Algebras. Springer-Verlag, 3rd edition, 1969. X + 237 pages.

[15] S. G. Simpson, editor. Reverse Mathematics 2001. Lecture Notes in Logic. Association for Symbolic Logic, 2004. To appear.

[16] Stephen G. Simpson. Π_{1}^{0} sets and models of WKL_{0}. In [15]. Preprint, April 2000, 29 pages, to appear.

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

[18] Stephen G. Simpson. Medvedev degrees of nonempty Pi^0_1 subsets of 2^omega. COMP-THY e-mail list [5], June 9, 2000.

[19] Stephen G. Simpson. Some Muchnik degrees of Π_{1}^{0} subsets of 2^{ω}. June 2001. Preprint, 7 pages, in preparation.

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

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

[22] Andrea Sorbi. The Medvedev lattice of degrees of difficulty. In [6], pages 289–312, 1996.