Mass Problems and Randomness

Stephen G. Simpson Department of Mathematics Pennsylvania State University

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

Draft: October 27, 2004

This research was partially supported by NSF grant DMS-0070718. I would like to thank Stephen Binns for discussing these topics with me.

AMS 2000 Subject Classifications: 03D30, 03D80, 03D25, 03F35, 03F15, 68Q30, 68Q15.

Bulletin of Symbolic Logic, 11, 2005, pp. 1–27.

Abstract

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We focus on the countable distributive lattices P_{w} and P_{s} of weak and strong degrees of mass problems given by nonempty Π_{1}^{0} subsets of 2^{ω}. Using an abstract Gödel/Rosser incompleteness property, we characterize the Π_{1}^{0} subsets of 2^{ω} whose associated mass problems are of top degree in P_{w} and P_{s}, respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P_{w}. Namely, we characterize r as the unique largest weak degree of a Π_{1}^{0} subset of 2^{ω} of positive measure. Within P_{w} we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π_{1}^{0} subsets of 2^{ω}. In addition, we present other natural examples of intermediate degrees in P_{w}. We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory.

Contents

Abstract 1

Contents 2

1 Introduction 2

2 Recursion-theoretic preliminaries 3

3 Mass problems 4

4 Recursively bounded Π_{1}^{0} sets 6

5 The lattices P_{w} and P_{s} 9

6 Weak and strong completeness 11

7 Π_{1}^{0} sets of positive measure 13

8 Π_{1}^{0} sets of random reals 15

9 Thin Π_{1}^{0} subsets of 2^{ω} 18

10 Some additional natural examples in P_{w} 22

References 25

1 Introduction

Among the principal objects of study in recursion theory going back to the seminal work of Turing [59] and Post [44] have been the upper semilattice D_{T} of all Turing degrees, i.e., degrees of unsolvability, and its countable sub-semilattice R_{T} consisting of the recursively enumerable Turing degrees, i.e., the Turing degrees of recursively enumerable sets of positive integers. See for instance Sacks [46], Rogers [45], Lerman [36], Soare [56], Odifreddi [42, 43].

A major difficulty or obstacle in the study of R_{T} has been the lack of natural examples. Although it has long been known that R_{T} is infinite and structurally rich, to this day no specific, natural examples of recursively enumerable Turing degrees are known, beyond the two original examples noted by Turing: 0′ = the Turing degree of the Halting Problem, and 0 = the Turing degree of solvable problems. Furthermore, 0′ and 0 are respectively the top and bottom elements of R_{T}. This lack of natural examples, although well known and a major source of frustration, has almost never been discussed in print, but see Rogers [45, Section 9.6]. In any case, the paucity of examples in R_{T} is striking, because it is well known that most other branches of mathematics are motivated and nurtured by a rich stock of natural examples. Clearly it ought to be of interest to somehow overcome this deficiency in the study of R_{T}.

In recent years it has emerged that there are some natural, important, wellbehaved degree structures, closely related to but different from R_{T}, which do not suffer from the above mentioned deficiency. Simpson 1999 [50, 51, 54] called attention to the countable distributive lattices P_{w} and P_{s} of weak and strong degrees of mass problems given by nonempty Π_{1}^{0} subsets of 2^{ω}, and noted the existence of specific, natural degrees which are intermediate between the top and bottom elements of P_{w} and P_{s}. One of the natural intermediate degrees noted by Simpson was the weak degree r of the set of Turing oracles which are random in the sense of Martin-Löf [39]. The study of P_{w} and P_{s} has been continued by Simpson [53, 49], Cenzer/Hinman [9], Simpson/Slaman [55], Binns [3, 4, 5], Binns/Simpson [6], Terwijn [58].

The purpose of the present paper is to elucidate additional properties of previously noted natural degrees in P_{w} and P_{s}, and to present some additional natural degrees in P_{w}. Along the way we give a somewhat leisurely introduction to mass problems in general, and to P_{w} and P_{s} in particular, and we review other known results concerning P_{w} and P_{s}.

In a later paper [48] we shall exhibit a natural embedding of the countable upper semilattice R_{T} into the countable distributive lattice P_{w}. This embedding will be one-to-one and will preserve the top and bottom elements as well as the partial order relation and least upper bound operation from R_{T}. In this way we shall see that P_{w} provides a satisfactory solution to several of the well known difficulties concerning R_{T}.

2 Recursion-theoretic preliminaries

In this section we establish notation concerning recursive functionals and Turing degrees.

Throughout this paper we use standard recursion-theoretic notation and concepts from Rogers [45] and Soare [56]. We write ω = {0, 1, 2, …} for the set of natural numbers. We write ω^{ω} for the space of total functions from ω into ω. We write 2^{ω} for the subspace of ω^{ω} consisting of the total functions from ω into {0, 1}. We sometimes identify a set A ⊆ ω with its characteristic function χ_{A} ∈ 2^{ω} given by χ_{A}(n) = 1 if n ∈ A, 0 if n ∉ A. For e, n, m ∈ ω and f ∈ ω^{ω} we write {e}^{f}(n) = m to mean that the Turing machine with Gödel number e and oracle f and input n eventually halts with output m. Furthermore, {e}^{f}(n) ↓ means that {e}^{f}(n) is defined, i.e., ∃m ({e}^{f}(n) = m), and {e}^{f}(n) ↑ means that {e}^{f}(n) is undefined, i.e., ¬ ∃m ({e}^{f}(n) = m). In the absence of an oracle f, we write simply {e}(n) = m, etc. For P ⊆ ω^{ω} we consider recursive functionals Φ : P → ω^{ω} given by Φ(f)(n) = {e}^{f}(n) for some e ∈ ω and all f ∈ P and n ∈ ω. In particular, a function h : ω → ω is said to be recursive or computable if there exists e ∈ ω such that h(n) = {e}(n) for all n ∈ ω. (The terms “recursive” and “computable” are synonymous.) A set A ⊆ ω is said to be recursively enumerable if it is the image of a recursive function, i.e., A = {m | ∃n (h(n) = m)} for some recursive h : ω → ω.

For f, g ∈ ω^{ω} we write f ≤_{T} g to mean that f is Turing reducible to g, i.e., ∃e ∀n (f(n) = {e}^{g}(n)). The Turing degree of f, denoted deg_{T} (f), is the set of all g such that f ≡_{T} g, i.e., f ≤_{T} g and g ≤_{T} f. The set D_{T} of all Turing degrees is partially ordered by putting deg_{T} (f) ≤ deg_{T} (g) if and only if f ≤_{T} g. Under this partial ordering, the bottom element of D_{T} is 0 = {f ∈ ω^{ω} | f is recursive}. It is known that D_{T} has no top element. Within D_{T}, the least upper bound of deg_{T} (f) and deg_{T} (g) is given as deg_{T} (f ⊕ g) where (f ⊕ g)(2n) = f(n) and (f ⊕ g)(2n + 1) = g(n) for all n ∈ ω. The standard, natural example of a Turing degree > deg_{T} (f) is given by the Turing jump operator, deg_{T} (f) ↦ deg_{T} (f)′ = deg_{T} (f′), where f′ is (the characteristic function of) the Halting Problem relative to f, H^{f} = {e | {e}^{f}(0) ↓}. A Turing degree is said to be recursively enumerable if it is deg_{T} (f) where f = χ_{A} is the characteristic function of a recursively enumerable set A ⊆ ω. The set of all recursively enumerable Turing degrees is denoted R_{T}. Clearly R_{T} is countable, because there are only countably many recursively enumerable sets. It is known that R_{T} is closed under the least upper bound operation inherited from D_{T}, and that 0′ and 0 are the top and bottom elements of R_{T}. Thus R_{T} is a countable upper semilattice with a top and bottom element.

3 Mass problems

A mass problem is a subset of ω^{ω}. The underlying idea here is to view a set P ⊆ ω^{ω} as a “problem” with a “solution” that does not necessarily exist and is not necessarily unique. The “solutions” of P are simply the members of P. In the special case when P is a singleton set, the “solution” exists and is unique, and the mass problem corresponds to a Turing degree.

In accordance with the conceptual scheme which was explained in the previous paragraph, one makes the following definitions.

Definition 3.1. Let P and Q be subsets of ω^{ω}. We say that P is weakly reducible to Q, written P ≤_{w} Q, if for all g ∈ Q there exists f ∈ P such that f ≤_{T} g. Conceptually this means that, given any “solution” of the mass problem Q, we can use it as an oracle to compute a “solution” of the mass problem P. The weak degree of P, written deg_{w}(P), is the set of all Q such that P ≡_{w} Q, i.e., P ≤_{w} Q and Q ≤_{w} P. The set D_{w} of all weak degrees is partially ordered by putting deg_{w}(P) ≤ deg_{w}(Q) if and only if P ≤_{w} Q.

Remark 3.2. The concept of weak reducibility goes back to Muchnik [41] and has sometimes been called Muchnik reducibility.

Definition 3.3. We say that P is strongly reducible to Q, written P ≤_{s} Q, if there exists e ∈ ω such that for all g ∈ Q there exists f ∈ P such that f(n) = {e}^{g}(n) for all n ∈ ω. In other words, P ≤_{s} Q if and only if there exists a recursive functional Φ : Q → P. Note that strong reducibility is the uniform variant of weak reducibility. Just as for weak degrees, the strong degree of P, written deg_{s}(P), is the set of all Q such that P ≡_{s} Q, i.e., P ≤_{s} Q and Q ≤_{s} P. The set D_{s} of all strong degrees is partially ordered by putting deg_{s}(P) ≤ deg_{s}(Q) if and only if P ≤_{s} Q.

Remark 3.4. The concept of strong reducibility goes back to Medvedev [40] and has sometimes been called Medvedev reducibility.

Remark 3.5. Given P, Q ⊆ ω^{ω}, a recursive homeomorphism of P onto Q is a recursive functional Φ : P → Q mapping P one-to-one onto Q such that the inverse functional Φ^{−1} : Q → P is also recursive. In this case we say that P and Q are recursively homeomorphic. In addition, let us say that P is Turing degree isomorphic to Q if {deg_{T} (f) | f ∈ P } = {deg_{T} (g) | g ∈ Q}. Clearly recursive homeomorphism of P and Q implies strong equivalence and Turing degree isomorphism, either of which implies weak equivalence. No other implications hold.

Theorem 3.6. D_{w} and D_{s} are distributive lattices. They have a bottom element, denoted 0, and a top element, denoted ∞.

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

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

The greatest lower bound of deg_{w}(P) and deg_{w}(Q) in D_{w} is deg_{w}(P ∪ Q), or deg_{w}(P + Q) where

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

