Mass Problems and Randomness

Stephen G. Simpson

Department of Mathematics

Draft: October 27, 2004

Pennsylvania State University

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 $\mathcal{P}_w$ and $\mathcal{P}_s$ of weak and strong degrees of mass problems given by nonempty $\Pi ^0_1$ subsets of $2^\omega$. Using an abstract Gödel/Rosser incompleteness property, we characterize the $\Pi ^0_1$ subsets of $2^\omega$ whose associated mass problems are of top degree in $\mathcal{P}_w$ and $\mathcal{P}_s$, respectively. Let $R$ be the set of Turing oracles which are random in the sense of Martin-Løf, and let $\mathbf{r}$ be the weak degree of $R$. We show that $\mathbf{r}$ is a natural intermediate degree within $\mathcal{P}_w$. Namely, we characterize $\mathbf{r}$ as the unique largest weak degree of a $\Pi ^0_1$ subset of $2^\omega$ of positive measure. Within $\mathcal{P}_w$ we show that $\mathbf{r}$ is meet irreducible, does not join to $\mathbf{1}$, and is incomparable with all weak degrees of nonempty thin perfect $\Pi ^0_1$ subsets of $2^\omega$. In addition, we present other natural examples of intermediate degrees in $\mathcal{P}_w$. We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory.

Contents

