An extension of the
recursively enumerable Turing degrees

Stephen G. Simpson

Department of Mathematics

August 10, 2004

Pennsylvania State University

This research was partially supported by NSF grant DMS-0070718.

AMS Subject Classifications: 03D25, 03D30, 68Q30.

Journal of the London Mathematical Society, 75, 2007, pp. 287-297.

Abstract:

Consider the countable semilattice $\mathcal{R}_T$ consisting of the recursively enumerable Turing degrees. Although $\mathcal{R}_T$ is known to be structurally rich, a major source of frustration is that no specific, natural degrees in $\mathcal{R}_T$ have been discovered, except the bottom and top degrees, $\mathbf{0}$ and $\mathbf{0}'$. In order to overcome this difficulty, we embed $\mathcal{R}_T$ into a larger degree structure which is better behaved. Namely, consider the countable distributive lattice $\mathcal{P}_w$ consisting of the weak degrees (a.k.a., Muchnik degrees) of mass problems associated with nonempty $\Pi^0_1$ subsets of $2^\omega$. It is known that $\mathcal{P}_w$ contains a bottom degree $\mathbf{0}$ and a top degree $\mathbf{1}$ and is structurally rich. Moreover, $\mathcal{P}_w$ contains many specific, natural degrees other than $\mathbf{0}$ and $\mathbf{1}$. In particular, we show that in $\mathcal{P}_w$ one has $\mathbf{0}<\mathbf{d}<\mathbf{r}_1<\inf(\mathbf{r}_2,\mathbf{1})<\mathbf{1}$. Here $\mathbf{d}$ is the weak degree of the diagonally nonrecursive functions, and $\mathbf{r}_n$ is the weak degree of the $n$-random reals. It is known that $\mathbf{r}_1$ can be characterized as the maximum weak degree of a $\Pi^0_1$ subset of $2^\omega$ of positive measure. We now show that $\inf(\mathbf{r}_2,\mathbf{1})$ can be characterized as the maximum weak degree of a $\Pi^0_1$ subset of $2^\omega$ whose Turing upward closure is of positive measure. We exhibit a natural embedding of $\mathcal{R}_T$ into $\mathcal{P}_w$ which is one-to-one, preserves the semilattice structure of $\mathcal{R}_T$, carries $\mathbf{0}$ to $\mathbf{0}$, and carries $\mathbf{0}'$ to $\mathbf{1}$. Identifying $\mathcal{R}_T$ with its image in $\mathcal{P}_w$, we show that all of the degrees in $\mathcal{R}_T$ except $\mathbf{0}$ and $\mathbf{1}$ are incomparable with the specific degrees $\mathbf{d}$, $\mathbf{r}_1$, and $\inf(\mathbf{r}_2,\mathbf{1})$ in $\mathcal{P}_w$.

Contents

• Introduction
• Background: $\mathcal{R}_T$ and $\mathcal{P}_w$
• Some specific degrees in $\mathcal{P}_w$
• Some additional, specific degrees in $\mathcal{P}_w$
• Embedding $\mathcal{R}_T$ into $\mathcal{P}_w$
• Bibliography

Introduction

A principal object of study in recursion theory going back to the seminal work of Turing [36] and Post [25] has been the countable upper semilattice $\mathcal{R}_T$ of recursively enumerable Turing degrees, i.e., Turing degrees of recursively enumerable sets of positive integers. See the monographs of Sacks [27], Rogers [26], Soare [35], and Odifreddi [22,23].

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 examples originally 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 paucity of examples in $\mathcal{R}_T$ is striking, because it is widely recognized that most other branches of mathematics are motivated and nurtured by a rich stock of examples. Clearly it ought to be of interest to somehow overcome this deficiency in the study of $\mathcal{R}_T$.

In 1999 [30,31] we defined a degree structure, here denoted $\mathcal{P}_w$, which is closely related to $\mathcal{R}_T$, but superior to $\mathcal{R}_T$ in at least two respects. First, $\mathcal{P}_w$ exhibits better structural behavior than $\mathcal{R}_T$, in the sense that $\mathcal{P}_w$ is a countable distributive lattice, while $\mathcal{R}_T$ is not even a lattice. Second and more importantly, there are plenty of specific, natural degrees in $\mathcal{P}_w$ which are intermediate between $\mathbf{1}$ and $\mathbf{0}$, the top and bottom elements of $\mathcal{P}_w$. Thus $\mathcal{P}_w$ does not suffer from the above-mentioned lack of examples, which plagues $\mathcal{R}_T$.

In more detail, let $\mathcal{P}_w$ be the lattice of weak degrees (a.k.a., Muchnik degrees) of mass problems given by nonempty $\Pi^0_1$ subsets of $2^\omega$. In 1999 [30] we showed that among the intermediate degrees in $\mathcal{P}_w$ is the specific degree $\mathbf{r}_1$ associated with the set of $1$-random reals. The concept of $1$-randomness was already well known from algorithmic information theory [19]. After 1999, we and other authors [2,3,4,5,32,33,34] continued the study of $\mathcal{P}_w$, using priority arguments to prove structural properties, just as for $\mathcal{R}_T$. In addition, we [33] discovered families of specific, natural, intermediate degrees in $\mathcal{P}_w$ related to foundationally interesting topics such as reverse mathematics, Gentzen-style proof theory, and computational complexity. Some additional degrees of this kind are presented in Sections 3 and 4 below.

The purpose of the present paper is to further clarify the relationship between the semilattice $\mathcal{R}_T$ and the lattice $\mathcal{P}_w$. Namely, we exhibit a specific, natural embedding $\phi:\mathcal{R}_T\to\mathcal{P}_w$ which is one-to-one, preserves the semilattice structure of $\mathcal{R}_T$, and carries the top and bottom elements of $\mathcal{R}_T$ to the top and bottom elements of $\mathcal{P}_w$. See Theorem 5.5 below. By identifying $\mathcal{R}_T$ with its image in $\mathcal{P}_w$, we place the recursively enumerable Turing degrees into a wider context, where natural intermediate degrees occur. We view this as a step toward overcoming the above-mentioned difficulties concerning $\mathcal{R}_T$.