The greatest lower bound of deg_{s}(P) and deg_{s}(Q) in D_{s} is deg_{s}(P + Q). It is straightforward to check distributivity. The bottom element of D_{w} and D_{s} is

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

The top element of D_{w} and D_{s} is ∞ = {∅}, where ∅ denotes the empty set.

Remark 3.7. There are obvious, natural embeddings of D_{T} into D_{w} and D_{s} given by deg_{T} (f) ↦ deg_{w}({f}) and deg_{T} (f) ↦ deg_{s}({f}) respectively. Here {f} is the singleton set whose only member is f ∈ ω^{ω}. These embeddings are one-to-one and preserve 0 and the partial order relation and least upper bound operation from D_{T}.

Remark 3.8. There is an obvious lattice homomorphism of D_{s} onto D_{w} given by deg_{s}(P) ↦ deg_{w}(P).

Remark 3.9. D_{w} is canonically isomorphic to the lattice of upward closed subsets of D_{T} under the set-theoretic operations of intersection and union. Namely, for each P ⊆ ω^{ω}, the weak degree deg_{w}(P) ∈ D_{w} gets mapped to the upward closure of {deg_{T} (f) | f ∈ P } within D_{T}. It follows that D_{w} is a complete distributive lattice. We do not know of an analogous set-theoretic representation of D_{s}.

Remark 3.10. For a survey of general mass problems, see Sorbi [57].

4 Recursively bounded Π_{1}^{0} sets

In this section we present some well known generalities concerning recursively bounded Π_{1}^{0} sets and almost recursive functions. The reader is advised to skip most of this section now, and refer to it later as needed.

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

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

A set P ⊆ ω^{ω} is said to be Π_{1}^{0} if there exists a recursive predicate R ⊆ ω^{ω} × ω such that P = {f | ∀n R(f, n)}.

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

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

is a string of length k + l. Note that σ ⊆ τ if and only if σ^{⌢}ρ = τ for some ρ, and this implies lh(σ) ≤ lh(τ). If σ is a string of length k, then for all f ∈ ω^{ω} we have σ^{⌢}f ∈ ω^{ω} defined by (σ^{⌢}f)(i) = σ(i) for i < k, f(i−k) for i ≥ k. Note that σ ⊂ f if and only if σ^{⌢}g = f for some g ∈ ω^{ω}. A tree is a set T ⊆ ω^{<ω} such that, for all σ ⊆ τ ∈ T, σ ∈ T. A path through T is an f ∈ ω^{ω} such that (∀σ ⊂ f) (σ ∈ T). The set of all paths through T is denoted [T]. We sometimes identify a string σ with its Gödel number #(σ) ∈ ω. A tree T is said to be recursive if {#(σ) | σ ∈ T } is recursive, and Π_{1}^{0} if {#(σ) | σ ∈ T } is Π_{1}^{0}.

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

Proof. If T is a recursive tree, we have [T] = {f | ∀n R(f, n)} where R(f, n) is the recursive predicate asserting that ⟨f(0), …, f(n − 1)⟩ ∈ T. Thus [T] is Π_{1}^{0}. For the converse, assume that P is Π_{1}^{0} with index e, i.e., via the Turing machine with Gödel number e. Thus for all f ∈ ω^{ω} we have f ∈ P if and only if ∀n ({e}^{f}(n) = 1), if and only if ∀n ({e}^{f}(n) ≠ 0). Let us write {e}^{σ}(n) = m to mean that {e}^{f}(n) = m via a Turing machine computation using only oracle information from σ ⊂ f and halting in ≤ lh(σ) steps. Note that the 4-place relation {e}^{σ}(n) = m and the 3-place relation {e}^{σ}(n) ↓ are primitive recursive. We have f ∈ P if and only if ∀n (∀σ ⊂ f) ({e}^{σ}(n) ≠ 0), if and only if (∀σ ⊂ f) (∀n ≤ lh(σ)) ({e}^{σ}(n) ≠ 0). Thus P = [T] where T is the primitive recursive tree consisting of all strings σ such that (∀n ≤ lh(σ)) ({e}^{σ}(n) ≠ 0).

Theorem 4.4. If P, Q ⊆ ω^{ω} are Π_{1}^{0} and Φ : P → ω^{ω} is a recursive functional, then the preimage {f ∈ P | Φ(f) ∈ Q} is Π_{1}^{0}.

Proof. By Theorem 4.3 let T be a recursive tree such that Q = [T]. Let e be an index of Φ, i.e., Φ(f)(n) = {e}^{f}(n) for all f ∈ P and all n. Given f ∈ P, we have Φ(f) ∈ Q if and only if for all σ ⊂ f and all τ ∉ T there exists n < lh(τ) such that {e}^{σ}(n) ≠ τ(n). It follows that {f ∈ P | Φ(f) ∈ Q} is Π_{1}^{0}.

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

Remark 4.6. Any subset of a recursively bounded set is recursively bounded. We shall be concerned with subsets of ω^{ω} which are recursively bounded and Π_{1}^{0}. In particular, 2^{ω} is recursively bounded and Π_{1}^{0}, and we are especially interested in Π_{1}^{0} subsets of 2^{ω}. As in Theorem 4.3, P is a Π_{1}^{0} subset of 2^{ω} if and only if P = [T] for some recursive tree T ⊆ 2^{<ω}. Here 2^{<ω} denotes the set of all strings of 0’s and 1’s. See also Theorem 4.10 and Corollary 4.11 below.

Theorem 4.7. Assume that P ⊆ ω^{ω} is recursively bounded Π_{1}^{0}, and assume that Φ : P → ω^{ω} is a recursive functional. Then the image {Φ(f) | f ∈ P } is recursively bounded Π_{1}^{0}. Moreover, there exists a total recursive functional Φ^{∗} : ω^{ω} → ω^{ω} such that Φ^{∗} extends Φ, i.e., Φ^{∗}(f) = Φ(f) for all f ∈ P.

Proof. The key to the proof is compactness. Let h ∈ ω^{ω} be a recursive function such that ∀i (∀f ∈ P) (f(i) < h(i)). Then P is a closed set in the product space

Q_{h} = ∏_{i∈ω}{0, 1, …, h(i) − 1} = {f ∈ ω^{ω} | ∀i (f(i) < h(i))}.

By general topology, Q_{h} is compact. Let T be a recursive tree such that P = [T]. Let e be an index of Φ, i.e., Φ(f)(n) = {e}^{f}(n) for all f ∈ P and all n. Then for each n there is a covering of Q_{h} by clopen sets {f | σ ⊂ f} where σ is a string such that either {e}^{σ}(n) ↓ or σ ∉ T. By compactness of Q_{h}, there exists a finite subcovering. Since h and T are recursive, a particular finite subcovering σ_{n}^{0}, …, σ_{n}^{k_{n}} can be found effectively. Put

h^{∗}(n) = max {{e}^{σ_{n}^{i}}(n) + 1 | i ≤ k_{n} and σ_{n}^{i} ∈ T } .

Then h^{∗} : ω → ω is a recursive function, and Φ(f)(n) < h^{∗}(n) for all f ∈ P and all n. Thus {Φ(f) | f ∈ P } is recursively bounded. For all g ∈ ω^{ω} we have g ∈ {Φ(f) | f ∈ P } if and only if there is no finite covering of Q_{h} by strings σ such that either {e}^{σ}(n) ↓ and ≠ g(n) for some n, or else σ ∉ T. Thus {Φ(f) | f ∈ P } is Π_{1}^{0}. We have now proved the first part of the lemma. To prove the second part, define a recursive functional Φ^{∗} : ω^{ω} → ω^{ω} by putting Φ^{∗}(f)(n) = {e}^{σ_{n}^{i}}(n) where i ≤ k_{n} is minimal such that σ_{n}^{i} ⊂ f and σ_{n}^{i} ∈ T, or Φ^{∗}(f)(n) = 0 if no such i exists. Clearly Φ^{∗} is recursive and extends Φ.

Definition 4.8. In general, suppose that to each n ∈ ω we have effectively associated a finite sequence of ordered pairs (σ_{n}^{0}, m_{n}^{0}), …, (σ_{n}^{k_{n}}, m_{n}^{k_{n}}) where σ_{n}^{i} ∈ ω^{<ω} and m_{n}^{i} ∈ ω for each i ≤ k_{n}. Define a recursive functional Φ : ω^{ω} → ω^{ω} by putting Φ(f)(n) = m_{n}^{i} where i ≤ k_{n} is minimal such that σ_{n}^{i} ⊂ f, or Φ(f)(n) = 0 if no such i exists. Then Φ is called a truth table functional. For f, g ∈ ω^{ω} we say that f is truth table reducible to g, written f ≤_{tt} g, if there exists a truth table functional Φ such that f = Φ(g). Rogers [45, Chapter 8 and Section 9.6] provides general background on truth table reducibility.

Corollary 4.9. Assume that P ⊆ ω^{ω} is recursively bounded Π_{1}^{0}, and assume that Φ : P → ω^{ω} is a recursive functional. Then Φ can be extended to a truth table functional. In particular, Φ(f) ≤_{tt} f for all f ∈ P.

Proof. In the proof of Theorem 4.7, note that Φ^{∗} is a truth table functional.

Theorem 4.10. Let P be a recursively bounded Π_{1}^{0} set. Then P is recursively homeomorphic to a Π_{1}^{0} subset of 2^{ω}.

Proof. Given a recursively bounded Π_{1}^{0} set P ⊆ ω^{ω}, put

P^{∗} = {G_{f} | f ∈ P } ⊆ 2^{ω}

where G_{f} = (the characteristic function of) {2^{m}3^{n} | f(m) = n}. Clearly f ↦ G_{f} is a recursive homeomorphism of P onto P^{∗}. By Theorem 4.7, P^{∗} is Π_{1}^{0}.

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

Proof. This is immediate from Theorem 4.10.

Definition 4.12. Given P ⊆ ω^{ω}, put

Ext(P) = {σ | (∃f ∈ P) (σ ⊂ f)} ⊆ ω^{<ω},

the set of extendible nodes of P. Note that Ext(P) is a tree, and [Ext(P)] is the topological closure of P in ω^{ω}. In particular, if P is Π_{1}^{0}, then P = [Ext(P)].

Lemma 4.13. Let P be a recursively bounded Π_{1}^{0} set. Then Ext(P) is Π_{1}^{0}.