• Introduction
• Recursion-theoretic preliminaries
• Mass problems
• Recursively bounded $\Pi ^0_1$ sets
• The lattices $\mathcal{P}_w$ and $\mathcal{P}_s$
• Weak and strong completeness
• $\Pi ^0_1$ sets of positive measure
• $\Pi ^0_1$ sets of random reals
• Thin $\Pi ^0_1$ subsets of $2^\omega$
• Some additional natural examples in $\mathcal{P}_w$
• Bibliography

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 $\mathcal{D}_T$ of all Turing degrees, i.e., degrees of unsolvability, and its countable sub-semilattice $\mathcal{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 $\mathcal{R}_T$ has been the lack of natural examples. Although it has long been known that $\mathcal{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: $\mathbf{0'}=$ the Turing degree of the Halting Problem, and $\mathbf{0}=$ the Turing degree of solvable problems. Furthermore, $\mathbf{0'}$ and $\mathbf{0}$ are respectively the top and bottom elements of $\mathcal{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 $\mathcal{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 $\mathcal{R}_T$.

In recent years it has emerged that there are some natural, important, well-behaved degree structures, closely related to but different from $\mathcal{R}_T$, which do not suffer from the above mentioned deficiency. Simpson 1999 [50,51,54] called attention to the countable distributive lattices $\mathcal{P}_w$ and $\mathcal{P}_s$ of weak and strong degrees of mass problems given by nonempty $\Pi ^0_1$ subsets of $2^\omega$, and noted the existence of specific, natural degrees which are intermediate between the top and bottom elements of $\mathcal{P}_w$ and $\mathcal{P}_s$. One of the natural intermediate degrees noted by Simpson was the weak degree $\mathbf{r}$ of the set of Turing oracles which are random in the sense of Martin-Løf [39]. The study of $\mathcal{P}_w$ and $\mathcal{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 $\mathcal{P}_w$ and $\mathcal{P}_s$, and to present some additional natural degrees in $\mathcal{P}_w$. Along the way we give a somewhat leisurely introduction to mass problems in general, and to $\mathcal{P}_w$ and $\mathcal{P}_s$ in particular, and we review other known results concerning $\mathcal{P}_w$ and $\mathcal{P}_s$.

In a later paper [48] we shall exhibit a natural embedding of the countable upper semilattice $\mathcal{R}_T$ into the countable distributive lattice $\mathcal{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 $\mathcal{R}_T$. In this way we shall see that $\mathcal{P}_w$ provides a satisfactory solution to several of the well known difficulties concerning $\mathcal{R}_T$.

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 $\omega=\{0,1,2,\dots\}$ for the set of natural numbers. We write $\omega^\omega$ for the space of total functions from $\omega$ into $\omega$. We write $2^\omega$ for the subspace of $\omega^\omega$ consisting of the total functions from $\omega$ into $\{0,1\}$. We sometimes identify a set $A\subseteq\omega$ with its characteristic function $\chi_A\in2^\omega$ given by $\chi_A(n)=1$ if $n\in A$, $0$ if $n\notin A$. For $e,n,m\in\omega$ and $f\in\omega^\omega$ 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)\downarrow$ means that $\{e\}^f(n)$ is defined, i.e., $\exists m (\{e\}^f(n)=m)$, and $\{e\}^f(n)\uparrow$ means that $\{e\}^f(n)$ is undefined, i.e., $\lnot\exists m (\{e\}^f(n)=m)$. In the absence of an oracle $f$, we write simply $\{e\}(n)=m$, etc. For $P\subseteq\omega^\omega$ we consider recursive functionals $\Phi:P\to\omega^\omega$ given by $\Phi(f)(n)=\{e\}^f(n)$ for some $e\in\omega$ and all $f\in P$ and $n\in\omega$. In particular, a function $h:\omega\to\omega$ is said to be recursive or computable if there exists $e\in\omega$ such that $h(n)=\{e\}(n)$ for all $n\in\omega$. (The terms ``recursive'' and ``computable'' are synonymous.) A set $A\subseteq\omega$ is said to be recursively enumerable if it is the image of a recursive function, i.e., $A=\{m\mid\exists n (h(n)=m)\}$ for some recursive $h:\omega\to\omega$.

For $f,g\in\omega^\omega$ we write $f\le_Tg$ to mean that $f$ is Turing reducible to $g$, i.e., $\exists e \forall n (f(n)=\{e\}^g(n))$. The Turing degree of $f$, denoted $\deg_T(f)$, is the set of all $g$ such that $f\equiv_Tg$, i.e., $f\le_Tg$ and $g\le_Tf$. The set $\mathcal{D}_T$ of all Turing degrees is partially ordered by putting $\deg_T(f)\le\deg_T(g)$ if and only if $f\le_Tg$. Under this partial ordering, the bottom element of $\mathcal{D}_T$ is $\mathbf{0}=\{f\in\omega^\omega\mid f$ is recursive$\}$. It is known that $\mathcal{D}_T$ has no top element. Within $\mathcal{D}_T$, the least upper bound of $\deg_T(f)$ and $\deg_T(g)$ is given as $\deg_T(f\oplus g)$ where $(f\oplus g)(2n)=f(n)$ and $(f\oplus g)(2n+1)=g(n)$ for all $n\in\omega$. The standard, natural example of a Turing degree $>\deg_T(f)$ is given by the Turing jump operator, $\deg_T(f)\mapsto\deg_T(f)'=\deg_T(f')$, where $f'$ is (the characteristic function of) the Halting Problem relative to $f$, $H^f=\{e\mid\{e\}^f(0)\downarrow\}$. A Turing degree is said to be recursively enumerable if it is $\deg_T(f)$ where $f=\chi_A$ is the characteristic function of a recursively enumerable set $A\subseteq\omega$. The set of all recursively enumerable Turing degrees is denoted $\mathcal{R}_T$. Clearly $\mathcal{R}_T$ is countable, because there are only countably many recursively enumerable sets. It is known that $\mathcal{R}_T$ is closed under the least upper bound operation inherited from $\mathcal{D}_T$, and that $\mathbf{0'}$ and $\mathbf{0}$ are the top and bottom elements of $\mathcal{R}_T$. Thus $\mathcal{R}_T$ is a countable upper semilattice with a top and bottom element.

Mass problems

A mass problem is a subset of $\omega^\omega$. The underlying idea here is to view a set $P\subseteq\omega^\omega$ 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 $\omega^\omega$. We say that $P$ is weakly reducible to $Q$, written $P\le_w Q$, if for all $g\in Q$ there exists $f\in P$ such that $f\le_Tg$. 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\equiv_wQ$, i.e., $P\le_w Q$ and $Q\le_wP$. The set $\mathcal{D}_w$ of all weak degrees is partially ordered by putting $\deg_w(P)\le\deg_w(Q)$ if and only if $P\le_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\le_s Q$, if there exists $e\in\omega$ such that for all $g\in Q$ there exists $f\in P$ such that $f(n)=\{e\}^g(n)$ for all $n\in\omega$. In other words, $P\le_s Q$ if and only if there exists a recursive functional $\Phi:Q\to 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\equiv_sQ$, i.e., $P\le_s Q$ and $Q\le_sP$. The set $\mathcal{D}_s$ of all strong degrees is partially ordered by putting $\deg_s(P)\le\deg_s(Q)$ if and only if $P\le_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\subseteq\omega^\omega$, a recursive homeomorphism of $P$ onto $Q$ is a recursive functional $\Phi:P\to Q$ mapping $P$ one-to-one onto $Q$ such that the inverse functional $\Phi^{-1}:Q\to 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)\mid f\in P\}=\{\deg_T(g)\mid g\in 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   $\mathcal{D}_w$ and $\mathcal{D}_s$ are distributive lattices. They have a bottom element, denoted $\mathbf{0}$, and a top element, denoted $\mathbf{\infty}$.

Remark 3.7   There are obvious, natural embeddings of $\mathcal{D}_T$ into $\mathcal{D}_w$ and $\mathcal{D}_s$ given by $\deg_T(f)\mapsto\deg_w(\{f\})$ and $\deg_T(f)\mapsto\deg_s(\{f\})$ respectively. Here $\{f\}$ is the singleton set whose only member is $f\in\omega^\omega$. These embeddings are one-to-one and preserve $\mathbf{0}$ and the partial order relation and least upper bound operation from $\mathcal{D}_T$.

Remark 3.8   There is an obvious lattice homomorphism of $\mathcal{D}_s$ onto $\mathcal{D}_w$ given by $\deg_s(P)\mapsto\deg_w(P)$.

Remark 3.9   $\mathcal{D}_w$ is canonically isomorphic to the lattice of upward closed subsets of $\mathcal{D}_T$ under the set-theoretic operations of intersection and union. Namely, for each $P\subseteq\omega^\omega$, the weak degree $\deg_w(P)\in\mathcal{D}_w$ gets mapped to the upward closure of $\{\deg_T(f)\mid f\in P\}$ within $\mathcal{D}_T$. It follows that $\mathcal{D}_w$ is a complete distributive lattice. We do not know of an analogous set-theoretic representation of $\mathcal{D}_s$.

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

Recursively bounded $\Pi ^0_1$ sets

In this section we present some well known generalities concerning recursively bounded $\Pi ^0_1$ 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\subseteq\omega^\omega\times\omega$ is said to be recursive if

$\exists e \forall f \forall n (\{e\}^f(n)=1$ if $R(f,n)$, and $\{e\}^f(n)=0$ if $\lnot R(f,n))$. A set $P\subseteq\omega^\omega$ is said to be $\Pi ^0_1$ if there exists a recursive predicate $R\subseteq\omega^\omega\times\omega$ such that $P=\{f\mid\forall n R(f,n)\}$.

Definition 4.2   A finite sequence of natural numbers $\sigma=\langle\sigma(0),\ldots,\sigma(k-1)\rangle$ is called a string of length $k$. We write $\mathrm{lh}(\sigma)=k$. The set of all strings is denoted $\omega^{<\omega}$. If $\sigma,\tau$ are strings of length $k,l$ respectively, then the concatenation

$$\sigma{{}^\smallfrown}\tau=\langle \sigma(0),\ldots,\sigma(k-1),\tau(0),\ldots,\tau(l-1)\rangle$$

is a string of length $k+l$. Note that $\sigma\subseteq\tau$ if and only if $\sigma{{}^\smallfrown}\rho=\tau$ for some $\rho$, and this implies $\mathrm{lh}(\sigma)\le\mathrm{lh}(\tau)$. If $\sigma$ is a string of length $k$, then for all $f\in\omega^\omega$ we have $\sigma{{}^\smallfrown} f\in\omega^\omega$ defined by $(\sigma{{}^\smallfrown}f)(i)=\sigma(i)$ for $i<k$, $f(i-k)$ for $i\ge k$. Note that $\sigma\subset f$ if and only if $\sigma{{}^\smallfrown}g=f$ for some $g\in\omega^\omega$. A tree is a set $T\subseteq\omega^{<\omega}$ such that, for all $\sigma\subseteq\tau\in T$, $\sigma\in T$. A path through $T$ is an $f\in\omega^\omega$ such that $(\forall\sigma\subset f) (\sigma\in T)$. The set of all paths through $T$ is denoted $[T]$. We sometimes identify a string $\sigma$ with its Gödel number $\char93 (\sigma)\in\omega$. A tree $T$ is said to be recursive if $\{\char93 (\sigma)\mid\sigma\in T\}$ is recursive, and $\Pi ^0_1$ if $\{\char93 (\sigma)\mid\sigma\in T\}$ is $\Pi ^0_1$.

Theorem 4.3   $P\subseteq\omega^\omega$ is $\Pi ^0_1$ if and only if $P=[T]$ for some recursive tree $T$.

Theorem 4.4   If $P,Q\subseteq\omega^\omega$ are $\Pi ^0_1$ and $\Phi:P\to\omega^\omega$ is a recursive functional, then the preimage $\{f\in P\mid\Phi(f)\in Q\}$ is $\Pi ^0_1$.

Definition 4.5   A set $P\subseteq\omega^\omega$ is said to be recursively bounded if there exists a recursive function $h\in\omega^\omega$ such that $f(n)<h(n)$ for all $f\in P$ and $n\in\omega$.

Remark 4.6   Any subset of a recursively bounded set is recursively bounded. We shall be concerned with subsets of $\omega^\omega$ which are recursively bounded and $\Pi ^0_1$. In particular, $2^\omega$ is recursively bounded and $\Pi ^0_1$, and we are especially interested in $\Pi ^0_1$ subsets of $2^\omega$. As in Theorem 4.3, $P$ is a $\Pi ^0_1$ subset of $2^\omega$ if and only if $P=[T]$ for some recursive tree $T\subseteq2^{<\omega}$. Here $2^{<\omega}$ 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\subseteq\omega^\omega$ is recursively bounded $\Pi ^0_1$, and assume that $\Phi:P\to\omega^\omega$ is a recursive functional. Then the image $\{\Phi(f)\mid f\in P\}$ is recursively bounded $\Pi ^0_1$. Moreover, there exists a total recursive functional $\Phi^\ast:\omega^\omega\to\omega^\omega$ such that $\Phi^\ast$ extends $\Phi$, i.e., $\Phi^\ast(f)=\Phi(f)$ for all $f\in P$.

Definition 4.8   In general, suppose that to each $n\in\omega$ we have effectively associated a finite sequence of ordered pairs $(\sigma_n^0,m_n^0),\ldots,(\sigma_n^{k_n},m_n^{k_n})$ where $\sigma_n^i\in\omega^{<\omega}$ and $m_n^i\in\omega$ for each $i\le k_n$. Define a recursive functional $\Phi:\omega^\omega\to\omega^\omega$ by putting $\Phi(f)(n)=m_n^i$ where $i\le k_n$ is minimal such that $\sigma_n^i\subset f$, or $\Phi(f)(n)=0$ if no such $i$ exists. Then $\Phi$ is called a truth table functional. For $f,g\in\omega^\omega$ we say that $f$ is truth table reducible to $g$, written $f\le_{tt}g$, if there exists a truth table functional $\Phi$ such that $f=\Phi(g)$. Rogers [45, Chapter 8 and Section 9.6] provides general background on truth table reducibility.

Corollary 4.9   Assume that $P\subseteq\omega^\omega$ is recursively bounded $\Pi ^0_1$, and assume that $\Phi:P\to\omega^\omega$ is a recursive functional. Then $\Phi$ can be extended to a truth table functional. In particular, $\Phi(f)\le_{tt}f$ for all $f\in P$.

Theorem 4.10   Let $P$ be a recursively bounded $\Pi ^0_1$ set. Then $P$ is recursively homeomorphic to a $\Pi ^0_1$ subset of $2^\omega$.

Corollary 4.11   The weak (strong) degrees of nonempty recursively bounded $\Pi ^0_1$ sets are the same as the weak (strong) degrees of nonempty $\Pi ^0_1$ subsets of $2^\omega$.

Definition 4.12   Given $P\subseteq\omega^\omega$, put

$$\mathrm{Ext}(P)=\{\sigma\mid(\exists f\in P) (\sigma\subset f)\} \subseteq\omega^{<\omega},$$

the set of extendible nodes of $P$. Note that $\mathrm{Ext}(P)$ is a tree, and $[\mathrm{Ext}(P)]$ is the topological closure of $P$ in $\omega^\omega$. In particular, if $P$ is $\Pi ^0_1$, then $P=[\mathrm{Ext}(P)]$.

Lemma 4.13   Let $P$ be a recursively bounded $\Pi ^0_1$ set. Then $\mathrm{Ext}(P)$ is $\Pi ^0_1$.

Definition 4.14   For $P\subseteq\omega^\omega$, an isolated point of $P$ is an $f\in P$ such that, for some string $\tau$, $f$ is the unique $g\in P$ such that $\tau\subset g$. We say that $P$ is perfect if $P$ has no isolated points.

Theorem 4.15   Let $P$ be a recursively bounded $\Pi ^0_1$ set. If $f$ is an isolated point of $P$, then $f$ is recursive.

Corollary 4.16   Let $P$ be a recursively bounded $\Pi ^0_1$ set. If the weak or strong degree of $P$ is $>\mathbf{0}$, then $P$ is perfect.

Definition 4.17   We say that $g\in\omega^\omega$ is almost recursive if for all $f\le_Tg$ there exists $h\in\omega^\omega$ such that $\forall 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\le_Tg$ we have $f\le_{tt}g$, i.e., $f$ is truth table reducible to $g$. In particular, $f=\Phi(g)$ for some total recursive functional $\Phi:\omega^\omega\to\omega^\omega$.

We end this section with the Almost Recursive Basis Theorem.

Theorem 4.19   If $P\subseteq\omega^\omega$ is nonempty, recursively bounded, and $\Pi ^0_1$, then there exists $g\in P$ such that $g$ is almost recursive.

The lattices $\mathcal{P}_w$ and $\mathcal{P}_s$

In this section we introduce the lattices $\mathcal{P}_w$ and $\mathcal{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 $\Pi ^0_1$ subsets of $\omega^\omega$, and especially Turing degrees of members of recursively bounded $\Pi ^0_1$ subsets of $\omega^\omega$. 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 $\Pi ^0_1$ sets as mass problems.

By Theorem 4.10 and Corollary 4.11, it suffices to consider $\Pi ^0_1$ subsets of $2^\omega$.

Definition 5.2   $\mathcal{P}_w$ ($\mathcal{P}_s$) is the set of weak (strong) degrees of nonempty recursively bounded $\Pi ^0_1$ sets. By Corollary 4.11, $\mathcal{P}_w$ ($\mathcal{P}_s$) is the same as the set of weak (strong) degrees of nonempty $\Pi ^0_1$ subsets of $2^\omega$.

Theorem 5.3   $\mathcal{P}_w$ and $\mathcal{P}_s$ are countable distributive lattices with a top and bottom element, denoted $\mathbf{1}$ and $\mathbf{0}$ respectively.

Remark 5.4   There is an obvious lattice homomorphism of $\mathcal{P}_s$ onto $\mathcal{P}_w$ given by $\deg_s(P)\mapsto\deg_w(P)$. Simpson and Slaman [55] have shown that every nonzero weak degree in $\mathcal{P}_w$ contains infinitely many strong degrees in $\mathcal{P}_s$.

Remark 5.5   In the context of recursively bounded $\Pi ^0_1$ 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 $\Pi ^0_1$ and $P\le_s Q$, then by Corollary 4.9 the recursive functional $\Phi:Q\to P$ is given by truth tables, hence for each $g\in Q$ there exists $f=\Phi(g)\in P$ such that $f\le_{tt}g$, i.e., $f$ is truth table reducible to $g$. Thus we see that $\mathcal{P}_w$ is analogous to $\mathcal{R}_T$, the recursively enumerable Turing degrees, while $\mathcal{P}_s$ is more closely analogous to $\mathcal{R}_{tt}$, the recursively enumerable truth table degrees.

Remark 5.6   It is known that the countable distributive lattices $\mathcal{P}_w$ and $\mathcal{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 $\mathcal{P}_w$. A similar conjecture for $\mathcal{P}_s$ remains open, although partial results in this direction are known. Binns [3,4] has obtained the $\mathcal{P}_w$ and $\mathcal{P}_s$ analogs of the Sacks Splitting Theorem. Namely, for all $\mathbf{b}>\mathbf{0}$ in $\mathcal{P}_w$ there exist $\mathbf{b}_1,\mathbf{b}_2<\mathbf{b}$ in $\mathcal{P}_w$ such that $\sup (\mathbf{b}_1,\mathbf{b}_2)=\mathbf{b}$, and similarly for $\mathcal{P}_s$. Cenzer/Hinman [9] have obtained the $\mathcal{P}_s$ analog of the Sacks Density Theorem. Namely, for all $\mathbf{a}<\mathbf{b}$ in $\mathcal{P}_s$ there exists $\mathbf{c}$ in $\mathcal{P}_s$ such that $\mathbf{a}<\mathbf{c}<\mathbf{b}$. A similar conjecture for $\mathcal{P}_w$ remains open. Binns [3,4] has improved the result of Cenzer/Hinman [9] by showing that for all $\mathbf{a}<\mathbf{b}$ in $\mathcal{P}_s$ there exist $\mathbf{b}_1,\mathbf{b}_2<\mathbf{b}$ in $\mathcal{P}_s$ such that $\mathbf{a}<\inf (\mathbf{b}_1,\mathbf{b}_2)< \sup (\mathbf{b}_1,\mathbf{b}_2)=\mathbf{b}$. These structural results for $\mathcal{P}_w$ and $\mathcal{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.

Weak and strong completeness

In this section we obtain additional information concerning sets which are of weak or strong degree $\mathbf{1}$ in $\mathcal{P}_w$ or $\mathcal{P}_s$, respectively. We show that, if $P$ is a nonempty recursively bounded $\Pi ^0_1$ set, then $\deg_w(P)=\mathbf{1}$ if and only if $P$ is Turing degree isomorphic to $\mathrm{PA}$, and $\deg_s(P)=\mathbf{1}$ if and only if $P$ is recursively homeomorphic to $\mathrm{PA}$.

By Theorem 4.10 and Corollary 4.11, it suffices to consider $\Pi ^0_1$ subsets of $2^\omega$.

Definition 6.1   Let $P$ be a nonempty recursively bounded $\Pi ^0_1$ set. $P$ is weakly complete if $\deg_w(P)=\mathbf{1}$, i.e., $P\ge_wQ$ for all nonempty $\Pi ^0_1$ sets $Q\subseteq2^\omega$. $P$ is strongly complete if $\deg_s(P)=\mathbf{1}$, i.e., $P\ge_sQ$ for all nonempty $\Pi ^0_1$ sets $Q\subseteq2^\omega$. 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 $\mathrm{PA}$ is strongly complete, hence weakly complete. In addition, there are natural examples of recursively bounded $\Pi ^0_1$ 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 $\Pi ^0_1$ subsets of $2^\omega$.

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 $\Phi:P\to Q$ which is onto $Q$, i.e., $Q=\{\Phi(f)\mid f\in P\}$.
3. $P$ is strongly complete if and only if $P$ is productive, i.e., given an index of a nonempty $\Pi ^0_1$ set $P'\subseteq P$ we can effectively find a canonically indexed clopen set $U\subseteq2^\omega$ such that both $P'\cap U$ and $P'\setminus U$ are nonempty.

Corollary 6.4   Let $P$ be a nonempty recursively bounded $\Pi ^0_1$ set. If $P$ is strongly complete, then the set of Turing degrees of members of $P$ is upward closed.

Corollary 6.5   Let $P$ be a nonempty recursively bounded $\Pi ^0_1$ set. Then $P$ is strongly complete if and only if $P$ is recursively homeomorphic to $\mathrm{PA}$.

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

Corollary 6.6   The set of Turing degrees of members of $\mathrm{PA}$ is upward closed.

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 $\varphi$ in the language of $T$ which is independent of $T'$, i.e., $T'\not\vdash\varphi$ and $T'\not\vdash\lnot\varphi$. 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 $\Pi ^0_1$ subsets of $2^\omega$.

Theorem 6.8   Let $P$ be a nonempty recursively bounded $\Pi ^0_1$ set. Then $P$ is weakly complete if and only if $P$ is Turing degree isomorphic to $\mathrm{PA}$.

Corollary 6.9   Let $P$ and $Q$ be nonempty recursively bounded $\Pi ^0_1$ sets. If $P$ and $Q$ are weakly complete, then $P$ is Turing degree isomorphic to $Q$.

We can now strengthen Corollary 6.4 as follows.

Corollary 6.10   Let $P$ be a nonempty recursively bounded $\Pi ^0_1$ set. If $P$ is weakly complete, then the set of Turing degrees of members of $P$ is upward closed.

$\Pi ^0_1$ sets of positive measure

Definition 7.1   The fair coin probability measure on $2^\omega$ is defined by

$$\mu(\{f\in2^\omega\mid f(n)=m\})=\frac12$$

for all $m\in\{0,1\}$ and $n\in\omega$. A set $P\subseteq2^\omega$ is said to be of positive measure if $\mu(P)>0$.

In this section we prove a ``non-helping'' theorem for weak and strong degrees of subsets of $2^\omega$ which are of positive measure.

Lemma 7.2   Let $F_n$, $n\in\omega$ be a sequence of finite subsets of $\omega$ of bounded cardinality. Put

$S=\prod_{n\in\omega}F_n=\{f\in\omega^\omega\mid\forall n (f(n)\in F_n)\}\subseteq\omega^\omega$.

Let $P\subseteq2^\omega$ be of positive measure. Let $Q\subseteq\omega^\omega$ be arbitrary. If $S\le_sP\times Q$, then $S\le_sQ$.

Lemma 7.3   Same as Lemma 7.2 with strong reducibility, $\le_s$, replaced by weak reducibility, $\le_w$.

Definition 7.4   For $A,B\subseteq\omega$ we say that $f\in2^\omega$ separates $A,B$ if $f(n)=1$ for all $n\in A$, and $f(n)=0$ for all $n\in B$. A nonempty $\Pi ^0_1$ set $S\subseteq2^\omega$ is said to be separating if there exist recursively enumerable sets $A,B\subseteq\omega$ such that $S=\{f\in2^\omega\mid 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 $\Pi ^0_1$ subsets of $2^\omega$. Assume that $S$ is separating and that $P$ is of positive measure. Let $\mathbf{s,p,q}\in\mathcal{P}_w$ be the weak degrees of $S,P,Q$ respectively. If $\mathbf{s}\le\sup (\mathbf{p},\mathbf{q})$, then $\mathbf{s}\le\mathbf{q}$. The same holds for strong degrees.

Corollary 7.6   Let $P$ and $Q$ be nonempty $\Pi ^0_1$ subsets of $2^\omega$. Assume that $P$ is of positive measure. Let $\mathbf{p,q}\in\mathcal{P}_w$ be the weak degrees of $P,Q$ respectively. If $\mathbf{q}<\mathbf{1}$, then $\sup (\mathbf{p},\mathbf{q})<\mathbf{1}$. The same holds for strong degrees.

Corollary 7.7   Let $P$ be a $\Pi ^0_1$ subset of $2^\omega$ of positive measure. Let $\mathbf{p}\in\mathcal{P}_w$ be the weak degree of $P$. Then $\mathbf{p}<\mathbf{1}$. The same holds for strong degrees.

Remark 7.8   In [48] we shall give an example of a $\Pi ^0_1$ set $Q\subseteq2^\omega$ whose Turing upward closure $\widehat{Q}=\{f\in2^\omega\mid(\exists g\le_Tf) (g\in Q)\}$ is of positive measure yet does not contain any $\Pi ^0_1$ set of positive measure.

Definition 7.9   Following Jockusch [25], for $k\ge2$ we define

$\mathrm{DNR}_k=\{f\in\omega^\omega\mid\forall n (f(n)<k$ and $f(n)\ne\{n\}(n))\}$. Thus $\mathrm{DNR}_k$ is the set of $k$-bounded, diagonally nonrecursive functions. Note that $\mathrm{DNR}_k$ is recursively bounded and $\Pi ^0_1$.

Remark 7.10   By Jockusch [25, Theorem 5] each $\mathrm{DNR}_k$ is weakly complete, i.e., of weak degree $\mathbf{1}$. Let $\mathbf{d}^\ast_k\in\mathcal{P}_s$ be the strong degree of $\mathrm{DNR}_k$. It is well known (see also the proof of Corollary 7.6 above) that $\mathrm{DNR}_2$ is strongly complete, i.e., $\mathbf{d}^\ast_2=\mathbf{1}$ in $\mathcal{P}_s$. By Jockusch [25, Theorem 6] we have

$\mathbf{1}=\mathbf{d}^\ast_2>\mathbf{d}^\ast_3>\cdots >\mathbf{d}^\ast_k>\mathbf{d}^\ast_{k+1}>\cdots$ in $\mathcal{P}_s$. See also Simpson [54, Remark 3.21].

We have the following new result.

Corollary 7.11   Let $P$ and $Q$ be $\Pi ^0_1$ subsets of $2^\omega$. Assume that $P$ is of positive measure. Let $\mathbf{p,q}\in\mathcal{P}_s$ be the strong degrees of $P,Q$ respectively. For each $k\ge2$, if $\mathbf{d}^\ast_k\le\sup (\mathbf{p},\mathbf{q})$, then $\mathbf{d}^\ast_k\le\mathbf{q}$. In particular we have

$\mathbf{1}=\sup (\mathbf{p},\mathbf{d}^\ast_2) >\sup (\mathbf{p},\mathbf{d}^... ...\mathbf{p},\mathbf{d}^\ast_k) >\sup (\mathbf{p},\mathbf{d}^\ast_{k+1})>\cdots$.

Remark 7.12   In Corollary 7.11, we do not know whether it is necessarily the case that $\mathbf{d}^\ast_3\ge\mathbf{p}$, or $\mathbf{d}^\ast_k\ge\mathbf{p}$ for all $k\ge3$.

$\Pi ^0_1$ sets of random reals

In this section we exhibit a particular degree $\mathbf{r}\in\mathcal{P}_w$ and note some of its degree-theoretic properties.

As in Section 7, let $\mu$ denote the fair coin probability measure on $2^\omega$.

Definition 8.1   An effective null $G_\delta$ is a set $S\subseteq2^\omega$ of the form $S=\bigcap_{n\in\omega}U_n$ where $\{U_n\}_{n\in\omega}$ is a recursive sequence of $\Sigma^0_1$ subsets of $2^\omega$ with $\mu(U_n)\le1/2^n$ for all $n$. A point $f\in2^\omega$ is said to be random if $f\notin S$ for all effective null $G_\delta$ sets $S\subseteq2^\omega$.

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 (Kucera [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_\delta$ sets is an effective null $G_\delta$ set.

Theorem 8.3   $\{f\in2^\omega\mid f$ is not random$\}$ is an effective null $G_\delta$ set.

Corollary 8.4   There exists a nonempty $\Pi ^0_1$ set

$P\subseteq R=\{f\in2^\omega\mid f$ is random$\}$.

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

Lemma 8.6   For all $f\in2^\omega$ and $k\in\omega$, $f$ is random if and only if $f^{(k)}$ is random.

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

Lemma 8.7   Let $f$ be random. Let $P\subseteq2^\omega$ be $\Pi ^0_1$ with $\mu(P)>0$. Then $\exists k (f^{(k)}\in P)$.

Lemma 8.8   Let $f\in2^\omega$ be random. Then for all $\Pi ^0_1$ sets $P\subseteq2^\omega$, if $f\in P$ then $\mu(P)>0$.

Lemma 8.9   Let $P$ and $R$ be as in Corollary 8.4. Then $\mu(P)>0$, and $P\equiv_wR$.

Theorem 8.10   Let $\mathbf{r}=\deg_w(R)$ where $R=\{f\in2^\omega\mid f$ is random$\}$. Then $\mathbf{r}$ can be characterized as the unique largest weak degree of a $\Pi ^0_1$ set $P\subseteq2^\omega$ such that $\mu(P)>0$.

Remark 8.11   Theorem 8.10 tells us that, among all weak degrees of $\Pi ^0_1$ 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 $\Pi ^0_1$ 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 $\mathbf{r}$ which was defined in Theorem 8.10.

Theorem 8.12   Let $\mathbf{r}$ be the weak degree of $R=\{f\in2^\omega\mid f$ is random$\}$. Then:

1. $\mathbf{r}\in\mathcal{P}_w$, and $\mathbf{0}<\mathbf{r}<\mathbf{1}$.
2. For all $\mathbf{q}\in\mathcal{P}_w$, if $\mathbf{q}<\mathbf{1}$ then $\sup (\mathbf{q},\mathbf{r})<\mathbf{1}$.
3. For all $\mathbf{q}_1,\mathbf{q}_2\in\mathcal{P}_w$, if $\mathbf{r}\ge\inf (\mathbf{q}_1,\mathbf{q}_2)$ then either $\mathbf{r}\ge\mathbf{q}_1$ or $\mathbf{r}\ge\mathbf{q}_2$.
4. There is no separating $\mathbf{s}\in\mathcal{P}_w$ such that $\mathbf{0}<\mathbf{s}\le\mathbf{r}$.

Corollary 8.13   The weak degree $\mathbf{r}\in\mathcal{P}_w$ is meet irreducible and does not join to $\mathbf{1}$ in $\mathcal{P}_w$.

Thin $\Pi ^0_1$ subsets of $2^\omega$

In this section we discuss an interesting class of degrees in $\mathcal{P}_w$, each of which is incomparable with the particular degree $\mathbf{r}\in\mathcal{P}_w$ of Section 8.

We begin with some generalities concerning thin $\Pi ^0_1$ sets.

Definition 9.1   A $\Pi ^0_1$ set $Q\subseteq\omega^\omega$ is said to be thin if, for all $\Pi ^0_1$ sets $Q'\subseteq Q$, the set-theoretic difference $Q\setminus Q'$ is $\Pi ^0_1$.

Lemma 9.2   Let $Q$ be a recursively bounded $\Pi ^0_1$ set. Then $Q$ is thin if and only if all $\Pi ^0_1$ subsets of $Q$ are trivial, i.e., they are of the form

$Q'=\{g\in Q\mid\sigma_1\subset g$ or $\cdots$ or $\sigma_k\subset g\}$

for some finite set of strings $\sigma_1,\ldots,\sigma_k$.

Theorem 9.3   Let $Q$ be a nonempty thin recursively bounded $\Pi ^0_1$ set. Then $f\in 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)>\mathbf{0}$.

Lemma 9.4   Let $Q$ be a thin recursively bounded $\Pi ^0_1$ set. Then:

1. Every $\Pi ^0_1$ subset of $Q$ is thin and recursively bounded.
2. Let $P=\{\Phi(g)\mid g\in Q\}$ be the image of $Q$ under a recursive functional $\Phi:Q\to\omega^\omega$. Then $P$ is a thin recursively bounded $\Pi ^0_1$ set.

Theorem 9.5   If $Q$ is a thin recursively bounded $\Pi ^0_1$ set, then $Q$ is recursively homeomorphic to a thin $\Pi ^0_1$ set $Q^\ast\subseteq2^\omega$. Moreover, $Q$ is perfect if and only if $Q^\ast$ is perfect.

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

Remark 9.7   Let $\mathbf{q}=\deg_w(Q)$ where $Q$ is any nonempty thin perfect recursively bounded $\Pi ^0_1$ set. Obviously