At the same time, our embedding of $\mathcal{R}_T$ into $\mathcal{P}_w$ fails to solve the long standing open problem of finding a specific, natural, intermediate degree within $\mathcal{R}_T$ itself. Indeed, we shall see below (Theorem 5.6) that, regrettably, all of the intermediate degrees belonging to the image of $\mathcal{R}_T$ under our embedding are incomparable with all of the known natural intermediate degrees in $\mathcal{P}_w$.

Background: $\mathcal{R}_T$ and $\mathcal{P}_w$

In this section we review some basic information concerning the semilattice $\mathcal{R}_T$ and the lattice $\mathcal{P}_w$.

Throughout this paper we shall use standard recursion-theoretic notation from Rogers [26] and Soare [35]. For special aspects of mass problems and $\Pi^0_1$ sets, a convenient reference is [33].

We write $\omega=\{0,1,2,\dots\}$ for the set of natural numbers, $\omega^\omega$ for the space of total functions from $\omega$ into $\omega$, and $2^\omega$ for the space of 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$. In the absence of an oracle $f$, we write $\{e\}(n)=m$. 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$. A function $h:\omega\to\omega$ is said to be recursive if there exists $e\in\omega$ such that $h(n)=\{e\}(n)$ for all $n\in\omega$. 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$\}$. Within $\mathcal{D}_T$, the least upper bound of $\deg_T(f)$ and $\deg_T(g)$ is $\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$. A Turing degree $\mathbf{a}$ is said to be recursively enumerable if $\mathbf{a}=\deg_T(\chi_A)$ where $A\subseteq\omega$ is recursively enumerable. The set of all recursively enumerable Turing degrees is denoted $\mathcal{R}_T$. It is easy to see that $\mathcal{R}_T$ is closed under the least upper bound operation inherited from $\mathcal{D}_T$. The top and bottom elements of $\mathcal{R}_T$ are $\mathbf{0}'$ and $\mathbf{0}$ respectively, where $\mathbf{0}'=\deg_T(H)$ is the Turing degree of the Halting Problem, $H=\{e\mid\exists m (\{e\}(0)=m)\}$. Thus $\mathcal{R}_T$ is a countable upper semilattice with a top and bottom element.

Definition 2.1   Let $P,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$. 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$. The concept of weak reducibility goes back to Muchnik [21] and has sometimes been called Muchnik reducibility.

Theorem 2.2   $\mathcal{D}_w$ is a complete distributive lattice.

Proof.The least upper bound of $\deg_w(P)$ and $\deg_w(Q)$ in $\mathcal{D}_w$ is $\deg_w(P\times Q)$ where

$$P\times Q=\{f\oplus g\mid f\in P\mbox{ and }g\in Q\}.$$

The greatest lower bound of $\deg_w(P)$ and $\deg_w(Q)$ in $\mathcal{D}_w$ is $\deg_w(P\cup Q)$. The bottom element of $\mathcal{D}_w$ is

$\mathbf{0}=\{P\subseteq\omega^\omega\mid\exists f (f\in P$ and $f$ is recursive$)\}$.

Note that $P\le_w Q$ if and only if $\widehat{P}\supseteq\widehat{Q}$, where $\widehat{P}$ is the Turing upward closure of $P$,

$$\widehat{P}=\{g\in\omega^\omega\mid(\exists f\in P) (f\le_Tg)\}.$$

Thus the lattice of weak degrees, $\mathcal{D}_w$, is inversely isomorphic to the lattice of subsets of $\omega^\omega$ which are upward closed with respect to $\le_T$. It follows that $\mathcal{D}_w$ is a complete distributive lattice.$\Box$

Remark 2.3   There is an obvious, natural embedding of $\mathcal{D}_T$ into $\mathcal{D}_w$ given by $\deg_T(f)\mapsto\deg_w(\{f\})$. Here $\{f\}$ is the singleton set whose only member is $f$. This embedding is one-to-one, preserves the partial ordering relation and least upper bound operation from $\mathcal{D}_T$, and carries $\mathbf{0}$ to $\mathbf{0}$. Compare this with our embedding of $\mathcal{R}_T$ into $\mathcal{P}_w$ in Theorem 5.5 below.

Definition 2.4   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)\}$. A set $S\subseteq\omega^\omega$ is said to be $\Sigma^0_3$ if there exists a recursive predicate $R\subseteq\omega^\omega\times\omega\times\omega\times\omega$ such that $S=\{f\mid\exists k \forall m \exists n R(f,k,m,n)\}$. Other levels of the arithmetical hierarchy are defined similarly.

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

Definition 2.6   For $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 recursive. In this case we say that $P$ and $Q$ are recursively homeomorphic.

Theorem 2.7   $P\subseteq\omega^\omega$ is recursively bounded $\Pi^0_1$ if and only if $P$ is recursively homeomorphic to a $\Pi^0_1$ set $P^\ast\subseteq2^\omega$.

Proof.See [33, Theorems 4.7 and 4.10].$\Box$

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

Proof.This is immediate from Theorem 2.7.$\Box$

Definition 2.9   $\mathcal{P}_w$ is the set of weak degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$.

Theorem 2.10   $\mathcal{P}_w$ is a countable distributive lattice with a top and bottom element, denoted $\mathbf{1}$ and $\mathbf{0}$ respectively.

Proof.If $P$ and $Q$ are $\Pi^0_1$ subsets of $2^\omega$, then so are $P\times Q$ and $P\cup Q$. Thus $\mathcal{P}_w$ is closed under the least upper bound and greatest lower bound operations inherited from $\mathcal{D}_w$. Clearly $\mathcal{P}_w$ is countable, because there are only countably many $\Pi^0_1$ subsets of $2^\omega$. Clearly $\mathbf{0}=\deg_w(2^\omega)$ is the bottom element of $\mathcal{P}_w$. Let $\mathrm{PA}$ be the set of completions of Peano Arithmetic. Identifying sentences with their Gödel numbers, we may view $\mathrm{PA}$ as a $\Pi^0_1$ subset of $2^\omega$. By Scott [29], $\deg_w(\mathrm{PA})=\mathbf{1}$ is the top element of $\mathcal{P}_w$. See also [33, Section 6].$\Box$