Proof. Let T be a recursive tree such that P = [T]. Let h ∈ ω^{ω} be a recursive function such that ∀n (∀f ∈ P) (f(n) < h(n)). As in the proof of Theorem 4.7, consider the compact space Q_{h} = {g | ∀n (g(n) < h(n))}. For each σ ∈ ω^{<ω}, we have σ ∉ Ext(P) if and only if Q_{h} is covered by clopen sets {g | τ ⊂ g} such that either τ ∉ T or τ is incompatible with σ. In this case, compactness of Q_{h} implies the existence of a finite subcovering. Moreover, since h and T are recursive, such a finite subcovering can be found effectively. Thus {#(σ) | σ ∉ Ext(P)} is recursively enumerable, i.e., Σ_{1}^{0}. It follows that Ext(P) is Π_{1}^{0}.

Definition 4.14. For P ⊆ ω^{ω}, an isolated point of P is an f ∈ P such that, for some string τ, f is the unique g ∈ P such that τ ⊂ g. We say that P is perfect if P has no isolated points.

Theorem 4.15. Let P be a recursively bounded Π_{1}^{0} set. If f is an isolated point of P, then f is recursive.

Proof. By Theorem 4.10 we may assume that P is a Π_{1}^{0} subset of 2^{ω}. Let τ ∈ 2^{<ω} be such that f is the unique g ∈ P such that τ ⊂ g. Then, for all σ ⊇ τ in 2^{<ω}, we have σ ⊂ f if and only if σ ∈ Ext(P). By Lemma 4.13, Ext(P) is Π_{1}^{0}, hence A = 2^{<ω} \ Ext(P) is recursively enumerable. Now, given σ ∈ 2^{<ω} of length n, we have σ ⊂ f if and only if ρ ∈ A for all ρ ∈ 2^{<ω} of length n other than σ. Since {ρ ∈ 2^{<ω} | lh(ρ) = n} is of cardinality 2^{n}, it follows that {σ | σ ⊂ f} is recursively enumerable, so f is recursive.

Corollary 4.16. Let P be a recursively bounded Π_{1}^{0} set. If the weak or strong degree of P is > 0, then P is perfect.

Proof. For any P ⊆ ω^{ω}, we have deg_{w}(P) > 0 or deg_{s}(P) > 0 if and only if P has no recursive members. If P is recursively bounded Π_{1}^{0} and has no recursive members, then by Theorem 4.15 P has no isolated points, i.e., P is perfect.

Definition 4.17. We say that g ∈ ω^{ω} is almost recursive if for all f ≤_{T} g there exists h ∈ ω^{ω} such that ∀n (f(n) < h(n)) and h is recursive. (Turing degrees which contain almost recursive functions have been known in the literature as hyperimmune-free Turing degrees.)

Theorem 4.18. Suppose g is almost recursive. Then for all f ≤_{T} g we have f ≤_{tt} g, i.e., f is truth table reducible to g. In particular, f = Φ(g) for some total recursive functional Φ : ω^{ω} → ω^{ω}.

Proof. Let e be such that f(n) = {e}^{g}(n) for all n. Define f^{∗} ∈ ω^{ω} by f^{∗}(n) = the least k such that {e}^{τ} (n) ↓ where τ = ⟨g(0), …, g(k)⟩. Clearly f^{∗} ≤_{T} g. Since g is almost recursive, there exists a recursive function h such that ∀n (f^{∗}(n) < h(n)). Define Φ : ω^{ω} → ω^{ω} by putting Φ(\overline{g})(n) = \{e\}\overline{τ} (n) where \overline{τ} = ⟨\overline{g}(0), …, \overline{g}(h(n))⟩, if \{e\}\overline{τ} (n) ↓, and Φ(\overline{g})(n) = 0 otherwise, for all \overline{g} ∈ ω^{ω} and n ∈ ω. Then Φ is a truth table functional, and f = Φ(g).

We end this section with the Almost Recursive Basis Theorem.

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

Proof. This is the Hyperimmune-Free Basis Theorem of Jockusch/Soare [26, Theorem 2.4]. For completeness we present the proof here. Define inductively a sequence of nonempty Π_{1}^{0} sets P = P_{0} ⊇ P_{1} ⊇ ⋯ ⊇ P_{e} ⊇ P_{e+1} ⊇ ⋯ as follows. Put P_{0} = P. If ∃n (∃f ∈ P_{e}) ({e}^{f}(n) ↑), fix such an n and put P_{e+1} = {f ∈ P_{e} | {e}^{f}(n) ↑}. Otherwise, Theorem 4.7 gives us a recursive function h = h_{e} such that ∀n (∀f ∈ P_{e}) ({e}^{f}(n) < h(n)), and in this case we put P_{e+1} = P_{e}. By compactness, ⋂_{e=0}^{∞} P_{e} is nonempty, so let g ∈ ⋂_{e=0}^{∞} P_{e}. By construction, g is almost recursive.

5 The lattices P_{w} and P_{s}

In this section we introduce the lattices P_{w} and P_{s} which are the focus of this paper.

Remark 5.1. There is a large recursion-theoretic literature concerning Turing degrees of members of Π_{1}^{0} subsets of ω^{ω}, and especially Turing degrees of members of recursively bounded Π_{1}^{0} subsets of ω^{ω}. See for instance the classic paper of Jockusch and Soare [26] and the survey article by Cenzer and Remmel [10]. Mindful of this literature, we find it natural to view nonempty recursively bounded Π_{1}^{0} sets as mass problems.

By Theorem 4.10 and Corollary 4.11, it suffices to consider Π_{1}^{0} subsets of 2^{ω}.

Definition 5.2. P_{w} (P_{s}) is the set of weak (strong) degrees of nonempty recursively bounded Π_{1}^{0} sets. By Corollary 4.11, P_{w} (P_{s}) is the same as the set of weak (strong) degrees of nonempty Π_{1}^{0} subsets of 2^{ω}.

Theorem 5.3. P_{w} and P_{s} are countable distributive lattices with a top and bottom element, denoted 1 and 0 respectively.

Proof. If P, Q ⊆ ω^{ω} are Π_{1}^{0} and recursively bounded, then so are P ∩ Q, P ∪ Q, P × Q, and P + Q. In particular, P_{w} and P_{s} are closed under the least upper bound and greatest lower bound operations inherited from the distributive lattices D_{w} and D_{s}, respectively. It follows that P_{w} and P_{s} are distributive lattices. Clearly P_{w} and P_{s} are countable, because there are only countably many Π_{1}^{0} subsets of 2^{ω}. Clearly 0 = deg_{w}(2^{ω}) = deg_{s}(2^{ω}) is the bottom element of P_{w} and of P_{s}. It remains to show that P_{w} and P_{s} have a top element. Let PA be the set of completions of Peano Arithmetic. Identifying sentences with their Gödel numbers, we may view PA as a Π_{1}^{0} subset of 2^{ω}. Since Peano Arithmetic is consistent, PA is nonempty. It is known that every nonempty Π_{1}^{0} subset of 2^{ω} is ≤_{s} PA, hence ≤_{w} PA. We shall obtain this result and much more in Section 6 below, but see Jockusch/Soare [26]. Let us use 1 ambiguously to denote either deg_{w}(PA) or deg_{s}(PA). Thus 1 is the top element both of P_{w} and of P_{s}.

Remark 5.4. There is an obvious lattice homomorphism of P_{s} onto P_{w} given by deg_{s}(P) ↦ deg_{w}(P). Simpson and Slaman [55] have shown that every nonzero weak degree in P_{w} contains infinitely many strong degrees in P_{s}.

Remark 5.5. In the context of recursively bounded Π_{1}^{0} sets, there is reason to view weak reducibility as the mass problem analog of Turing reducibility, while strong reducibility is the mass problem analog of truth table reducibility. See Rogers [45, Sections 8.3 and 9.6] and Simpson [54, Remark 3.12]. Namely, if Q is recursively bounded Π_{1}^{0} and P ≤_{s} Q, then by Corollary 4.9 the recursive functional Φ : Q → P is given by truth tables, hence for each g ∈ Q there exists f = Φ(g) ∈ P such that f ≤_{tt} g, i.e., f is truth table reducible to g. Thus we see that P_{w} is analogous to R_{T}, the recursively enumerable Turing degrees, while P_{s} is more closely analogous to R_{tt}, the recursively enumerable truth table degrees.

Remark 5.6. It is known that the countable distributive lattices P_{w} and P_{s} are structurally rich. Binns/Simpson [3, 6] have shown that every countable distributive lattice is lattice embeddable in every nontrivial initial segment of P_{w}. A similar conjecture for P_{s} remains open, although partial results in this direction are known. Binns [3, 4] has obtained the P_{w} and P_{s} analogs of the Sacks Splitting Theorem. Namely, for all b > 0 in P_{w} there exist b_{1}, b_{2} < b in P_{w} such that sup (b_{1}, b_{2}) = b, and similarly for P_{s}. Cenzer/Hinman [9] have obtained the P_{s} analog of the Sacks Density Theorem. Namely, for all a < b in P_{s} there exists c in P_{s} such that a < c < b. A similar conjecture for P_{w} remains open. Binns [3, 4] has improved the result of Cenzer/Hinman [9] by showing that for all a < b in P_{s} there exist b_{1}, b_{2} < b in P_{s} such that a < inf (b_{1}, b_{2}) < sup (b_{1}, b_{2}) = b. These structural results for P_{w} and P_{s} are proved by means of priority arguments. They invite comparison with the older, known results for recursively enumerable Turing degrees, which were also proved by priority arguments.

6 Weak and strong completeness

In this section we obtain additional information concerning sets which are of weak or strong degree 1 in P_{w} or P_{s}, respectively. We show that, if P is a nonempty recursively bounded Π_{1}^{0} set, then deg_{w}(P) = 1 if and only if P is Turing degree isomorphic to PA, and deg_{s}(P) = 1 if and only if P is recursively homeomorphic to PA.

By Theorem 4.10 and Corollary 4.11, it suffices to consider Π_{1}^{0} subsets of 2^{ω}.

Definition 6.1. Let P be a nonempty recursively bounded Π_{1}^{0} set. P is weakly complete if deg_{w}(P) = 1, i.e., P ≥_{w} Q for all nonempty Π_{1}^{0} sets Q ⊆ 2^{ω}. P is strongly complete if deg_{s}(P) = 1, i.e., P ≥_{s} Q for all nonempty Π_{1}^{0} sets Q ⊆ 2^{ω}. These notions have sometimes been referred to as Muchnik completeness and Medvedev completeness, respectively.

Remark 6.2. We have seen in the proof of Theorem 5.3 that PA is strongly complete, hence weakly complete. In addition, there are natural examples of recursively bounded Π_{1}^{0} sets which are weakly complete but not strongly complete. See Definition 7.9 and Remark 7.10 below.

Theorem 6.3. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}.

1. If P and Q are strongly complete, then P is recursively homeomorphic to Q.

2. If P is strongly complete, then we can find a recursive functional Φ : P → Q which is onto Q, i.e., Q = {Φ(f) | f ∈ P }.

