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 $\mathbf{q}\in\mathcal{P}_w$. Let $\mathbf{r}=\deg_w(R)$ where $R=\{f\in2^\omega\mid f$ is random$\}$. We have seen in Theorem 8.10 that $\mathbf{r}\in\mathcal{P}_w$. Our goal in this section is to prove Theorem 9.15, which says that $\mathbf{q}$ and $\mathbf{r}$ are incomparable, i.e., $\mathbf{q}\not\le\mathbf{r}$ and $\mathbf{r}\not\le\mathbf{q}$. By Theorem 9.5, it suffices to prove this in the special case when $Q$ is a nonempty thin perfect $\Pi ^0_1$ subset of $2^\omega$.

Lemma 9.8   Let $Q$ be a thin $\Pi ^0_1$ subset of $2^\omega$. Then $\mu(Q)=0$.

Remark 9.9   We do not know the answer to the following question. If $Q$ is a thin perfect $\Pi ^0_1$ subset of $2^\omega$, does it follow that the Turing upward closure $\widehat{Q}=\{f\in2^\omega\mid(\exists g\le_Tf) (g\in Q)\}$ is of measure 0?

Lemma 9.10   Let $Q$ be a nonempty thin $\Pi ^0_1$ subset of $2^\omega$. If $f$ is random, and if $g\in Q$ is almost recursive, then $f\not\le_Tg$. In particular, $R\not\le_wQ$.

Lemma 9.11   Let $f\in2^\omega$ be random. If $g\le_{tt}f$ is nonrecursive, then there exists $\overline{f}\in2^\omega$ such that $\overline{f}\equiv_Tg$ and $\overline{f}$ is random.

Lemma 9.12   Let $f\in2^\omega$ be random and almost recursive. If $g\le_Tf$ is nonrecursive, then there exists $\overline{f}\in2^\omega$ such that $\overline{f}\equiv_Tg$ and $\overline{f}$ is random.

Lemma 9.13   Let $Q$ be a nonempty thin perfect $\Pi ^0_1$ subset of $2^\omega$. If $g\in Q$, and if $f\in2^\omega$ is random and almost recursive, then $g\not\le_Tf$. In particular $Q\not\le_wR$, and $Q\not\le_wP$ for all $\Pi ^0_1$ sets $P\subseteq2^\omega$ of positive measure.

Summarizing, we have:

Lemma 9.14   Let $f,g\in2^\omega$ be almost recursive. Assume that $f$ is random, and assume that $g\in Q$ where $Q$ is a thin perfect $\Pi ^0_1$ subset of $2^\omega$. Then $f\not\le_Tg$ and $g\not\le_Tf$, i.e., the Turing degrees of $f$ and $g$ are incomparable.

Theorem 9.15   Let $\mathbf{q}=\deg_w(Q)$ where $Q$ is a nonempty thin perfect $\Pi ^0_1$ subset of $2^\omega$. Let $\mathbf{r}=\deg_w(R)$ where $R=\{f\in2^\omega\mid f$ is random$\}$. Then $\mathbf{q}$ and $\mathbf{r}$ are incomparable weak degrees in $\mathcal{P}_w$.

Corollary 9.16   There exist $\mathbf{0}<\mathbf{q}<\mathbf{q}^\ast$ in $\mathcal{P}_w$ such that $\mathbf{q}$ is separating and $\mathbf{q}^\ast$ is not separating. Indeed, every separating $\mathbf{s}\in\mathcal{P}_w$ which is $\le\mathbf{q}^\ast$ is $\le\mathbf{q}$.

Some additional natural examples in $\mathcal{P}_w$

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

Definition 10.1   Put $\mathrm{DNR}=\{f\in\omega^\omega\mid\forall n (f(n)\ne\{n\}(n))\}$, the set of diagonally nonrecursive functions. The set of Turing degrees of members of $\mathrm{DNR}$ has been studied by Jockusch [25]. Note that $\mathrm{DNR}$ is nonempty and $\Pi ^0_1$. If $h:\omega\to\omega$ is a recursive function such that $h(n)\ge2$ for all $n$, put $\mathrm{DNR}_h=\{f\in\mathrm{DNR}\mid\forall n (f(n)<h(n))\}$, the set of $h$-bounded $\mathrm{DNR}$ functions. In addition, put $\mathrm{DNR}_\mathrm{REC}=\bigcup\{\mathrm{DNR}_h\mid h$ is recursive$\}$, the set of recursively bounded $\mathrm{DNR}$ functions.

Remark 10.2   Trivially

$$\mathrm{DNR} \supset \mathrm{DNR}_\mathrm{REC} \supset \mathrm{DNR}_h,$$