Remark 2.11   Just like the countable semilattice $\mathcal{R}_T$, the countable distributive lattice $\mathcal{P}_w$ is known to be structurally rich. Binns/Simpson [2,5] have shown that every countable distributive lattice is lattice embeddable in every nontrivial initial segment of $\mathcal{P}_w$. Binns [2,3] has obtained the $\mathcal{P}_w$ analog of the Sacks Splitting Theorem for $\mathcal{R}_T$ [27]. Namely, for all $\mathbf{p},\mathbf{q}>\mathbf{0}$ in $\mathcal{P}_w$ there exist $\mathbf{q}_1,\mathbf{q}_2\in\mathcal{P}_w$ such that $\mathbf{q}_1,\mathbf{q}_2\not\ge\mathbf{p}$ and $\sup(\mathbf{q}_1,\mathbf{q}_2)=\mathbf{q}$. (The $\mathcal{P}_w$ analog of the Sacks Density Theorem for $\mathcal{R}_T$ [28] remains as an open problem.) These structural results for $\mathcal{P}_w$ are proved by means of priority arguments. They invite comparison with the older, known results for $\mathcal{R}_T$, which were also proved by means of priority arguments.

We end this section by mentioning some technical notions and results concerning trees and almost recursiveness.

A finite sequence of natural numbers $\sigma=\langle\sigma(0),\ldots,\sigma(k-1)\rangle$ is called a string of length $k$. The set of all strings is denoted $\omega^{<\omega}$. The set of strings of $0$'s and $1$'s is denoted $2^{<\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$. We write $\sigma\subseteq\tau$ if $\sigma{{}^\smallfrown}\rho=\tau$ for some $\rho$. 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$. We write $\sigma\subset f$ 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.

Theorem 2.12   $P\subseteq\omega^\omega$ is $\Pi^0_1$ if and only if $P=[T]$ for some recursive tree $T\subseteq\omega^{<\omega}$. $P\subseteq2^\omega$ is $\Pi^0_1$ if and only if $P=[T]$ for some recursive tree $T\subseteq2^{<\omega}$.

Proof.See [33, Theorem 4.3].$\Box$

Definition 2.13   We say that $g\in\omega^\omega$ is almost recursive if for all $f\le_Tg$ there exists a recursive function $h$ such that $\forall n (f(n)<h(n))$.

Theorem 2.14   Suppose $g$ is almost recursive. Then for all $f\le_Tg$ we have $f=\Phi(g)$ for some total recursive functional $\Phi:\omega^\omega\to\omega^\omega$.

Proof.See [33, Theorem 4.18].$\Box$

The following result is known as the Almost Recursive Basis Theorem.

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

Proof.This is a restatement of the Hyperimmune-Free Basis Theorem of [15, Theorem 2.4]. See also [33, Theorem 4.19].$\Box$

Some specific degrees in $\mathcal{P}_w$

In this section we identify and characterize some specific, natural degrees in $\mathcal{P}_w$, and we investigate their degree-theoretic properties.

Definition 3.1   Let $\mu$ be the ``fair coin'' probability measure on $2^\omega$ given by $\mu(\{f\in2^\omega\mid f\supset\sigma\})=1/2^{\vert\sigma\vert}$ for all $\sigma\in2^{<\omega}$. Let $C$ be a Turing oracle. A point $f\in2^\omega$ is said to be $C$-random if there does not exist a recursive sequence of $\Sigma^{0,C}_1$ sets $U^C_i\subseteq2^\omega$, $i\in\omega$, such that $\mu(U^C_i)\le1/2^i$ and $f\in\bigcap_{i=0}^\infty U^C_i$. If $C=0^{(n-1)}=$ the $(n{-}1)$st Turing jump of $0$, where $0$ is recursive and $n\ge1$, then $f$ is said to be $n$-random.

Thus $f$ is $1$-random if and only if $f$ is random in the sense of Martin-Löf [20], and $f$ is $2$-random if and only if $f$ is random relative to the Halting Problem. For a thorough treatment of randomness and $n$-randomness, see Kautz [16] or Downey/Hirschfeldt [8]. We write

$R_n=\{f\in2^\omega\mid f$ is $n$-random$\}$. Note that $\mu(R_n)=1$.

Lemma 3.2   $R_n$ is $\Sigma^0_{n+1}$. In particular, $R_1$ is $\Sigma^0_2$, and $R_2$ is $\Sigma^0_3$.

Proof.It is is well known (see for instance [33, Theorem 8.3]) that $R=R_1$ is $\Sigma^0_2$. Relativizing to $C$ we see that $R^C=\{f\in2^\omega\mid f$ is $C$-random$\}$ is $\Sigma^{0,C}_2$, i.e., $\Sigma^0_2$ relative to $C$. Putting $C=0^{(n-1)}$, we see that $R_n$ is $\Sigma^0_2$ relative to $0^{(n-1)}$. From this it follows easily that $R_n$ is $\Sigma^0_{n+1}$.$\Box$

Lemma 3.3   Let $S\subseteq\omega^\omega$ be $\Sigma^0_3$, and let $P\subseteq2^\omega$ be nonempty $\Pi^0_1$. Then we can find a nonempty $\Pi^0_1$ set $Q\subseteq2^\omega$ such that $Q\equiv_wS\cup P$.

Proof.First use a Skolem function technique to reduce to the case where $S$ is $\Pi^0_1$. Namely, fix a recursive predicate $R$ such that $S=\{f\mid\exists k \forall n \exists m R(f,k,n,m)\}$, and replace $S$ by the set of all $\langle k\rangle{{}^\smallfrown}(f\oplus g)\in\omega^\omega$ such that $\forall n R(f,k,n,g(n))$ holds. Clearly the latter set is $\equiv_w S$ and $\Pi^0_1$. Assuming now that $S$ is a $\Pi^0_1$ subset of $\omega^\omega$, let $T_S$ be a recursive subtree of $\omega^{<\omega}$ such that $S$ is the set of paths through $T_S$. We may safely assume that, for all $\tau\in T_S$ and $n<$ the length of $\tau$, $\tau(n)\ge2$. Let $T_P$ be a recursive subtree of $2^{<\omega}$ such that $P$ is the set of paths through $T_P$. Define $T_Q$ to be the set of strings $\rho\in\omega^{<\omega}$ of the form

$$\rho=\sigma_0{{}^\smallfrown}\langle m_0\rangle{{}^\smallfr... ...{}^\smallfrown}\langle m_{k-1}\rangle{{}^\smallfrown}\sigma_k$$

where $\langle m_0,m_1,\ldots,m_{k-1}\rangle\in T_S$, $\sigma_0,\sigma_1,\ldots,\sigma_k\in T_P$, and $\rho(n)\le\max(n,2)$ for all $n<$ the length of $\rho$. Thus $T_Q$ is a recursive subtree of $\omega^{<\omega}$. Let $Q\subseteq\omega^\omega$ be the set of paths through $T_Q$. (Compare the construction of $\mathcal{T}$ in Jockusch/Soare [14].) It is straightforward to verify that $Q\equiv_wS\cup P$. Note that $Q$ is $\Pi^0_1$ and recursively bounded. By Theorem 2.7 we can find a $\Pi^0_1$ set $Q^\ast\subseteq2^\omega$ which is recursively homeomorphic to $Q$. This completes the proof.$\Box$

Lemma 3.4   There exist $\Pi^0_1$ sets $P_1,P_2\subseteq2^\omega$ such that $P_1\equiv_wR_1$ and

$$P_2\equiv_wR_2\cup\mathrm{PA}.$$

Proof.By Lemmas 3.2 and 3.3 we can find $\Pi^0_1$ sets $P_1,P_2\subseteq2^\omega$ such that $P_1\equiv_wR_1\cup\mathrm{PA}$ and $P_2\equiv_wR_2\cup\mathrm{PA}$. Since $R_1$ is nonempty and $\Sigma^0_2$, there is a nonempty $\Pi^0_1$ set $Q\subseteq R_1$. Then $Q\le_w\mathrm{PA}$, hence $R_1\le_w\mathrm{PA}$, hence $P_1\equiv_wR_1\cup\mathrm{PA}\equiv_wR_1$.$\Box$

Definition 3.5   We write $\mathbf{r}_n=\deg_w(R_n)$ and

$$\mathbf{r}_n^\ast=\inf(\mathbf{r}_n,\mathbf{1})=\deg_w(R_n\cup\mathrm{PA}).$$

Theorem 3.6   We have $\mathbf{r}_1\in\mathcal{P}_w$ and $\mathbf{r}_2^\ast\in\mathcal{P}_w$ and $\mathbf{0}<\mathbf{r}_1<\mathbf{r}_2^\ast<\mathbf{1}$.

Proof.By Lemma 3.4 there are $\Pi^0_1$ sets $P_1,P_2\subseteq2^\omega$ such that $\mathbf{r}_1=\deg_w(P_1)$ and $\mathbf{r}_2^\ast=\deg_w(P_2)$. Thus $\mathbf{r}_1,\mathbf{r}_2^\ast\in\mathcal{P}_w$ and $\mathbf{r}_1,\mathbf{r}_2^\ast\le\mathbf{1}$. Clearly $R_1\supseteq R_2$, hence $\mathbf{r}_1\le\mathbf{r}_2$. Clearly $R_1$ has no recursive member, i.e., $\mathbf{r}_1>\mathbf{0}$. By [33, Section 7] or [15, Corollary 5.4], the Turing upward closure of $\mathrm{PA}$ is of measure $0$, i.e., $\mathrm{PA}\not\le_wS$ for all $S\subseteq2^\omega$ of positive measure. In particular $\mathrm{PA}\not\le_wR_2$, i.e., $\mathbf{1}\not\le\mathbf{r}_2$. Summarizing, we have now shown that $\mathbf{0}<\mathbf{r}_1\le\inf(\mathbf{r}_2,\mathbf{1})=\mathbf{r}_2^\ast<\mathbf{1}$.

It remains to show that $\mathbf{r}_1\not\ge\mathbf{r}_2^\ast$, i.e., $R_1\not\ge_wR_2\cup\mathrm{PA}$. By Lemma 3.2, let $P$ be a nonempty $\Pi^0_1$ subset of $R_1$. By the Almost Recursive Basis Theorem 2.15, let $g\in P$ be almost recursive. By Kautz [16, Theorem IV.2.4(iv)] or Dobrinen/Simpson [7, Remark 2.8], there is no almost recursive $f\in R_2$. In particular, there is no $f\in R_2$ such that $f\le_Tg$. Suppose there were $f\in\mathrm{PA}$ such that $f\le_Tg$. By Theorem 2.14 let $\Phi:2^\omega\to2^\omega$ be a total recursive functional such that $f=\Phi(g)$. Put $\overline{P}=\{\overline{g}\in P\mid\Phi(\overline{g})\in\mathrm{PA}\}$. We have $\Phi(g)=f\in\mathrm{PA}$, hence $g\in\overline{P}$, hence $\overline{P}$ is nonempty. Since $P$ and $\mathrm{PA}$ are $\Pi^0_1$, it follows by [33, Theorem 4.4] that $\overline{P}\subseteq P\subseteq R_1$ is $\Pi^0_1$. Hence, by [33, Lemma 8.8], $\overline{P}$ is of positive measure. Since $\Phi:\overline{P}\to\mathrm{PA}$, it follows that the Turing upward closure of $\mathrm{PA}$ is of positive measure, but this is a contradiction. We have now shown that, for a particular $g\in R_1$, there is no $f\le_Tg$ such that $f\in R_2\cup\mathrm{PA}$. Thus $R_2\cup\mathrm{PA}\not\le_wR_1$, and this completes the proof.$\Box$

Remark 3.7   As an application of Theorem 3.6, we can find essentially undecidable, finitely axiomatizable theories $T_1$ and $T_2$ in the first-order predicate calculus, with the following properties: every $1$-random real computes a completion of $T_1$; every $2$-random real but not every $1$-random real computes a completion of $T_2$. This follows from Theorem 3.6 plus the well known, general relationship between $\Pi^0_1$ subsets of $2^\omega$ and finitely axiomatizable theories. See [32, Theorem 3.18 and Remark 3.19] and Peretyatkin [24].

Theorem 3.8   We can characterize $\mathbf{r}_1$ as the maximum weak degree of a $\Pi^0_1$ subset of $2^\omega$ of positive measure. We can characterize $\mathbf{r}_2^\ast$ as the maximum weak degree of a $\Pi^0_1$ subset of $2^\omega$ whose Turing upward closure is of positive measure.

Proof.The first statement is [33, Theorem 8.10]. For the second statement, assume that $Q$ is a $\Pi^0_1$ subset of $2^\omega$ whose Turing upward closure $\widehat{Q}$ is of positive measure. A computation in the style of Tarski and Kuratowski (compare Rogers [26, Section 14.3]) shows that $\widehat{Q}$ is $\Sigma^0_3$. Since $\widehat{Q}$ is $\Sigma^0_3$ of positive measure, let $Q'\subseteq\widehat{Q}$ be $\Pi^0_2$ of positive measure. By Kautz [16, Lemma II.1.4(ii)] or Dobrinen/Simpson [7, Theorem 3.3], we may assume that $Q'$ is $\Pi^0_1$ relative to $\mathbf{0}'$. Relativizing [33, Lemma 8.7] to $\mathbf{0}'$, we have $Q'\le_wR_2$. Since $Q'\subseteq\widehat{Q}$, it follows that $\widehat{Q}\le_wR_2$, hence $Q\le_wR_2$. Furthermore, since $Q$ is a nonempty $\Pi^0_1$ subset of $2^\omega$, we have $Q\le_w\mathrm{PA}$. We now see that $Q\le_wR_2\cup\mathrm{PA}$, i.e., $\deg_w(Q)\le\mathbf{r}_2^\ast$. On the other hand, by Theorem 3.6 let $P_2$ be a $\Pi^0_1$ subset of $2^\omega$ such that $\deg_w(P_2)=\mathbf{r}_2^\ast$. Note that $\widehat{P_2}\supseteq R_2$, hence $\widehat{P_2}$ is of positive measure. We have now shown that $\mathbf{r}_2^\ast$ is the maximum $\deg_w(Q)\in\mathcal{P}_w$ such that $\widehat{Q}$ is of positive measure. This completes the proof of our theorem.$\Box$

Corollary 3.9   Let $Q$ be a nonempty $\Pi^0_1$ subset of $2^\omega$. Then $Q\le_wR_2$ if and only if $\widehat{Q}$ is of positive measure.

Proof.If $Q\le_wR_2$ then trivially $\widehat{Q}\supseteq R_2$, hence $\widehat{Q}$ is of measure $1$. Conversely, if $\widehat{Q}$ is of positive measure, then by Theorem 3.8 we have $Q\le_wR_2$.$\Box$

Corollary 3.10   We can find a $\Pi^0_1$ set $Q\subseteq2^\omega$ whose Turing upward closure $\widehat{Q}$ is of positive measure yet does not include any $\Pi^0_1$ set of positive measure.

Proof.By Theorem 3.6 let $Q\subseteq2^\omega$ be $\Pi^0_1$ such that $\deg_w(Q)=\mathbf{r}_2^\ast$. By Theorem 3.8, $\widehat{Q}$ is of positive measure. If there were a $\Pi^0_1$ set $P\subseteq\widehat{Q}$ of positive measure, then by Theorem 3.8 we would have $\mathbf{r}_1\ge\deg_w(P)\ge\deg_w(Q)=\mathbf{r}_2^\ast$, contradicting Theorem 3.6.$\Box$

Theorem 3.11   Let $\mathbf{p},\mathbf{q}\in\mathcal{P}_w$. If $\mathbf{r}_1\ge\inf(\mathbf{p},\mathbf{q})$ then either $\mathbf{r}_1\ge\mathbf{p}$ or $\mathbf{r}_1\ge\mathbf{q}$. If $\mathbf{r}_2^\ast\ge\inf(\mathbf{p},\mathbf{q})$ then either $\mathbf{r}_2^\ast\ge\mathbf{p}$ or $\mathbf{r}_2^\ast\ge\mathbf{q}$.

Proof.The first statement is [33, Theorem 8.12, part 3]. For the second statement, let $P,Q\subseteq2^\omega$ be nonempty $\Pi^0_1$ subsets of $2^\omega$ with $\mathbf{p}=\deg_w(P)$ and $\mathbf{q}=\deg_w(Q)$. Trivially $\inf(\mathbf{p},\mathbf{q})=\deg_w(P\cup Q)$. Moreover $\widehat{P\cup Q}=\widehat{P}\cup\widehat{Q}$, hence $\widehat{P\cup Q}$ is of positive measure if and only if at least one of $\widehat{P}$ and $\widehat{Q}$ is of positive measure. By Corollary 3.9 this means that $\mathbf{r}_2^\ast\ge\inf(\mathbf{p},\mathbf{q})$ if and only if $\mathbf{r}_2^\ast\ge$ at least one of $\mathbf{p}$ and $\mathbf{q}$.$\Box$

Definition 3.12   As in [33, Section 7], say that $\mathbf{s}\in\mathcal{P}_w$ is separating if there is a pair of disjoint, recursively enumerable sets $A,B\subseteq\omega$ such that $\mathbf{s}=\deg_w(S)$ where $S=\{f\in2^\omega\mid f$ separates $A,B\}$. In particular, $\mathbf{1}$ is separating.

Theorem 3.13   If $\mathbf{s}$ is separating and $\mathbf{s}\le\sup(\mathbf{q},\mathbf{r}_n)$, then $\mathbf{s}\le\mathbf{q}$.

Proof.This is a special case of [33, Theorem 7.5].$\Box$

Corollary 3.14   For all weak degrees $\mathbf{q}<\mathbf{1}$, we have $\sup(\mathbf{q},\mathbf{r}_2^\ast)<\mathbf{1}$.

Proof.Assume $\mathbf{q}<\mathbf{1}$. By the definition of $\mathbf{r}_2^\ast$, we have $\mathbf{r}_2^\ast\le\mathbf{1}$, hence $\sup(\mathbf{q},\mathbf{r}_2^\ast)\le\mathbf{1}$. Since $\mathbf{1}$ is separating and $\mathbf{q}\not\ge\mathbf{1}$, Theorem 3.13 tells us that $\sup(\mathbf{q},\mathbf{r}_2)\not\ge\mathbf{1}$, hence $\sup(\mathbf{q},\mathbf{r}_2^\ast)\not\ge\mathbf{1}$.$\Box$

Corollary 3.15   Within the lattice $\mathcal{P}_w$, the degrees $\mathbf{r}_1$ and $\mathbf{r}_2^\ast$ are meet-irreducible and do not join to $\mathbf{1}$.

Proof.This follows from Theorem 3.11 and Corollary 3.14.$\Box$

Some additional, specific degrees in $\mathcal{P}_w$

In this section we identify some additional specific, natural, intermediate degrees in $\mathcal{P}_w$ related to diagonal nonrecursiveness.

Definition 4.1   A function $g:\omega\to\omega$ is said to be diagonally nonrecursive if $g(n)\ne\{n\}(n)$ for all $n\in\omega$. We put $\mathbf{d}=\deg_w(\mathrm{DNR})$ where

$\mathrm{DNR}=\{g\in\omega^\omega\mid g$ is diagonally nonrecursive$\}$. The Turing degrees of diagonally nonrecursive functions have been studied by Jockusch [12]. In particular, a Turing degree contains a diagonally nonrecursive function if and only if it contains a fixed point free function, if and only if it contains an effectively immune set, if and only if it contains an effectively biimmune set. Thus we see that the weak degree $\mathbf{d}$ is recursion-theoretically natural.

Theorem 4.2   We have $\mathbf{d}\in\mathcal{P}_w$.

Proof.Put $\mathrm{DNR}_2=\{g\in2^\omega\mid g$ is diagonally nonrecursive$\}$. Obviously $\mathrm{DNR}_2$ is a nonempty $\Pi^0_1$ subset of $2^\omega$. By Lemma 3.3 we can find a nonempty $\Pi^0_1$ set $Q\subseteq2^\omega$ such that $Q\equiv_w\mathrm{DNR}\cup\mathrm{DNR}_2$. But $\mathrm{DNR}\supseteq\mathrm{DNR}_2$, hence $Q\equiv_w\mathrm{DNR}$. We now see that $\mathbf{d}=\deg_w(\mathrm{DNR})=\deg_w(Q)\in\mathcal{P}_w$.$\Box$

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

$$\mathbf{0}<\mathbf{d}<\mathbf{r}_1<\mathbf{r}_2^\ast<\mathbf{1}.$$

Proof.By Theorem 3.6 we have $\mathbf{0}<\mathbf{r}_1<\mathbf{r}_2^\ast<\mathbf{1}$. Clearly $\mathrm{DNR}$ has no recursive member, i.e., $\mathbf{d}>\mathbf{0}$. By Giusto/Simpson [11, Lemma 6.18], for all $f\in R_1$ there exists $g\le_Tf$ such that $g\in\mathrm{DNR}$. Thus we have $\mathbf{0}<\mathbf{d}\le\mathbf{r}_1$. It remains to show that $\mathbf{d}\not\ge\mathbf{r}_1$. By Kumabe [18] there is a diagonally nonrecursive function which is of minimal Turing degree. But if $f\in2^\omega$ is $1$-random, then $f$ is not of minimal Turing degree, because the functions $g$ and $h$ defined by $f=g\oplus h$ are Turing incomparable (see for instance van Lambalgen [37]). This proves $\mathbf{d}\not\ge\mathbf{r}_1$. An alternative reference for the conclusion $\mathbf{d}\not\ge\mathbf{r}_1$ is Ambos-Spies et al [1, Theorems 1.4 and 2.1].$\Box$

Definition 4.4   Let $\mathrm{DNR}_\mathrm{REC}$ be the set of recursively bounded $\mathrm{DNR}$ functions. Thus we have

$$\mathrm{DNR}_\mathrm{REC}=\{g\in\mathrm{DNR}\mid(\exists\mbox{ recursive }h) \forall n (g(n)<h(n))\}.$$

Put $\mathbf{d}_\mathrm{REC}=\deg_w(\mathrm{DNR}_\mathrm{REC})$. For an extended discussion of the recursion-theoretic naturalness of $\mathbf{d}_\mathrm{REC}$ and related weak degrees, see [33, Section 10].

Theorem 4.5   We have $\mathbf{d}_\mathrm{REC}\in\mathcal{P}_w$ and

$$\mathbf{0}<\mathbf{d}<\mathbf{d}_\mathrm{REC}<\mathbf{r}_1<\mathbf{r}_2^\ast<\mathbf{1}.$$

Proof.A Tarski/Kuratowski computation shows that $\mathrm{DNR}_\mathrm{REC}$ is $\Sigma^0_3$. Let $\mathrm{DNR}_2$ be as in the proof of Theorem 4.2. By Lemma 3.3 we can find a nonempty $\Pi^0_1$ set $Q_\mathrm{REC}\subseteq2^\omega$ such that $Q_\mathrm{REC}\equiv_w\mathrm{DNR}_\mathrm{REC}\cup\mathrm{DNR}_2=\mathrm{DNR}_\mathrm{REC}$. Thus $\mathbf{d}_\mathrm{REC}=\deg_w(\mathrm{DNR}_\mathrm{REC})=\deg_w(Q_\mathrm{REC})\in\mathcal{P}_w$. By Ambos-Spies et al [1, Theorems 1.4, 1.8, 1.9] we have $\mathbf{d}<\mathbf{d}_\mathrm{REC}<\mathbf{r}_1$, and the rest is from Theorem 4.3.$\Box$

Definition 4.6   For all $f\in\omega^\omega$ put

$$\mathrm{DNR}^f=\{g\in\omega^\omega\mid\forall n (g(n)\ne\{n\}^f(n))\},$$

the set of functions which are diagonally nonrecursive relative to $f$. Put $\mathrm{DNR}^1=\mathrm{DNR}$ and, for each $n\ge1$,

$$\mathrm{DNR}^{n+1}=\{f\oplus g\mid f\in\mathrm{DNR}^n\mbox{ and }g\in\mathrm{DNR}^f\}.$$

Clearly $\mathrm{DNR}^n$ is a $\Pi^0_1$ subset of $\omega^\omega$. Put $\mathbf{d}^n=\deg_w(\mathrm{DNR}^n)$.

Remark 4.7   Trivially $\mathbf{d}^1=\mathbf{d}$ and $\mathbf{d}^n\le\mathbf{d}^{n+1}$ for all $n\ge1$. The proofs of Theorems 4.2 and 4.3 show that $\mathbf{d}^n\in\mathcal{P}_w$ and $\mathbf{d}^n<\mathbf{r}_1$ for all $n\ge1$. By Kumabe [18] we have $\mathbf{d}^1<\mathbf{d}^2$, and we conjecture that $\mathbf{d}^n<\mathbf{d}^{n+1}$ for all $n$. Thus in $\mathcal{P}_w$ we apparently have

$$\mathbf{0}<\mathbf{d}=\mathbf{d}^1<\mathbf{d}^2<\cdots<\mat... ...{d}^{n+1}<\cdots <\mathbf{r}_1<\mathbf{r}_2^\ast<\mathbf{1}.$$

Note also that the sequence $\mathbf{d}^1<\cdots<\mathbf{d}^n<\cdots$ can be extended into the transfinite.

Remark 4.8   We conjecture that, for all $n\ge2$, $\mathbf{d}^n$ is incomparable with $\mathbf{d}_\mathrm{REC}$. Note also that these $\mathbf{d}^n$'s are not to be confused with the $\mathbf{d}_\alpha$'s of Simpson [33, Example 10.14]. Indeed, we conjecture that, for all $n\ge2$ and $\alpha\ge0$, $\mathbf{d}^n$ is incomparable with $\mathbf{d}_\alpha$.

Remark 4.9   We do not know of any specific, natural degrees in $\mathcal{P}_w$ outside the interval from $\mathbf{d}$ to $\mathbf{r}_2^\ast$, except $\mathbf{0}$ and $\mathbf{1}$. On the other hand, by Theorem 4.5 and Remarks 4.7 and 4.8, the interval from $\mathbf{d}$ to $\mathbf{r}_2^\ast$ within $\mathcal{P}_w$ appears to be remarkably rich in specific, natural degrees.

Embedding $\mathcal{R}_T$ into $\mathcal{P}_w$

In this section we exhibit a specific, natural embedding of the countable upper semilattice $\mathcal{R}_T$ into the countable distributive lattice $\mathcal{P}_w$.

Definition 5.1   A $\Pi^0_2$ singleton is a point $f\in\omega^\omega$ such that the singleton set $\{f\}$ is $\Pi^0_2$.

Lemma 5.2   Given a $\Pi^0_2$ singleton $f$, we have $\deg_w(\{f\}\cup\mathrm{PA})\in\mathcal{P}_w$. Thus

$$\phi:\deg_T(f)\mapsto\deg_w(\{f\}\cup\mathrm{PA})$$ (1)

is an upper semilattice homomorphism of the Turing degrees of $\Pi^0_2$ singletons into $\mathcal{P}_w$.

Proof.The first statement is the special case of Lemma 3.3 with $S=\{f\}$ and $P=\mathrm{PA}$. For the second statement, note that for any $f,g\in\omega^\omega$ and $P\subseteq\omega^\omega$ we have $\{f\oplus g\}\cup P\equiv_w(\{f\}\cup P)\times(\{g\}\cup P)$, and $f\le_Tg$ implies $\{f\}\cup P\le_w\{g\}\cup P$. In particular this holds when $f$ and $g$ are $\Pi^0_2$ singletons and $P=\mathrm{PA}$.$\Box$

Lemma 5.3   We have an upper semilattice homomorphism $\phi$ of the Turing degrees $\le\mathbf{0}'$ into $\mathcal{P}_w$, given by (1). Moreover, $\phi(\mathbf{0})=\mathbf{0}$ and $\phi(\mathbf{0}')=\mathbf{1}$.