3. P is strongly complete if and only if P is productive, i.e., given an index of a nonempty Π_{1}^{0} set P′ ⊆ P we can effectively find a canonically indexed clopen set U ⊆ 2^{ω} such that both P′ ∩ U and P′ \ U are nonempty.

Proof. See Simpson [54, Section 3].

Corollary 6.4. Let P be a nonempty recursively bounded Π_{1}^{0} set. If P is strongly complete, then the set of Turing degrees of members of P is upward closed.

Proof. For any P, the set of Turing degrees of members of P × 2^{ω} is obviously upward closed. Now assume that P is strongly complete. Then clearly P × 2^{ω} is strongly complete. Hence, by Theorem 4.10 and part 1 of Theorem 6.3, P and P × 2^{ω} are recursively homeomorphic to each other. Since the set of Turing degrees of members of P × 2^{ω} is upward closed, it follows that the set of Turing degrees of members of P is upward closed.

Corollary 6.5. Let P be a nonempty recursively bounded Π_{1}^{0} set. Then P is strongly complete if and only if P is recursively homeomorphic to PA.

Proof. Recall that PA is the set of completions of Peano Arithmetic. By the Gödel/Rosser Theorem for Peano Arithmetic, PA is productive. Hence, by part 3 of Theorem 6.3, PA is strongly complete. Our corollary now follows by Theorem 4.10 and part 1 of Theorem 6.3.

The next corollary is originally due to Robert M. Solovay.

Corollary 6.6. The set of Turing degrees of members of PA is upward closed.

Proof. This is immediate from Corollaries 6.4 and 6.5.

Remark 6.7. Instead of Peano Arithmetic, we could have used any consistent recursively axiomatizable theory T which is effectively essentially incomplete, i.e., has the property given by the Gödel/Rosser Theorem. The required property of T is as follows. Given a consistent recursively axiomatizable theory T′ extending T, we can effectively find a sentence φ in the language of T which is independent of T′, i.e., T′ ⊬ φ and T′ ⊬ ¬ φ. Compare this with our notion of productivity from part 3 of Theorem 6.3, which may be viewed as an abstract Gödel/Rosser property for Π_{1}^{0} subsets of 2^{ω}.

Theorem 6.8. Let P be a nonempty recursively bounded Π_{1}^{0} set. Then P is weakly complete if and only if P is Turing degree isomorphic to PA.

Proof. By Corollary 6.5, PA is strongly complete. (This is the only property of PA which we shall need.) Hence PA is weakly complete, so any P which is Turing degree isomorphic to PA is weakly complete. For the converse, let P be a nonempty Π_{1}^{0} subset of 2^{ω} which is weakly complete. In particular PA ≤_{w} P. It follows by Corollary 6.6 that the Turing degrees of members of P are included in the Turing degrees of members of PA.

In order to finish the proof of Theorem 6.8, we need the following lemma, which exposes an interesting relationship between weak reducibility and strong reducibility.

Lemma 6.9. Let P and Q be nonempty recursively bounded Π_{1}^{0} sets. If P ≤_{w} Q, then we can find a nonempty Π_{1}^{0} set \overline{Q} ⊆ Q such that P ≤_{s} \overline{Q}.

Proof. By the Almost Recursive Basis Theorem 4.19, let g ∈ Q be almost recursive. Since P ≤_{w} Q, let f ∈ P be such that f ≤_{T} g. By Theorem 4.18 we can find a total recursive functional Φ : ω^{ω} → ω^{ω} such that f = Φ(g). Put \overline{Q} = \{\overline{g} ∈ Q | Φ(\overline{g}) ∈ P \}. By Theorem 4.4 we have that \overline{Q} is a Π_{1}^{0} subset of Q. Since f = Φ(g) ∈ P, we have g ∈ \overline{Q}, hence \overline{Q} is nonempty. Putting \overline{Φ} = the restriction of Φ to \overline{Q}, we have \overline{Φ} : \overline{Q} → P, so P ≤_{s} \overline{Q}.

Now, since our P is ≥_{w} PA, apply Lemma 6.9 to get a nonempty Π_{1}^{0} set \overline{P} ⊆ P such that \overline{P} ≥_{s} PA. Since PA is strongly complete, \overline{P} is strongly complete. Hence, by Theorem 4.10 and part 1 of Theorem 6.3, \overline{P} is recursively homeomorphic to PA. It follows that \overline{P} is Turing degree isomorphic to PA. We now have \{deg_{T} (f) | f ∈ P \} ⊆ \{deg_{T} (f) | f ∈ PA\} = \{deg_{T} (f) | f ∈ \overline{P} \} ⊆ {deg_{T} (f) | f ∈ P }, so P is Turing degree isomorphic to PA. This completes the proof of Theorem 6.8.

Corollary 6.10. Let P and Q be nonempty recursively bounded Π_{1}^{0} sets. If P and Q are weakly complete, then P is Turing degree isomorphic to Q.

Proof. By Theorem 6.8, P and Q are Turing degree isomorphic to PA, hence to each other.

We can now strengthen Corollary 6.4 as follows.

Corollary 6.11. Let P be a nonempty recursively bounded Π_{1}^{0} set. If P is weakly complete, then the set of Turing degrees of members of P is upward closed.

Proof. This is immediate from Corollary 6.6 and Theorem 6.8.

7 Π_{1}^{0} sets of positive measure

Definition 7.1. The fair coin probability measure on 2^{ω} is defined by

μ(\{f ∈ 2^{ω} | f(n) = m\}) = \frac{1}{2}

for all m ∈ {0, 1} and n ∈ ω. A set P ⊆ 2^{ω} is said to be of positive measure if μ(P) > 0.

In this section we prove a “non-helping” theorem for weak and strong degrees of subsets of 2^{ω} which are of positive measure.

Lemma 7.2. Let F_{n}, n ∈ ω be a sequence of finite subsets of ω of bounded cardinality. Put

S = ∏_{n∈ω} F_{n} = {f ∈ ω^{ω} | ∀n (f(n) ∈ F_{n})} ⊆ ω^{ω}.

Let P ⊆ 2^{ω} be of positive measure. Let Q ⊆ ω^{ω} be arbitrary. If S ≤_{s} P × Q, then S ≤_{s} Q.

Proof. We generalize an argument of Jockusch/Soare [26, Theorem 5.3]. Let k ≥ 2 be such that, for all n, F_{n} is of cardinality < k. Our hypothesis concerning P is that μ(P) > 0. By measure theory, let V ⊇ P be an open set in 2^{ω} such that μ(V \P) < μ(P)/4k. Let U ⊆ V be a clopen set such that μ(V \U) < μ(P)/4k. It follows that μ(U \P) < μ(U)/k. Note that μ(U) is a positive rational number. Since S ≤_{s} P × Q, let Φ be a recursive functional such that Φ(f ⊕ g) ∈ S for all f ∈ P and g ∈ Q. Given g ∈ Q and n ∈ ω, we can effectively find m = Ψ(g)(n) ∈ ω such that μ({f ∈ U | Φ(f ⊕ g)(n) = m}) > μ(U)/k. It follows that m ∈ F_{n}. Thus Ψ is a recursive functional, and Ψ(g) ∈ S for all g ∈ Q. Hence S ≤_{s} Q.

Lemma 7.3. Same as Lemma 7.2 with strong reducibility, ≤_{s}, replaced by weak reducibility, ≤_{w}.

Proof. Assume S ≤_{w} P × Q. Fix g ∈ Q. We have S ≤_{w} P × {g}. By countable additivity of μ, since there are only countably many recursive functionals, there exists P_{g} ⊆ P such that μ(P_{g}) > 0 and S ≤_{s} P_{g} × {g}. By Lemma 7.2 it follows that S ≤_{s} {g}. This implies S ≤_{w} Q, since g ∈ Q is arbitrary.

Definition 7.4. For A, B ⊆ ω we say that f ∈ 2^{ω} separates A, B if f(n) = 1 for all n ∈ A, and f(n) = 0 for all n ∈ B. A nonempty Π_{1}^{0} set S ⊆ 2^{ω} is said to be separating if there exist recursively enumerable sets A, B ⊆ ω such that S = {f ∈ 2^{ω} | f separates A, B}. In this case we say that the weak degree deg_{w}(S) and the strong degree deg_{s}(S) are separating.

Theorem 7.5. Let S, P, Q be Π_{1}^{0} subsets of 2^{ω}. Assume that S is separating and that P is of positive measure. Let s, p, q ∈ P_{w} be the weak degrees of S, P, Q respectively. If s ≤ sup (p, q), then s ≤ q. The same holds for strong degrees.

Proof. It suffices to note that S is of the form required by Lemmas 7.2 and 7.3. Namely, S = ∏_{n∈ω} F_{n} where F_{n} = {1} if n ∈ A, {0} if n ∈ B, {0, 1} otherwise.

Corollary 7.6. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. Assume that P is of positive measure. Let p, q ∈ P_{w} be the weak degrees of P, Q respectively. If q < 1, then sup (p, q) < 1. The same holds for strong degrees.

Proof. By Theorem 7.5, it suffices to note that 1 is separating. Namely, 1 is the weak or strong degree of the Π_{1}^{0} set S = {f ∈ 2^{ω} | f separates A, B} where A = {n | {n}(n) = 0} and B = {n | {n}(n) = 1}. Or, we could take A and B to be the set of Gödel numbers of provable and refutable sentences of Peano Arithmetic. See also Jockusch/Soare [26] and Simpson [54, Section 3].

Corollary 7.7. Let P be a Π_{1}^{0} subset of 2^{ω} of positive measure. Let p ∈ P_{w} be the weak degree of P. Then p < 1. The same holds for strong degrees.

Proof. This follows from Corollary 7.6 by setting q = 0.

Remark 7.8. In [48] we shall give an example of a Π_{1}^{0} set Q ⊆ 2^{ω} whose Turing upward closure Q̂ = {f ∈ 2^{ω} | (∃g ≤_{T} f) (g ∈ Q)} is of positive measure yet does not contain any Π_{1}^{0} set of positive measure.

Definition 7.9. Following Jockusch [25], for k ≥ 2 we define

DNR_{k} = {f ∈ ω^{ω} | ∀n (f(n) < k and f(n) ≠ {n}(n))}.

Thus DNR_{k} is the set of k-bounded, diagonally nonrecursive functions. Note that DNR_{k} is recursively bounded and Π_{1}^{0}.

Remark 7.10. By Jockusch [25, Theorem 5] each DNR_{k} is weakly complete, i.e., of weak degree 1. Let d_{k}^{∗} ∈ P_{s} be the strong degree of DNR_{k}. It is well known (see also the proof of Corollary 7.6 above) that DNR_{2} is strongly complete, i.e., d_{2}^{∗} = 1 in P_{s}. By Jockusch [25, Theorem 6] we have