hence $\mathrm{DNR}\le_s\mathrm{DNR}_\mathrm{REC}\le_s\mathrm{DNR}_h$, hence $\mathrm{DNR}\le_w\mathrm{DNR}_\mathrm{REC}\le_w\mathrm{DNR}_h$. According to Ambos-Spies et al [2, Theorems 1.8 and 1.9], we have strict inequalities

$$\mathrm{DNR} <_w \mathrm{DNR}_\mathrm{REC} <_w \mathrm{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 $\mathrm{DNR}_h\le_wR$ provided $h$ is such that $\sum_{n=0}^\infty1/h(n)<\infty$, for example $h(n)=\max(n^2,2)$.

Remark 10.3   Since $\mathrm{DNR}_h$ is nonempty, recursively bounded, and $\Pi ^0_1$, we have $\deg_s(\mathrm{DNR}_h)\in\mathcal{P}_s$ and $\deg_w(\mathrm{DNR}_h)\in\mathcal{P}_w$. Although $\mathrm{DNR}$ and $\mathrm{DNR}_\mathrm{REC}$ are not recursively bounded, it will be shown in Simpson [48] that $\deg_w(\mathrm{DNR})\in\mathcal{P}_w$ and $\deg_w(\mathrm{DNR}_\mathrm{REC})\in\mathcal{P}_w$. We do not know whether $\deg_s(\mathrm{DNR})\in\mathcal{P}_s$, or whether $\deg_s(\mathrm{DNR}_\mathrm{REC})\in\mathcal{P}_s$. Put $\mathbf{d}=\deg_w(\mathrm{DNR})$, $\mathbf{d}_\mathrm{REC}=\deg_w(\mathrm{DNR}_\mathrm{REC})$, $\mathbf{d}_h=\deg_w(\mathrm{DNR}_h)$, $\mathbf{r}=\deg_w(R)$. Summarizing, we have the following result.

Theorem 10.4   In $\mathcal{P}_w$ we have

$$\mathbf{0} < \mathbf{d} < \mathbf{d}_\mathrm{REC} < \mathbf{d}_h < \mathbf{r} < \mathbf{1}$$

for all sufficiently fast-growing recursive functions $h:\omega\to\omega$.

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 $\mathbf{1}$, $\mathbf{r}$, $\mathbf{d}$ correspond to the systems $\mathsf{WKL}_0$, $\mathsf{WWKL}_0$, $\mathsf{RCA}_0+\mathrm{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 $\mathrm{DNR}$, $\mathrm{DNR}_\mathrm{REC}$, $\mathrm{DNR}_h$ and of their weak degrees $\mathbf{d}$, $\mathbf{d}_\mathrm{REC}$, $\mathbf{d}_h$. First, $\mathrm{DNR}$, $\mathrm{DNR}_\mathrm{REC}$, $\mathrm{DNR}_h$ are not invariant under recursive permutations of $\omega$, 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 $\mathbf{d}$, $\mathbf{d}_\mathrm{REC}$, $\mathbf{d}_h$, because all weak and strong degrees are invariant under recursive permutations of $\omega$. Second, one may note that our definitions of $\mathrm{DNR}$, $\mathrm{DNR}_\mathrm{REC}$, $\mathrm{DNR}_h$ and their weak degrees $\mathbf{d}$, $\mathbf{d}_\mathrm{REC}$, $\mathbf{d}_h$ depend upon a particular choice of Gödel numbering of Turing machines, because the function $n\mapsto\{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\mapsto\{n\}(n)$ by an arbitrary partial recursive function $n\mapsto\psi(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 $\mathrm{D}$ be the set of $g\in\omega^\omega$ such that for all partial recursive functions $\psi$ there exists $f\le_Tg$ such that $\forall n (f(n)\ne\psi(n))$. Let $\mathrm{D}_\mathrm{REC}$ be the set of $g\in\omega^\omega$ such that for all partial recursive functions $\psi$ there exists $f\le_Tg$ such that $\forall n (f(n)<h(n)$ and $f(n)\ne\psi(n))$ for some recursive function $h:\omega\to\omega$.

Remark 10.8   Using the S-m-n Theorem, it is easy to see that $\mathrm{DNR}\equiv_w\mathrm{D}$ and $\mathrm{DNR}_\mathrm{REC}\equiv_w\mathrm{D}_\mathrm{REC}$. (See also the proof of Theorem 10.10 below.) Thus the weak degrees $\mathbf{d}$ and $\mathbf{d}_\mathrm{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 $\mathbf{d}_h$ where $h$ is a fixed recursive function? Let $\mathrm{D}_h$ be the set of $g\in\omega^\omega$ such that for all partial recursive functions $\psi$ there exists $f\le_Tg$ such that $\forall n (f(n)<h(n)$ and $f(n)\ne\psi(n))$. It is not clear that $\mathrm{DNR}_h\equiv_w\mathrm{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 $\mathrm{DNR}_C=\bigcup_{h\in C}\mathrm{DNR}_h$. Let $\mathrm{D}_C$ be the set of $g\in\omega^\omega$ such that for all partial recursive functions $\psi$ there exists $f\le_Tg$ such that $\forall n (f(n)<h(n)$ and $f(n)\ne\psi(n))$ for some $h\in C$.

Theorem 10.10   If $C$ is closed under composition with primitive recursive functions, then $\mathrm{DNR}_C\equiv_w\mathrm{D}_C$. If there exists a uniform recursive enumeration of $C$, then $\deg_w(\mathrm{DNR}_C)\in\mathcal{P}_w$.

Theorem 10.11   Let $S$ be a $\Sigma^0_2$ subset of $2^\omega$. Then we can find a $\Pi ^0_1$ set $P\subseteq2^\omega$ such that $P$ is Turing degree isomorphic to $S$.

Remark 10.12   In the proof of Theorem 10.11, note that $\mathbf{p}=\inf_n\mathbf{p}_n$, where $\mathbf{p}=\deg_w(P)$ and $\mathbf{p}_n=\deg_w(P_n)$. Thus the proof shows that $\mathcal{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 $\mathbf{d}_C=\deg_w(\mathrm{DNR}_C)$. We have seen that $\mathbf{d}_C\in\mathcal{P}_w$ and that $\mathbf{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^\ast\supset C$ is another such class, then $\mathbf{d}_{C^\ast}\le\mathbf{d}_C$, and according to Ambos-Spies et al [2, Theorem 1.9] we have strict inequality $\mathbf{d}_{C^\ast}<\mathbf{d}_C$ provided $C^\ast$ 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 $\alpha$, let $C_\alpha$ be the class of recursive functions obtained at levels $<\omega\cdot(1+\alpha)$ 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 $\mathbf{d}_\alpha=\mathbf{d}_{C_\alpha}$ we have a transfinite descending sequence

$$\mathbf{d}_0>\mathbf{d}_1>\cdots> \mathbf{d}_\alpha>\mathbf{d}_{\alpha+1}>\cdots$$

in $\mathcal{P}_w$. Moreover, if $\alpha$ is a limit ordinal, then $\mathbf{d}_\alpha=\inf_{\beta<\alpha}\mathbf{d}_\beta$. Thus we see a rich set of natural degrees in $\mathcal{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\in C$ and $c\ge1$ there exists $h^\ast_c\in C$ such that $h^\ast_c(n)\ge h(m)$ for all $m\le c\cdot(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 $\mathbf{d}_C\in\mathcal{P}_w$ is natural in that its definition does not depend on the choice of a standard Gödel numbering.

Example 10.16   In $\mathcal{P}_w$ we have

$$\mathbf{d}_\mathrm{PTIME}>\mathbf{d}_\mathrm{EXPTIME}>\cdots$$

etc. Thus we see a rich set of natural degrees in $\mathcal{P}_w$ which are related to computational complexity.

Bibliography

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 $\Pi ^0_1$ 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 $\Pi ^0_1$ classes.
Archive for Mathematical Logic, 45:393-410, 2006.

6

Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of $\Pi ^0_1$ 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 $\Pi ^0_1$ classes.
Archive for Mathematical Logic, 42:583-600, 2003.

10

Douglas Cenzer and Jeffrey B. Remmel.
$\Pi ^0_1$ classes in mathematics.
In [20], pages 623-821, 1998.

11

Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann.
Automorphisms of the lattice of $\Pi ^0_1$ 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.
$\Pi ^0_1$ 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 Kucera.
Measure, $\Pi ^0_1$ classes and complete extensions of PA.
In [19], pages 245-259, 1985.

30

Antonín Kucera.
An alternative, priority-free, solution to Post's problem.
In [24], pages 493-500, 1986.

31

Antonín Kucera.
On the role of $\mathbf{0'}$ in recursion theory.
In [17], pages 133-141, 1988.

32

Antonín Kucera.
On the use of diagonally nonrecursive functions.
In [18], pages 219-239, 1989.

33

Antonín Kucera.
Randomness and generalizations of fixed point free functions.
In [1], pages 245-254, 1990.

34

Antonín Kucera.
On relative randomness.
Annals of Pure and Applied Logic, 63:61-67, 1993.

35

Antonín Kucera 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$\verb\vert^\vert$0$\verb\vert _\vert$1 subsets of 2$\verb\vert^\vert$omega.
COMP-THY e-mail list [12], June 9, 2000.

54

Stephen G. Simpson.
$\Pi ^0_1$ sets and models of $\mathsf{WKL}_0$.
In [47], pages 352-378. 2005.

55

Stephen G. Simpson and Theodore A. Slaman.
Medvedev degrees of $\Pi ^0_1$ subsets of $2^\omega$.
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.

About this document ...

Mass Problems and Randomness

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 massrand

The translation was initiated by Stephen G Simpson on 2007-09-28