Proof.The first statement is a special case of Lemma 5.2, because $\deg_T(f)\le\mathbf{0}'$ if and only if $f$ is $\Delta^0_2$ (see Kleene [17, Theorem XI, page 293]), which implies that $f$ is a $\Pi^0_2$ singleton. It is easy to see that $\phi(\mathbf{0})=\mathbf{0}$. To show that $\phi(\mathbf{0}')=\mathbf{1}$, by Kleene [17, Theorem 38*, pages 401-402] let $f\in\mathrm{PA}$ be $\Delta^0_2$. Then $\deg_T(f)\le\mathbf{0}'$ and $\phi(\deg_T(f))=\deg_w(\{f\}\cup\mathrm{PA})=\deg_w(\mathrm{PA})=\mathbf{1}$, hence $\phi(\mathbf{0}')=\mathbf{1}$.$\Box$

Lemma 5.4   If $\mathbf{a},\mathbf{b}$ are Turing degrees $\le\mathbf{0}'$, and if $\mathbf{b}\in\mathcal{R}_T$, then $\mathbf{a}\le\mathbf{b}$ if and only if $\phi(\mathbf{a})\le\phi(\mathbf{b})$. In particular, the restriction of $\phi$ to $\mathcal{R}_T$ is one-to-one.

Proof.Let $f,g\in\omega^\omega$ be such that $\deg_T(f)=\mathbf{a}$ and $\deg_T(g)=\mathbf{b}$. We must show that $f\le_Tg$ if and only if $\{f\}\cup\mathrm{PA}\le_w\{g\}\cup\mathrm{PA}$. The ``only if'' part is trivial. For the ``if'' part, suppose $\{f\}\cup\mathrm{PA}\le_w\{g\}\cup\mathrm{PA}$. In particular, $\{f\}\cup\mathrm{PA}\le_w\{g\}$. If $f\not\le_Tg$, then $\mathrm{PA}\le_w\{g\}$, hence $\mathrm{DNR}\le_w\{g\}$, hence $\deg_T(g)=\mathbf{0}'$ by the Arslanov Completeness Criterion [12], hence $f\le_Tg$, a contradiction. Thus $f\le_Tg$. This proves our lemma.$\Box$