1 = d_{2}^{∗} > d_{3}^{∗} > ⋯ > d_{k}^{∗} > d_{k+1}^{∗} > ⋯

in P_{s}. See also Simpson [54, Remark 3.21].

We have the following new result.

Corollary 7.11. Let P and Q be Π_{1}^{0} subsets of 2^{ω}. Assume that P is of positive measure. Let p, q ∈ P_{s} be the strong degrees of P, Q respectively. For each k ≥ 2, if d_{k}^{∗} ≤ sup (p, q), then d_{k}^{∗} ≤ q. In particular we have

1 = sup (p, d_{2}^{∗}) > sup (p, d_{3}^{∗}) > ⋯ > sup (p, d_{k}^{∗}) > sup (p, d_{k+1}^{∗}) > · · ·.

Proof. It suffices to note that DNR_{k} is of the form required by Lemma 7.2. Namely, DNR_{k} = ∏_{n∈ω} F_{n} where F_{n} = {m < k | {n}(n) ≠ m}.

Remark 7.12. In Corollary 7.11, we do not know whether it is necessarily the case that d_{3}^{∗} ≥ p, or d_{k}^{∗} ≥ p for all k ≥ 3.

8 Π_{1}^{0} sets of random reals

In this section we exhibit a particular degree r ∈ P_{w} and note some of its degree-theoretic properties.

As in Section 7, let μ denote the fair coin probability measure on 2^{ω}.

Definition 8.1. An effective null G_{δ} is a set S ⊆ 2^{ω} of the form S = ⋂_{n∈ω} U_{n} where {U_{n}}_{n∈ω} is a recursive sequence of Σ_{1}^{0} subsets of 2^{ω} with μ(U_{n}) ≤ 1/2^{n} for all n. A point f ∈ 2^{ω} is said to be random if f ∉ S for all effective null G_{δ} sets S ⊆ 2^{ω}.

Remark 8.2. The notion of randomness in Definition 8.1 is due to Martin-Löf [39] and has been studied extensively. It appears to be the most general and natural notion of algorithmic randomness for infinite sequences of 0’s and 1’s. It has also been called Martin-Löf randomness (Li/Vitányi [37, Section 2.5]), 1-randomness (Kurtz [28], Kautz [27]), and the NAP property (Kučera [29, 30, 31, 32, 33, 34, 35]). It is closely related to Kolmogorov complexity (see Li/Vitányi [37]).

The following theorem is well known. It says that the union of all effective null G_{δ} sets is an effective null G_{δ} set.

Theorem 8.3. {f ∈ 2^{ω} | f is not random} is an effective null G_{δ} set.

Proof. This result is essentially due to Martin-Löf [39]. See also Kučera [29, Theorems 1 and 2]. For the sake of completeness, we present the proof here. For each e ∈ ω define a Σ_{1}^{0} set V_{e} ⊆ 2^{ω} as follows. Compute {e}(e). If {e}(e) is undefined, V_{e} = the empty set. If {e}(e) = m, let V_{e} = the Σ_{1}^{0} subset of 2^{ω} with Σ_{1}^{0} index m enumerated so long as its measure is ≤ 1/2^{e}. Put R = ⋃_{k=0}^{∞} R_{k} where R_{k} = 2^{ω} \ ⋃_{e=k+1}^{∞} V_{e}. We have

μ(2^{ω} \ R_{k}) ≤ ∑_{e=k+1}^{∞} μ(V_{e}) ≤ ∑_{e=k+1}^{∞} \frac{1}{2^{e}} = \frac{1}{2^{k}}

and R_{k} is uniformly Π_{1}^{0}. Thus 2^{ω} \ R = ⋂_{k=0}^{∞}(2^{ω} \ R_{k}) is an effective null G_{δ} set. Hence every random f ∈ 2^{ω} belongs to R. We claim that, conversely, every f ∈ R is random. To see this, consider an effective null G_{δ} set S = ⋂_{n=0}^{∞} U_{n}, where μ(U_{n}) ≤ 1/2^{n}. It suffices to show that R ∩ S = ∅. Given k ∈ ω, let e ≥ k + 1 be such that, for all n, {e}(n) is a Σ_{1}^{0} index of U_{n}. In particular, {e}(e) is a Σ_{1}^{0} index of U_{e}. Since μ(U_{e}) ≤ 1/2^{e}, it follows that V_{e} = U_{e}. Since R_{k} is disjoint from V_{e}, it follows that R_{k} is disjoint from S. But k is arbitrary, so R is disjoint from S. This completes the proof that R = {f ∈ 2^{ω} | f is random}.

Corollary 8.4. There exists a nonempty Π_{1}^{0} set

P ⊆ R = {f ∈ 2^{ω} | f is random}.

Proof. Trivially any effective null G_{δ} set is Π_{2}^{0}. In particular, by Theorem 8.3, R is Σ_{2}^{0}. Hence R is a union of Π_{1}^{0} sets. Let P be any one of these Π_{1}^{0} sets. Alternatively, we could let P be any one of the sets R_{k} as in the proof of Theorem 8.3. Each of these sets is Π_{1}^{0}.

Notation 8.5. We use the following notation for shifts: f^{(k)}(n) = f(k + n). Note that f ↦ f^{(k)} is a mapping of 2^{ω} into 2^{ω}.

Lemma 8.6. For all f ∈ 2^{ω} and k ∈ ω, f is random if and only if f^{(k)} is random.

Proof. The proof is straightforward.

The next lemma is an effective version of the Zero-One Law of probability theory.

Lemma 8.7. Let f be random. Let P ⊆ 2^{ω} be Π_{1}^{0} with μ(P) > 0. Then ∃k (f^{(k)} ∈ P).

Proof. This is due to Kučera [29]. For completeness we present the proof here. Let P be the set of paths through T, where T ⊆ 2^{<ω} is a recursive tree. Put

T̃ = {σ^{⌢}⟨i⟩ | σ ∈ T, i ∈ {0, 1}, σ^{⌢}⟨i⟩ ∉ T }.

For n ≥ 1, put

T^{n} = {τ_{1}^{⌢} ⋯^{⌢}τ_{m}^{⌢}σ | m < n, τ_{1}, …, τ_{m} ∈ T̃, σ ∈ T },

and let P^{n} = [T^{n}], the set of paths through T^{n}. We have

μ(P^{n}) = 1 − (1 − μ(P))^{n},

hence 2^{ω} \ ⋃_{n=1}^{∞} P^{n} is an effective null G_{δ} set. Hence f ∈ P^{n} for some n. Hence for some m < n and τ_{1}, …, τ_{m} ∈ T̃ we have f = τ_{1}^{⌢} ⋯^{⌢}τ_{m}^{⌢}g where g ∈ P. Putting k = length of τ_{1}^{⌢} ⋯^{⌢}τ_{m}, we have g = f^{(k)}.

Lemma 8.8. Let f ∈ 2^{ω} be random. Then for all Π_{1}^{0} sets P ⊆ 2^{ω}, if f ∈ P then μ(P) > 0.

Proof. Since P is Π_{1}^{0}, let P = ⋂_{s} P_{s} where P_{s}, s ∈ ω, is a recursive sequence of canonically indexed clopen sets in 2^{ω} with

P_{0} ⊇ P_{1} ⊇ ⋯ ⊇ P_{s} ⊇ P_{s+1} ⊇ · · · .

Assume μ(P) = 0. By countable additivity, lim_{s} μ(P_{s}) = 0. Define a recursive function h : ω → ω by h(n) = least s such that μ(P_{s}) ≤ 1/2^{n}. Putting U_{n} = P_{h(n)}, we see that P = ⋂_{n} U_{n} is an effective null G_{δ} set. Hence f ∉ P, a contradiction.

Lemma 8.9. Let P and R be as in Corollary 8.4. Then μ(P) > 0, and P ≡_{w} R.

Proof. By Lemma 8.8 μ(P) > 0, and by Lemma 8.7 (∀f ∈ R) ∃k (f^{(k)} ∈ P). Thus P ≤_{w} R. On the other hand, since P ⊆ R, P ≥_{w} R, so P ≡_{w} R.

Theorem 8.10. Let r = deg_{w}(R) where R = {f ∈ 2^{ω} | f is random}. Then r can be characterized as the unique largest weak degree of a Π_{1}^{0} set P ⊆ 2^{ω} such that μ(P) > 0.

Proof. By Lemma 8.7 we have that, for any Π_{1}^{0} set P ⊆ 2^{ω} with μ(P) > 0, P ≤_{w} R. By Corollary 8.4 let P′ be a nonempty Π_{1}^{0} subset of R. By Lemma 8.9 we have μ(P′) > 0 and P′ ≡_{w} R. This completes the proof.

Remark 8.11. Theorem 8.10 tells us that, among all weak degrees of Π_{1}^{0} sets of positive measure, there exists a unique largest degree. Simpson/Slaman [55] and independently Terwijn [58] have shown that, among all strong degrees of Π_{1}^{0} sets of positive measure, there is no largest or even maximal degree.

We end this section by noting some additional properties of the particular weak degree r which was defined in Theorem 8.10.

Theorem 8.12. Let r be the weak degree of R = {f ∈ 2^{ω} | f is random}. Then:

1. r ∈ P_{w}, and 0 < r < 1.

2. For all q ∈ P_{w}, if q < 1 then sup (q, r) < 1.

3. For all q_{1}, q_{2} ∈ P_{w}, if r ≥ inf (q_{1}, q_{2}) then either r ≥ q_{1} or r ≥ q_{2}.

4. There is no separating s ∈ P_{w} such that 0 < s ≤ r.

Proof. Since R has no recursive members, r > 0. Theorem 8.10 implies that r ∈ P_{w} and contains a Π_{1}^{0} subset of 2^{ω} of positive measure. By Corollary 7.7 it follows that r < 1, completing the proof of part 1 of the theorem. Corollary 7.6 gives part 2. To prove part 3, let Q_{1}, Q_{2} be Π_{1}^{0} subsets of 2^{ω} of weak degree q_{1}, q_{2} respectively. We are assuming that R ≥_{w} Q_{1} ∪Q_{2}. By Corollary 8.4 let P be a nonempty Π_{1}^{0} subset of R. Then P ≥_{w} Q_{1} ∪Q_{2}. By Lemma 6.9 we can find a nonempty Π_{1}^{0} set \overline{P} ⊆ P such that \overline{P} ≥_{s} Q_{1} ∪ Q_{2}. Thus there is a recursive functional Φ : \overline{P} → Q_{1} ∪ Q_{2}. Put \overline{P}_{1} = \overline{P} ∩ Φ^{−1}(Q_{1}) and \overline{P}_{2} = \overline{P} ∩ Φ^{−1}(Q_{2}). We have \overline{P} = \overline{P}_{1} ∪ \overline{P}_{2}, hence at least one of \overline{P}_{1} and \overline{P}_{2} is nonempty, say \overline{P}_{1}. Then \overline{P}_{1} ≥_{s} Q_{1}. Note also that \overline{P}_{1} is a Π_{1}^{0} subset of R, hence by Lemma 8.9 we have \overline{P}_{1} ≡_{w} R. It follows that R ≥_{w} Q_{1}, and this proves part 3. Part 4 is a consequence of Theorem 7.5.