We now obtain our main result.

Theorem 5.5   We have an embedding $\phi:\mathcal{R}_T\to\mathcal{P}_w$ given by (1). The embedding $\phi$ is one-to-one, preserves the partial ordering relation and the least upper bound operation from $\mathcal{R}_T$, carries $\mathbf{0}$ to $\mathbf{0}$, and carries $\mathbf{0}'$ to $\mathbf{1}$.

Proof.This result is obtained by combining Lemmas 5.3 and 5.4.$\Box$

Theorem 5.6   Let $\phi:\mathcal{R}_T\to\mathcal{P}_w$ be the embedding given by (1). Let $\mathbf{a}\in\mathcal{R}_T$ be a recursively enumerable Turing degree other than $\mathbf{0}$ and $\mathbf{0}'$. Then the weak degree $\phi(\mathbf{a})\in\mathcal{P}_w$ is incomparable with each of the specific weak degrees $\mathbf{d},\mathbf{r}_1,\mathbf{r}_2^\ast\in\mathcal{P}_w$ of Theorem 4.3.

Proof.By the Arslanov Completeness Criterion [12] we have $\phi(\mathbf{a})\not\ge\mathbf{d}$. It remains to show that $\phi(\mathbf{a})\not\le\mathbf{r}_2^\ast$. This is obvious, because for any nonrecursive $A$ we have $\mu(\{f\in2^\omega\mid A\le_Tf\})=0$ [27, §10, Theorem 1].$\Box$