Corollary 8.13. The weak degree r ∈ P_{w} is meet irreducible and does not join to 1 in P_{w}.

Proof. This follows from parts 1, 2 and 3 of Theorem 8.12.

9 Thin Π_{1}^{0} subsets of 2^{ω}

In this section we discuss an interesting class of degrees in P_{w}, each of which is incomparable with the particular degree r ∈ P_{w} of Section 8.

We begin with some generalities concerning thin Π_{1}^{0} sets.

Definition 9.1. A Π_{1}^{0} set Q ⊆ ω^{ω} is said to be thin if, for all Π_{1}^{0} sets Q′ ⊆ Q, the set-theoretic difference Q \ Q′ is Π_{1}^{0}.

Lemma 9.2. Let Q be a recursively bounded Π_{1}^{0} set. Then Q is thin if and only if all Π_{1}^{0} subsets of Q are trivial, i.e., they are of the form

Q′ = {g ∈ Q | σ_{1} ⊂ g or ⋯ or σ_{k} ⊂ g}

for some finite set of strings σ_{1}, …, σ_{k}.

Proof. If Q is any Π_{1}^{0} set, and if Q′ ⊆ Q is trivial, then clearly Q′ and Q\Q′ are Π_{1}^{0}. It remains to prove that if Q is a recursively bounded Π_{1}^{0} set, and if Q′ ⊆ Q is such that Q′ and Q\Q′ are Π_{1}^{0}, then Q′ is trivial. To see this, let h be a recursive function such that ∀n (∀g ∈ Q) (g(n) < h(n)). As in the proof of Theorem 4.7, note that Q is a closed set in the compact space Q_{h} = {g | ∀n (g(n) < h(n))}. By Theorem 4.3, since Q′ and Q \ Q′ are Π_{1}^{0}, let T′ and T′′ be recursive trees such that Q′ = [T′] and Q \ Q′ = [T′′]. Then Q_{h} is covered by clopen sets of the form {g | τ ⊂ g} where either τ ∉ T′ or τ ∉ T′′. Let τ_{1}, …, τ_{l} be a finite subcovering. Let σ_{1}, …, σ_{k} consist of those τ_{i}, 1 ≤ i ≤ l, such that τ_{i} ∉ T′′. Then Q′ = {g ∈ Q | σ_{1} ⊂ g or ⋯ or σ_{k} ⊂ g}, so Q′ is trivial.

Theorem 9.3. Let Q be a nonempty thin recursively bounded Π_{1}^{0} set. Then f ∈ Q is isolated if and only if f is recursive. In particular, Q is perfect if and only if and only if Q has no recursive members, i.e., deg_{w}(Q) > 0.

Proof. If f ∈ Q is isolated, then f is recursive by Theorem 4.15. Conversely, suppose f ∈ Q is recursive. Then the singleton set {f} is a Π_{1}^{0} subset of Q. Since Q is thin and recursively bounded Π_{1}^{0}, by Lemma 9.2 there is a finite set of strings σ_{1}, …, σ_{k} such that f is the unique g ∈ Q such that σ_{1} ⊂ g or ⋯ or σ_{k} ⊂ g. It follows that f is isolated. This proves the first part of the theorem. The second part follows immediately.

Lemma 9.4. Let Q be a thin recursively bounded Π_{1}^{0} set. Then:

1. Every Π_{1}^{0} subset of Q is thin and recursively bounded.

2. Let P = {Φ(g) | g ∈ Q} be the image of Q under a recursive functional Φ : Q → ω^{ω}. Then P is a thin recursively bounded Π_{1}^{0} set.

Proof. Part 1 is straightforward. For part 2, note first that, since Q is recursively bounded and Π_{1}^{0}, so is P, by Theorem 4.7. It remains to show that P is thin. Given a Π_{1}^{0} set P′ ⊆ P, let Q′ = {g ∈ Q | Φ(g) ∈ P′} be the preimage of P′. By Theorem 4.4, Q′ is Π_{1}^{0}. Since Q is thin, Q \ Q′ is also Π_{1}^{0}. It follows by Theorem 4.7 that P \ P′ = {Φ(g) | g ∈ Q \ Q′} is Π_{1}^{0}. Since P′ is an arbitrary Π_{1}^{0} subset of P, we see that P is thin.

Theorem 9.5. If Q is a thin recursively bounded Π_{1}^{0} set, then Q is recursively homeomorphic to a thin Π_{1}^{0} set Q^{∗} ⊆ 2^{ω}. Moreover, Q is perfect if and only if Q^{∗} is perfect.

Proof. This follows from Theorems 4.10 and 9.3 and part 2 of Lemma 9.4.

Remark 9.6. There is a large literature on thin perfect Π_{1}^{0} subsets of 2^{ω} going back to Martin/Pour-El [38]. See Downey/Jockusch/Stob [15, 16] and Cholak et al [11]. Typically, thin perfect Π_{1}^{0} subsets of 2^{ω} are constructed by means of priority arguments. In this sense, thin perfect Π_{1}^{0} subsets of 2^{ω} and their weak and strong degrees are artificial or unnatural. In particular, thin perfect Π_{1}^{0} subsets of 2^{ω} have been used by Binns/Simpson [6] to embed countable distributive lattices into P_{w} and P_{s}.

Remark 9.7. Let q = deg_{w}(Q) where Q is any nonempty thin perfect recursively bounded Π_{1}^{0} set. Obviously q ∈ P_{w}. Let r = deg_{w}(R) where R = {f ∈ 2^{ω} | f is random}. We have seen in Theorem 8.10 that r ∈ P_{w}. Our goal in this section is to prove Theorem 9.15, which says that q and r are incomparable, i.e., q ≰ r and r ≰ q. By Theorem 9.5, it suffices to prove this in the special case when Q is a nonempty thin perfect Π_{1}^{0} subset of 2^{ω}.

Lemma 9.8. Let Q be a thin Π_{1}^{0} subset of 2^{ω}. Then μ(Q) = 0.

Proof. For f, g ∈ 2^{ω} we write f <_{lex} g to mean that there exists j such that (∀i < j) (f(i) = g(i)) and f(j) < g(j). Note that <_{lex} is a linear ordering of 2^{ω}, the lexicographical ordering. For σ, τ ∈ 2^{<ω} we write σ <_{lex} τ to mean that there exists j < min(lh(σ), lh(τ)) such that (∀i < j) (σ(i) = τ(i)) and σ(j) < τ(j). Note that, for each n ∈ ω, the restriction of <_{lex} to strings of length n is a linear ordering, the lexicographical ordering.

Let Q be a thin Π_{1}^{0} subset of 2^{ω}. Assume for a contradiction that μ(Q) > 0. Fix p ∈ ω such that μ(Q) > 1/2^{p}. Put T = Ext(Q) = {τ ∈ 2^{<ω} | (∃g ∈ Q) (τ ⊂ g)}, the set of extendible nodes of Q. By Lemma 4.13 T is a Π_{1}^{0} tree, and Q = [T]. Define inductively a sequence of strings τ_{n} ∈ T, n ∈ ω, as follows: τ_{n} = the lexicographically least τ ∈ T of length p + n + 1 such that τ >_{lex} τ_{m} for all m < n. The existence of τ_{n} is assured by the fact that {g ∈ Q | τ_{0} ⊂ g or ⋯ or τ_{n−1} ⊂ g} is a lexicographically initial segment of Q of measure

∑_{m=0}^{n−1} μ(\{g ∈ Q | τ_{m} ⊂ g\}) ≤ ∑_{m=0}^{n−1} \frac{1}{2^{p+m+1}} < \frac{1}{2^{p}} < μ(Q).

Put Q′ = {g ∈ Q | ¬ ∃n (τ_{n} ⊂ g)}. Thus Q′ is a lexicographically final segment of Q. Moreover Q \ Q′ = {g ∈ Q | ∃n (τ_{n} ⊂ g)} is clearly not compact, hence not of the form {g ∈ Q | σ_{1} ⊂ g or ⋯ or σ_{k} ⊂ g} where σ_{1}, …, σ_{k} is a finite set of strings. It follows that Q′ is also not of this form. In the next paragraph we shall show that Q′ is a Π_{1}^{0} subset of Q. Hence Q is not thin, so our lemma will be proved.

It remains to show that Q′ is Π_{1}^{0}. Since T is Π_{1}^{0}, let T^{s}, s ∈ ω be a recursive sequence of recursive trees such that

T^{0} ⊇ T^{1} ⊇ ⋯ ⊇ T^{s} ⊇ T^{s+1} ⊇ ⋯

and ⋂_{s=0}^{∞} T^{s} = T. For each s define inductively τ_{n}^{s} = the lexicographically least τ ∈ T^{s} of length p + n + 1 such that τ >_{lex} τ_{m}^{s} for all m < n. The double sequence τ_{n}^{s}, n, s ∈ ω is recursive, and for each n we have

τ_{n}^{0} ≤_{lex} τ_{n}^{1} ≤_{lex} ⋯ ≤_{lex} τ_{n}^{s} ≤_{lex} τ_{n}^{s+1} ≤_{lex} ⋯

and τ_{n} = lim_{s} τ_{n}^{s}. Since Q′ is a lexicographically final segment of Q = [T], it follows that

Q′ = {g ∈ Q | ¬ ∃n (τ_{n} ⊂ g)} = {g ∈ Q | ¬ ∃s ∃n (τ_{n}^{s} ⊂ g)}.

Thus Q′ is Π_{1}^{0}, and our lemma is proved.

Remark 9.9. We do not know the answer to the following question. If Q is a thin perfect Π_{1}^{0} subset of 2^{ω}, does it follow that the Turing upward closure Q̂ = {f ∈ 2^{ω} | (∃g ≤_{T} f) (g ∈ Q)} is of measure 0?

Lemma 9.10. Let Q be a nonempty thin Π_{1}^{0} subset of 2^{ω}. If f is random, and if g ∈ Q is almost recursive, then f ≰_{T} g. In particular, R ≰_{w} Q.

Proof. Assume for a contradiction that f ∈ R and f ≤_{T} g. Since g is almost recursive, by Theorem 4.18 we have f ≤_{tt} g, i.e., f = Φ(g) where Φ : 2^{ω} → 2^{ω} is a total recursive functional. Since R is Σ_{2}^{0}, let P be a Π_{1}^{0} subset of R such that f ∈ P. Put \overline{Q} = \{\overline{g} ∈ Q | Φ(\overline{g}) ∈ P \}. Then \overline{Q} is a Π_{1}^{0} subset of Q. By part 1 of Lemma 9.4, \overline{Q} is thin. Note also that g ∈ \overline{Q}, since Φ(g) = f ∈ P. Put \overline{P} = \{Φ(\overline{g}) | \overline{g} ∈ \overline{Q}\}. Clearly \overline{P} ⊆ P ⊆ R, and by Theorem 4.7 we have that \overline{P} is Π_{1}^{0}. Moreover f = Φ(g) ∈ \overline{P}, so \overline{P} is nonempty, so by Lemma 8.8 we have μ(\overline{P}) > 0. On the other hand, by part 2 of Lemma 9.4, \overline{P} is thin, hence by Lemma 9.8 we have μ(\overline{P}) = 0. This contradiction proves the first part of our lemma. For the second part, since Q is nonempty, the Almost Recursive Basis Theorem 4.19 gives g ∈ Q such that g is almost recursive. By the first part of the lemma, f ≰_{T} g for all f ∈ R. It follows that R ≰_{w} Q.

Lemma 9.11. Let f ∈ 2^{ω} be random. If g ≤_{tt} f is nonrecursive, then there exists \overline{f} ∈ 2^{ω} such that \overline{f} ≡_{T} g and \overline{f} is random.

Proof. This lemma has been stated by Demuth [14, Lemma 30]. The proof is in Kautz’s thesis [27, Theorem IV.3.16].

Lemma 9.12. Let f ∈ 2^{ω} be random and almost recursive. If g ≤_{T} f is nonrecursive, then there exists \overline{f} ∈ 2^{ω} such that \overline{f} ≡_{T} g and \overline{f} is random.

Proof. This follows from Lemma 9.11 because, by Theorem 4.18, if f is almost recursive then g ≤_{T} f implies g ≤_{tt} f.

Lemma 9.13. Let Q be a nonempty thin perfect Π_{1}^{0} subset of 2^{ω}. If g ∈ Q, and if f ∈ 2^{ω} is random and almost recursive, then g ≰_{T} f. In particular Q ≰_{w} R, and Q ≰_{w} P for all Π_{1}^{0} sets P ⊆ 2^{ω} of positive measure.

Proof. Assume for a contradiction that g ∈ Q and g ≤_{T} f. Since f is almost recursive, g is almost recursive. Since f is random and almost recursive, Lemma 9.12 gives us \overline{f} ≡_{T} g such that \overline{f} is random. This contradicts Lemma 9.10. The first part of our lemma is now proved. For the second part, let P ⊆ 2^{ω} be Π_{1}^{0} of positive measure. Since R is Σ_{2}^{0} of measure 1, we can find a Π_{1}^{0} set P′ ⊆ P ∩ R which is of positive measure. By the Almost Recursive Basis Theorem 4.19, let f ∈ P′ be almost recursive. By the first part of our lemma, we have g ≰_{T} f for all g ∈ Q. Thus Q ≰_{w} P′. It follows that Q ≰_{w} P and Q ≰_{w} R.

Summarizing, we have:

Lemma 9.14. Let f, g ∈ 2^{ω} be almost recursive. Assume that f is random, and assume that g ∈ Q where Q is a thin perfect Π_{1}^{0} subset of 2^{ω}. Then f ≰_{T} g and g ≰_{T} f, i.e., the Turing degrees of f and g are incomparable.

Proof. This is immediate from Lemmas 9.10 and 9.13.

Theorem 9.15. Let q = deg_{w}(Q) where Q is a nonempty thin perfect Π_{1}^{0} subset of 2^{ω}. Let r = deg_{w}(R) where R = {f ∈ 2^{ω} | f is random}. Then q and r are incomparable weak degrees in P_{w}.

Proof. Obviously q ∈ P_{w}. Theorem 8.10 implies that r ∈ P_{w}. By Lemma 9.10 we have r ≰ q. By Lemma 9.13 we have q ≰ r.

Corollary 9.16. There exist 0 < q < q^{∗} in P_{w} such that q is separating and q^{∗} is not separating. Indeed, every separating s ∈ P_{w} which is ≤ q^{∗} is ≤ q.

Proof. By Martin/Pour-El [38] let Q ⊆ 2^{ω} be a thin perfect Π_{1}^{0} set which is separating. Put q = deg_{w}(Q) and q^{∗} = sup(q, r). By Theorem 9.15 we have q < q^{∗}. If s were separating and ≤ q^{∗} but not ≤ q, then this would contradict Theorem 7.5.

10 Some additional natural examples in P_{w}

In this section we present some additional natural examples in P_{w}, including a hierarchy of weak degrees in P_{w} corresponding to the transfinite Ackermann hierarchy from proof theory.

Definition 10.1. Put DNR = {f ∈ ω^{ω} | ∀n (f(n) ≠ {n}(n))}, the set of diagonally nonrecursive functions. The set of Turing degrees of members of DNR has been studied by Jockusch [25]. Note that DNR is nonempty and Π_{1}^{0}. If h : ω → ω is a recursive function such that h(n) ≥ 2 for all n, put DNR_{h} = {f ∈ DNR | ∀n (f(n) < h(n))}, the set of h-bounded DNR functions. In addition, put DNR_{REC} = ⋃{DNR_{h} | h is recursive}, the set of recursively bounded DNR functions.

Remark 10.2. Trivially

DNR ⊃ DNR_{REC} ⊃ DNR_{h},

hence DNR ≤_{s} DNR_{REC} ≤_{s} DNR_{h}, hence DNR ≤_{w} DNR_{REC} ≤_{w} DNR_{h}. According to Ambos-Spies et al [2, Theorems 1.8 and 1.9], we have strict inequalities

DNR <_{w} DNR_{REC} <_{w} DNR_{h}.

As in Section 8, let R be the set of random reals. An argument of Kurtz (see Jockusch [25, Proposition 3]) shows that DNR_{h} ≤_{w} R provided h is such that ∑_{n=0}^{∞} 1/h(n) < ∞, for example h(n) = max(n^{2}, 2).

Remark 10.3. Since DNR_{h} is nonempty, recursively bounded, and Π_{1}^{0}, we have deg_{s}(DNR_{h}) ∈ P_{s} and deg_{w}(DNR_{h}) ∈ P_{w}. Although DNR and DNR_{REC} are not recursively bounded, it will be shown in Simpson [48] that deg_{w}(DNR) ∈ P_{w} and deg_{w}(DNR_{REC}) ∈ P_{w}. We do not know whether deg_{s}(DNR) ∈ P_{s}, or whether deg_{s}(DNR_{REC}) ∈ P_{s}. Put d = deg_{w}(DNR), d_{REC} = deg_{w}(DNR_{REC}), d_{h} = deg_{w}(DNR_{h}), r = deg_{w}(R). Summarizing, we have the following result.

Theorem 10.4. In P_{w} we have

0 < d < d_{REC} < d_{h} < r < 1

for all sufficiently fast-growing recursive functions h : ω → ω.

Proof. This follows from part 1 of Theorem 8.12 plus the results of Ambos-Spies et al [2] and Simpson [48] which were mentioned in Remarks 10.2 and 10.3 above.

Remark 10.5. Some of our natural weak degrees are closely related to certain formal systems which arise naturally in the foundations of mathematics. Namely, the weak degrees 1, r, d correspond to the systems WKL_{0}, WWKL_{0}, RCA_{0} + DNR respectively. Each of these subsystems of second order arithmetic is of interest in connection with the well known foundational program of reverse mathematics. See Simpson [52, Chapter IV and Section X.1], Yu/Simpson [61], Brown/Giusto/Simpson [7], and Giusto/Simpson [23]. The standard reference for reverse mathematics is Simpson [52].

Remark 10.6. From the recursion-theoretic viewpoint, there are some subtle issues concerning naturalness of the mass problems DNR, DNR_{REC}, DNR_{h} and of their weak degrees d, d_{REC}, d_{h}. First, DNR, DNR_{REC}, DNR_{h} are not invariant under recursive permutations of ω, and on this basis it is possible to question their recursion-theoretic naturalness. (See also the discussion of the recursion-theoretic Erlanger Programm in Rogers [45, Chapter 4].) On the other hand, this objection clearly does not apply to the weak degrees d, d_{REC}, d_{h}, because all weak and strong degrees are invariant under recursive permutations of ω. Second, one may note that our definitions of DNR, DNR_{REC}, DNR_{h} and their weak degrees d, d_{REC}, d_{h} depend upon a particular choice of Gödel numbering of Turing machines, because the function n ↦ {n}(n) is defined in terms of such a Gödel numbering. (See also the discussion of acceptable Gödel numberings in Rogers [45].) We shall now present a method of overcoming this objection. Our idea is to replace the particular partial recursive function n ↦ {n}(n) by an arbitrary partial recursive function n ↦ ψ(n). This will answer the objection, because the extensional concept “partial recursive function” is independent of the choice of Gödel numbering.

Definition 10.7. Let D be the set of g ∈ ω^{ω} such that for all partial recursive functions ψ there exists f ≤_{T} g such that ∀n (f(n) ≠ ψ(n)). Let D_{REC} be the set of g ∈ ω^{ω} such that for all partial recursive functions ψ there exists f ≤_{T} g such that ∀n (f(n) < h(n) and f(n) ≠ ψ(n)) for some recursive function h : ω → ω.

Remark 10.8. Using the S-m-n Theorem, it is easy to see that DNR ≡_{w} D and DNR_{REC} ≡_{w} D_{REC}. (See also the proof of Theorem 10.10 below.) Thus the weak degrees d and d_{REC} are natural in the sense that they can be defined in a way that does not depend on the choice of Gödel numbering. What about d_{h} where h is a fixed recursive function? Let D_{h} be the set of g ∈ ω^{ω} such that for all partial recursive functions ψ there exists f ≤_{T} g such that ∀n (f(n) < h(n) and f(n) ≠ ψ(n)). It is not clear that DNR_{h} ≡_{w} D_{h} for a fixed recursive function h, but we have the following definition and theorem for classes of recursive functions.

Definition 10.9. If C is a class of recursive functions, put DNR_{C} = ⋃_{h∈C} DNR_{h}. Let D_{C} be the set of g ∈ ω^{ω} such that for all partial recursive functions ψ there exists f ≤_{T} g such that ∀n (f(n) < h(n) and f(n) ≠ ψ(n)) for some h ∈ C.

Theorem 10.10. If C is closed under composition with primitive recursive functions, then DNR_{C} ≡_{w} D_{C}. If there exists a uniform recursive enumeration of C, then deg_{w}(DNR_{C}) ∈ P_{w}.