We finish by noting some generalizations of Theorem 5.5.

Remark 5.7   A set $A\subseteq\omega$ is said to be $n$-REA if $A=A_1\oplus\cdots\oplus A_n$ where $A_1$ is recursively enumerable and, for each $i=1,\ldots,n-1$, $A_{i+1}$ is recursively enumerable relative to $A_i$ and $\ge_TA_i$. A Turing degree is said to be $n$-REA if it contains an $n$-REA set. Note that any $n$-REA set is a $\Pi^0_2$ singleton. Hence by Lemma 5.2 we have $\phi(\mathbf{a})\in\mathcal{P}_w$ for all $n$-REA Turing degrees $\mathbf{a}$. Jockusch et al [13, Theorem 5.1] have generalized the Arslanov Completeness Criterion to $n$-REA Turing degrees. In our terms, their result says that if $\mathbf{a}$ is an $n$-REA Turing degree for some $n\in\omega$, then $\phi(\mathbf{a})\ge\mathbf{d}$ if and only if $\mathbf{a}\ge\mathbf{0}'$, in which case $\phi(\mathbf{a})=\mathbf{1}$. Therefore, letting $\mathcal{R}_T^\ast(\le\mathbf{0}')$ denote the set of Turing degrees which are $\le\mathbf{0}'$ and $n$-REA for some $n\in\omega$, we have as in Theorem 5.5 an embedding

$$\phi:\mathcal{R}_T^\ast(\le\mathbf{0}')\to\mathcal{P}_w$$

which is one-to-one, preserves the partial ordering relation and the least upper bound operation from $\mathcal{R}_T^\ast(\le\mathbf{0}')$, and carries $\mathbf{0}$ to $\mathbf{0}$ and $\mathbf{0}'$ to $\mathbf{1}$. Moreover, for all $\mathbf{a}\in\mathcal{R}_T^\ast(\le\mathbf{0}')$ other than $\mathbf{0}$ and $\mathbf{0}'$, we have as in Theorem 5.6 that $\phi(\mathbf{a})$ is incomparable with $\mathbf{d},\mathbf{r}_1,\mathbf{r}_2^\ast$.

Remark 5.8   More generally, given $\mathbf{q}\in\mathcal{P}_w$ such that $\mathbf{q}\ge\mathbf{d}$, we have an embedding

$$\phi_\mathbf{q}:\mathcal{R}_T^\ast(\le\mathbf{0}')\to\mathcal{P}_w(\le\mathbf{q})$$

defined by $\phi_\mathbf{q}(\mathbf{a})=\inf(\phi(\mathbf{a}),\mathbf{q})$. The embedding $\phi_\mathbf{q}$ is one-to-one, preserves the partial ordering relation and least upper bound operation from $\mathcal{R}_T^\ast(\le\mathbf{0}')$, carries $\mathbf{0}$ to $\mathbf{0}$, and carries $\mathbf{0}'$ to $\mathbf{q}$. If we set $\mathbf{q}=\mathbf{1}$, we recover the embedding $\phi:\mathcal{R}_T^\ast(\le\mathbf{0}')\to\mathcal{P}_w$ of Remark 5.7. If we set $\mathbf{q}=\mathbf{1}$ and restrict to $\mathcal{R}_T$, we recover the embedding $\phi:\mathcal{R}_T\to\mathcal{P}_w$ of Theorem 5.5.

Bibliography

1

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.

2

Stephen Binns.
The Medvedev and Muchnik Lattices of $\Pi^0_1$ Classes.
PhD thesis, Pennsylvania State University, August 2003.
VII + 80 pages.

3

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

4

Stephen Binns.
Small $\Pi^0_1$ classes.
Archive for Mathematical Logic, 45:393-410, 2006.

5

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.

6

J. C. E. Dekker, editor.
Recursive Function Theory.
Proceedings of Symposia in Pure Mathematics. American Mathematical Society, 1962.
VII + 247 pages.

7

Natasha L. Dobrinen and Stephen G. Simpson.
Almost everywhere domination.
Journal of Symbolic Logic, 69:914-922, 2004.

8

Rodney G. Downey and Denis Hirschfeldt.
Algorithmic Randomness and Complexity.
May 2004.
Preprint, 305 pages, in preparation, to appear.

9

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

10

FOM e-mail list.
http://www.cs.nyu.edu/mailman/listinfo/fom/.
September 1997 to the present.

11

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

12

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

13

Carl G. Jockusch, Jr., Manuel Lerman, Robert I. Soare, and Robert M. Solovay.
Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion.
Journal of Symbolic Logic, 54:1288-1323, 1989.

14

Carl G. Jockusch, Jr. and Robert I. Soare.
Degrees of members of $\Pi^0_1$ classes.
Pacific Journal of Mathematics, 40:605-616, 1972.

15

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.

16

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

17

Stephen C. Kleene.
Introduction to Metamathematics.
Van Nostrand, 1952.
X + 550 pages.

18

Masahiro Kumabe.
A fixed point free minimal degree.
1997.
Preprint, 48 pages.

19

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.

20

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

21

Albert A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:1328-1341, 1963.
In Russian.

22

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

23

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

24

Mikhail G. Peretyatkin.
Finitely Axiomatizable Theories.
Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997.
XIV + 294 pages.

25

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

26

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

27

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

28

Gerald E. Sacks.
The recursively enumerable degrees are dense.
Annals of Mathematics, 80:300-312, 1964.

29

Dana S. Scott.
Algebras of sets binumerable in complete extensions of arithmetic.
In [6], pages 117-121, 1962.

30

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

31

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

32

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

33

Stephen G. Simpson.
Mass problems and randomness.
Bulletin of Symbolic Logic, 11:1-27, 2005.

34

Stephen G. Simpson and Theodore A. Slaman.
Medvedev degrees of $\Pi^0_1$ subsets of $2^\omega$.
July 2001.
Preprint, 4 pages, in preparation, to appear.

35

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

36

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

37

Michiel van Lambalgen.
Von Mises' definition of random sequences reconsidered.
Journal of Symbolic Logic, 52:725-755, 1987.

About this document ...

An extension of the
recursively enumerable Turing degrees

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 extre

The translation was initiated by Stephen G Simpson on 2008-04-28