Proof. Given g ∈ D_{C}, let f ≤_{T} g be as in the definition of D_{C} for the particular partial recursive function ψ(n) ≃ {n}(n). Clearly f ∈ DNR_{C}, and this shows that DNR_{C} ≤_{w} D_{C}. Conversely, to show that DNR_{C} ≥_{w} D_{C}, let f ∈ DNR_{C} be given, say f ∈ DNR_{h} where h ∈ C. Given a partial recursive function ψ, apply the S-m-n Theorem to get a primitive recursive function p : ω → ω such that {p(n)}(p(n)) ≃ ψ(n) for all n. Then we have ∀n (f(p(n)) < h(p(n)) and f(p(n)) ≠ ψ(n)). Moreover, the function n ↦ f(p(n)) is Turing reducible to f, and the function n ↦ h(p(n)) belongs to C. Thus f ∈ D_{C}. We have now shown that DNR_{C} ⊆ D_{C}. It follows that DNR_{C} ≥_{w} D_{C}, and we have proved the first part of the theorem. To prove the second part, let h_{n}, n ∈ ω be a uniform recursive enumeration of C. Putting P_{n} = DNR_{h_{n}}, we note that P_{n} is uniformly recursively bounded and Π_{1}^{0}. As in the proof of Theorem 4.10, put P_{n}^{∗} = {G_{f} | f ∈ P_{n}}. Thus P_{n}^{∗} is a uniformly Π_{1}^{0} subset of 2^{ω} which is uniformly recursively homeomorphic to P_{n}. Put S^{∗} = ⋃_{n} P_{n}^{∗}. Then S^{∗} is a Σ_{2}^{0} subset of 2^{ω}, and by construction S^{∗} is Turing degree isomorphic to ⋃_{n} P_{n} = DNR_{C}. Now apply Theorem 10.11 to find a Π_{1}^{0} set P^{∗} ⊆ 2^{ω} such that P^{∗} is Turing degree isomorphic to S^{∗}. Then deg_{w}(DNR_{C}) = deg_{w}(S^{∗}) = deg_{w}(P^{∗}) ∈ P_{w}.

Theorem 10.11. Let S be a Σ_{2}^{0} subset of 2^{ω}. Then we can find a Π_{1}^{0} set P ⊆ 2^{ω} such that P is Turing degree isomorphic to S.

Proof. We may safely assume that S is nonempty. By hypothesis S = ⋃_{n} P_{n} where P_{n}, n ∈ ω is a recursive sequence of nonempty Π_{1}^{0} subsets of 2^{ω}. We use a construction from Binns/Simpson [6, Definition 4.2]. Let T_{n}, n ∈ ω be a recursive sequence of infinite recursive subtrees of 2^{<ω} such that P_{n} = [T_{n}], the set of paths through T_{n}. Put

T̃_{0} = {σ^{⌢}⟨i⟩ | σ ∈ T_{0}, i ∈ {0, 1}, σ^{⌢}⟨i⟩ ∉ T_{0}}.

We may safely assume that T̃_{0} is infinite. Note that the strings in T̃_{0} are pairwise incompatible. Let τ_{n}, n ∈ ω be a one-to-one recursive enumeration of T̃_{0}. Put T = T_{0} ∪ ⋃_{n}{τ_{n}^{⌢}σ | σ ∈ T_{n}}. Thus T is an infinite recursive subtree of 2^{<ω}. Let P = [T], the set of paths through T. Thus P is a nonempty Π_{1}^{0} subset of 2^{ω}. By construction we have P = P_{0} ∪ ⋃_{n}{τ_{n}^{⌢}f | f ∈ P_{n}}, hence P is Turing degree isomorphic to ⋃_{n} P_{n} = S.

Remark 10.12. In the proof of Theorem 10.11, note that p = inf_{n} p_{n}, where p = deg_{w}(P) and p_{n} = deg_{w}(P_{n}). Thus the proof shows that P_{w} is closed under effective infima.

Remark 10.13. If C is a class of recursive functions satisfying the hypotheses of Theorem 10.10, put d_{C} = deg_{w}(DNR_{C}). We have seen that d_{C} ∈ P_{w} and that d_{C} is natural in the sense that it can be defined in a way which does not depend on the choice of Gödel numbering. Moreover, if C^{∗} ⊃ C is another such class, then d_{C^{∗}} ≤ d_{C}, and according to Ambos-Spies et al [2, Theorem 1.9] we have strict inequality d_{C^{∗}} < d_{C} provided C^{∗} contains a function which “grows much faster than” all functions in C. There are many examples and problems here.

Example 10.14. For each constructive ordinal α, let C_{α} be the class of recursive functions obtained at levels < ω · (1 + α) of the transfinite Ackermann hierarchy. (See for instance Wainer [60].) Thus C_{0} is the class of primitive recursive functions, C_{1} is the class of functions which are primitive recursive relative to the Ackermann function, etc. Putting d_{α} = d_{C_{α}} we have a transfinite descending sequence

d_{0} > d_{1} > ⋯ > d_{α} > d_{α+1} > ⋯

in P_{w}. Moreover, if α is a limit ordinal, then d_{α} = inf_{β<α} d_{β}. Thus we see a rich set of natural degrees in P_{w} which are related to subrecursive hierarchies of the kind that arise in Gentzen-style proof theory.

Remark 10.15. Let us assume that we are using one of the standard Gödel numberings of Turing machines which appear in the literature. Then the function p(n) in the proof of Theorem 10.10 can be chosen to be bounded by a linear function. Therefore, instead of assuming that C is closed under composition with primitive recursive functions, we could assume merely that for all h ∈ C and c ≥ 1 there exists h_{c}^{∗} ∈ C such that h_{c}^{∗}(n) ≥ h(m) for all m ≤ c · (n + 1). In particular, we can take C to be various well known computational complexity classes such as PTIME, EXPTIME, etc. For each such class, Theorem 10.10 shows that the weak degree d_{C} ∈ P_{w} is natural in that its definition does not depend on the choice of a standard Gödel numbering.

Example 10.16. In P_{w} we have

d_{PTIME} > d_{EXPTIME} > ⋯

etc. Thus we see a rich set of natural degrees in P_{w} which are related to computational complexity.

References

[1] K. Ambos-Spies, G. H. Müller, and G. E. Sacks, editors. Recursion Theory Week. Number 1432 in Lecture Notes in Mathematics. Springer-Verlag, 1990. IX + 393 pages.

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

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

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

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

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

[7] Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson. Vitali’s theorem and WWKL. Archive for Mathematical Logic, 41:191–206, 2002.

[8] P. Bruscoli and A. Guglielmi, editors. Summer School and Workshop on Proof Theory, Computation and Complexity, Dresden, 2003. Electronic Notes in Theoretical Computer Science. Elsevier, 2004. To appear.

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

[10] Douglas Cenzer and Jeffrey B. Remmel. Π_{1}^{0} classes in mathematics. In [20], pages 623–821, 1998.

[11] Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann. Automorphisms of the lattice of Π_{1}^{0} classes; perfect thin classes and ANC degrees. Transactions of the American Mathematical Society, 353:4899–4924, 2001.

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

September 1995 to the present.

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

[14] Oswald Demuth. A notion of semigenericity. Commentationes Mathematicae Universitatis Carolinae, 28:71–84, 1987.

[15] Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob. Array nonrecursive sets and multiple permitting arguments. In [1], pages 141–174, 1990.

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

[17] F. R. Drake and J. K. Truss, editors. Logic Colloquium ’86. Studies in Logic and the Foundations of Mathematics. North-Holland, 1988. X + 342 pages.

[18] H.-D. Ebbinghaus, J. Fernandez-Prida, M. Garrido, D. Lascar, and M. Rodriguez Artalejo, editors. Logic Colloquium ’87. Studies in Logic and the Foundations of Mathematics. North-Holland, 1989. X + 375 pages.

[19] H.-D. Ebbinghaus, G. H. Müller, and G. E. Sacks, editors. Recursion Theory Week. Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985. IX + 418 pages.

[20] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors. Handbook of Recursive Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, 1998. Volumes 1 and 2, XLVI + 1372 pages.

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

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

September 1997 to the present.

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

[24] J. Gruska, B. Rovan, and J. Wiedermann, editors. Mathematical Foundations of Computer Science. Number 233 in Lecture Notes in Computer Science. Springer-Verlag, 1986. IX + 650 pages.

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

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

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

[28] Stuart A. Kurtz. Randomness and Genericity in the Degrees of Unsolvability. PhD thesis, University of Illinois at Urbana-Champaign, 1981. VII + 131 pages.

[29] Antonín Kučera. Measure, Π_{1}^{0} classes and complete extensions of PA. In [19], pages 245–259, 1985.

[30] Antonín Kučera. An alternative, priority-free, solution to Post’s problem. In [24], pages 493–500, 1986.

[31] Antonín Kučera. On the role of 0′ in recursion theory. In [17], pages 133–141, 1988.

[32] Antonín Kučera. On the use of diagonally nonrecursive functions. In [18], pages 219–239, 1989.

[33] Antonín Kučera. Randomness and generalizations of fixed point free functions. In [1], pages 245–254, 1990.

[34] Antonín Kučera. On relative randomness. Annals of Pure and Applied Logic, 63:61–67, 1993.

[35] Antonín Kučera and Sebastiaan A. Terwijn. Lowness for the class of random sets. Journal of Symbolic Logic, 64:1396–1402, 1999.

[36] Manuel Lerman. Degrees of Unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, 1983. XIII + 307 pages.

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

[38] Donald A. Martin and Marian B. Pour-El. Axiomatizable theories with few axiomatizable extensions. Journal of Symbolic Logic, 35:205–209, 1970.

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

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

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

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

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

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

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

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

[47] S. G. Simpson, editor. Reverse Mathematics 2001, volume 21 of Lecture Notes in Logic. Association for Symbolic Logic, 2005. X + 401 pages.

[48] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society. Preprint, August 2004, 15 pages, accepted for publication.

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

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

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

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

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

[54] Stephen G. Simpson. Π_{1}^{0} sets and models of WKL_{0}. In [47], pages 352–378. 2005.

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

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

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

[58] Sebastiaan A. Terwijn. The Medvedev lattice of computably closed sets. Archive for Mathematical Logic. Preprint, June 2004, 22 pages, accepted for publication.

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

[60] Stanley S. Wainer. A classification of the ordinal recursive functions. Archiv für Mathematische Logik und Grundlagenforschung, 13:136–153, 1970.

[61] Xiaokang Yu and Stephen G. Simpson. Measure theory and weak König’s lemma. Archive for Mathematical Logic, 30:171–180, 1990.