Mass Problems and
Almost Everywhere Domination

Stephen G. Simpson

Pennsylvania State University

First draft: September 15, 2006
This draft: April 28, 2008

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

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

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

Accepted April 24, 2007 for Mathematical Logic Quarterly.

Mathematical Logic Quarterly, 53, 2007, pp. 483-492.

Abstract:

We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let $\mathrm{AED}$ and $\mathrm{MLR}$ be the set of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let $\mathbf{b}_1$, $\mathbf{b}_2$, $\mathbf{b}_3$ be the degrees of unsolvability of the mass problems associated with the sets $\mathrm{AED}$, $\mathrm{MLR}\times\mathrm{AED}$, $\mathrm{MLR}\cap\mathrm{AED}$ respectively. Let $\mathcal{P}_w$ be the lattice of degrees of unsolvability of mass problems associated with nonempty $\Pi^0_1$ subsets of $2^\omega$. Let $\mathbf{1}$ and $\mathbf{0}$ be the top and bottom elements of $\mathcal{P}_w$. We show that $\inf(\mathbf{b}_1,\mathbf{1})$ and $\inf(\mathbf{b}_2,\mathbf{1})$ and $\inf(\mathbf{b}_3,\mathbf{1})$ belong to $\mathcal{P}_w$ and that $\mathbf{0}<\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{b}_2,\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$. Under the natural embedding of the recursively enumerable Turing degrees into $\mathcal{P}_w$, we show that $\inf(\mathbf{b}_1,\mathbf{1})$ and $\inf(\mathbf{b}_3,\mathbf{1})$ but not $\inf(\mathbf{b}_2,\mathbf{1})$ are comparable with some recursively enumerable Turing degrees other than $\mathbf{0}$ and $\mathbf{0}'$. In order to make this paper more self-contained, we exposit the proofs of some recent theorems due to Hirschfeldt, Miller, Nies, and Stephan.

Contents

• Introduction
• Some mass problem inequalities
• Comparison with r.e. Turing degrees
• A theorem of Hirschfeldt and Miller
• A theorem of Nies
• A theorem of Stephan
• Bibliography

Introduction

In our previous papers [3,31,34,32,7] we studied the lattice $\mathcal{P}_w$ of degrees of unsolvability of mass problems associated with nonempty $\Pi^0_1$ subsets of $2^\omega$. We showed that $\mathcal{P}_w$ contains many specific, natural degrees in addition to $\mathbf{1}$ and $\mathbf{0}$, the top and bottom elements of $\mathcal{P}_w$. We showed that many specific, natural degrees in $\mathcal{P}_w$ arise from foundationally interesting topics such as reverse mathematics, algorithmic randomness, computational complexity, hyperarithmeticity, and subrecursive hierarchies from Gentzen-style proof theory.

The purpose of the present paper is to exhibit and discuss some relatively new examples of specific, natural degrees in $\mathcal{P}_w$. The new examples arise from almost everywhere domination, a concept which was originally introduced by Dobrinen/Simpson [9]. Let $B$ be a Turing oracle. We say that $B$ is almost everywhere dominating if, for all $X\in2^\omega$ except a set of measure $0$, each function computable from $X$ is dominated by some function computable from $B$. It is known [9] that almost everywhere domination is closely related to the reverse mathematics of measure theory.

In order to succinctly state our results, let $\mathrm{MLR}=\{X\in2^\omega\mid X$ is Martin-Löf random$\}$ and $\mathrm{AED}=\{Y\in2^\omega\mid Y$ is almost everywhere dominating$\}$. For $P,Q\subseteq2^\omega$ we write $P\times Q=\{X\oplus Y\mid X\in P$ and $Y\in Q\}$ and $P\cap Q=$ the intersection of $P$ and $Q$. With these conventions, let $\mathbf{b}_1$, $\mathbf{b}_2$, $\mathbf{b}_3$ be the respective degrees of unsolvability of the mass problems associated with $\mathrm{AED}$, $\mathrm{MLR}\times\mathrm{AED}$, $\mathrm{MLR}\cap\mathrm{AED}$. Trivially $\mathbf{b}_1\le\mathbf{b}_2\le\mathbf{b}_3$. Our main results may be summarized by saying that the degrees $\inf(\mathbf{b}_1,\mathbf{1})$, $\inf(\mathbf{b}_2,\mathbf{1})$, $\inf(\mathbf{b}_3,\mathbf{1})$ belong to $\mathcal{P}_w$ and

$\mathbf{0}<\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{b}_2,\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$.

The proof of this chain of inequalities uses virtually everything that is currently known about the relationship between Martin-Löf randomness and almost everywhere domination. See Theorems 2.2 and 2.3 below.

Historically, there has been a great deal of interest in the semilattice of recursively enumerable Turing degrees. Therefore, it seems desirable to examine the relationships between recursively enumerable Turing degrees and the various specific, natural degrees in $\mathcal{P}_w$. In order to state our results, let us temporarily identify each recursively enumerable Turing degree $\mathbf{a}$ with its image in $\mathcal{P}_w$ under the natural one-to-one embedding $\mathbf{a}\mapsto\inf(\mathbf{a},\mathbf{1})$ given in [34, Theorem 5.5]. In particular, we identify $\mathbf{0}'$ and $\mathbf{0}$, the top and bottom recursively enumerable Turing degrees, with $\mathbf{1}$ and $\mathbf{0}$, the top and bottom degrees in $\mathcal{P}_w$. In our papers [31,34] written in 2004, we remarked that all of the specific, natural degrees in $\mathcal{P}_w$ which were known at that time are incomparable with all recursively enumerable Turing degrees except $\mathbf{0}'$ and $\mathbf{0}$. In this respect it turns out that our new examples of specific, natural degrees in $\mathcal{P}_w$ behave somewhat differently from the old ones. Namely, although $\inf(\mathbf{b}_2,\mathbf{1})$ is again incomparable with all recursively enumerable Turing degrees except $\mathbf{0}'$ and $\mathbf{0}$, this turns out not to be the case for $\inf(\mathbf{b}_1,\mathbf{1})$ and $\inf(\mathbf{b}_3,\mathbf{1})$. See Theorems 3.1 and 3.2 below.

Our work in this paper owes much to conversations with Bjørn Kjos-Hanssen, Antonín Kucera, and Joseph S. Miller. In particular, the fact that $\inf(\mathbf{b}_1,\mathbf{1})$ belongs to $\mathcal{P}_w$ was already implicit in Kjos-Hanssen [18], and Miller corrected an error in one of our early proofs of the inequality $\inf(\mathbf{b}_2,\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})$.

The reader who is familiar with the basics of recursion theory will find that this paper is largely self-contained. If $E$ is an expression which may or may not denote a natural number, we write $E\downarrow$ to mean that $E$ is defined (i.e., $E$ denotes a natural number), otherwise $E\uparrow$. If $E_1$ and $E_2$ are two such expressions, we write $E_1\simeq E_2$ to mean that $E_1$ and $E_2$ are both defined and equal, or both undefined. Throughout this paper, a convenient background reference is our recent paper [33], which includes a fairly thorough exposition of almost everywhere domination and Martin-Löf randomness.

Some mass problem inequalities

The purpose of this section is to prove our mass problem inequalities in $\mathcal{P}_w$. The proofs use some recent theorems of Cholak/Greenberg/Miller, Kjos-Hanssen, Hirschfeldt/Miller, Nies, and Stephan concerning almost everywhere domination and Martin-Löf randomness. In order to make this paper more self-contained, we exposit the proofs of the theorems of Hirschfeldt/Miller, Nies, and Stephan respectively in Sections 4, 5, 6 below.

Our notion of reducibility for decision problems is standard. Given $X,Y\in2^\omega$, we say that $X$ is Turing reducible to $Y$, abbreviated $X\le_TY$, if $X$ is computable using $Y$ as an oracle. A Turing degree is an equivalence class of elements of $2^\omega$ under mutual Turing reducibility. The Turing degree of $X$ is denoted $\deg_T(X)$.

Our notion of reducibility for mass problems is as follows. Given $P,Q\subseteq2^\omega$, we say that $P$ is weakly reducible to $Q$, abbreviated $P\le_wQ$, if for all $Y\in Q$ there exists $X\in P$ such that $X$ is Turing reducible to $Y$. A weak degree is an equivalence class of subsets of $2^\omega$ under mutual weak reducibility. The weak degree of $P$ is denoted $\deg_w(P)$. Weak degrees have sometimes been known as Muchnik degrees [23].

Note that for $\mathbf{p}=\deg_w(P)$ and $\mathbf{q}=\deg_w(Q)$ we have $\inf(\mathbf{p},\mathbf{q})=\deg_w(P\cup Q)$ and $\sup(\mathbf{p},\mathbf{q})=\deg_w(P\times Q)$. Note also that for $X,Y\in2^\omega$ we have $X\le_TY$ if and only if $\{X\}\le_w\{Y\}$. Here $\{X\}$ denotes the singleton set whose only element is $X$. Therefore, the Turing degree $\deg_T(X)$ is sometimes identified with the weak degree $\deg_w(\{X\})$.

Definition 2.1  

1. Let $\mathbf{b}_1=\deg_w(\mathrm{AED})$ where
   $\mathrm{AED}=\{Y\in2^\omega\mid Y$ is almost everywhere dominating$\}$.
2. Let $\mathbf{b}_2=\deg_w(\mathrm{MLR}\times\mathrm{AED})$ where
   $\mathrm{MLR}=\{X\in2^\omega\mid X$ is Martin-Löf random$\}$.
3. Let $\mathbf{b}_3=\deg_w(\mathrm{MLR}\cap\mathrm{AED})$.

Theorem 2.2   The weak degrees $\inf(\mathbf{b}_1,\mathbf{1})$, $\inf(\mathbf{b}_2,\mathbf{1})$, $\inf(\mathbf{b}_3,\mathbf{1})$ belong to $\mathcal{P}_w$.

Proof.An important tool in the study of $\mathcal{P}_w$ is the Embedding Lemma [34, Lemma 3.3], [32, Lemma 4]. The Embedding Lemma says: For any $\mathbf{s}=\deg_w(S)$ where $S$ is $\Sigma^0_3$, we have $\inf(\mathbf{s},\mathbf{1})\in\mathcal{P}_w$. Therefore, in order to prove Theorem 2.2, it suffices to show that $\mathrm{AED}$ and $\mathrm{MLR}$ are $\Sigma^0_3$.

After Dobrinen/Simpson [9], the concept of almost everywhere domination was subsequently explored by Binns/Kjos-Hanssen/Lerman/Solomon [2], Cholak/Greenberg/Miller [5], Kjos-Hanssen [18], Kjos-Hanssen/Miller/Solomon [19], and Simpson [33]. We now know [18,19] that $B$ is almost everywhere dominating if and only if $0'\le_\mathit{LR}B$. Here $0'$ denotes the Halting Problem, and $\le_\mathit{LR}$ denotes $\mathit{LR}$-reducibility: $A\le_\mathit{LR}B$ if and only if $\forall X ($if $X$ is random relative to $B$, then $X$ is random relative to $A)$. Moreover, as shown in [19], $\mathit{LR}$-reducibility is equivalent to $\mathit{LK}$-reducibility: $A\le_\mathit{LK}B$ if and only if $K^B(\tau)\le K^A(\tau)+O(1)$ for all $\tau$. Here $K^B(\tau)$ denotes the prefix-free Kolmogorov complexity of $\tau$ relative to a Turing oracle $B$. The concepts of $\mathit{LR}$-reducibility and $\mathit{LK}$-reducibility were originally introduced by Nies [24, Section 8]. A convenient reference for these results is Simpson [33].

One way to see that $\mathrm{AED}$ is $\Sigma^0_3$ is to use the characterization in terms of $\mathit{LK}$-reducibility. We know that $B\in\mathrm{AED}$ if and only if $0'\le_{LK}B$, i.e., $K^B(\tau)\le K^{0'}(\tau)+O(1)$, i.e., $\exists c \forall\tau (K^B(\tau)\le K^{0'}(\tau)+c)$. But $K^B(\tau)\le K^{0'}(\tau)+c$ if and only if $\forall\rho (U^{0'}(\rho)\simeq\tau\Rightarrow \exists\sigma (\vert\sigma\vert\le\vert\rho\vert+c$ and $U^B(\sigma)\simeq\tau))$. Here $U^B$ is a universal prefix-free oracle machine. The last satement is $\Pi^0_2$, so $\mathrm{AED}$ is $\Sigma^0_3$. The fact that $\mathrm{AED}$ is $\Sigma^0_3$ has previously been noted by Kjos-Hanssen [18] and Kjos-Hanssen/Miller/Solomon [19]. See also [33, Corollary 5.9].

It remains to show that $\mathrm{MLR}$ is $\Sigma^0_3$. In fact, $\mathrm{MLR}$ is $\Sigma^0_2$ in view of the existence of a universal Martin-Löf test. See for instance [20] or [31, Theorem 8.3] or [33, Theorem 3.2]. This completes the proof of Theorem 2.2.$\Box$

Theorem 2.3   In $\mathcal{P}_w$ we have $\mathbf{0}<\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{b}_2,\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$.

Proof.Trivially $\mathbf{b}_1\le\mathbf{b}_2\le\mathbf{b}_3$, hence $\inf(\mathbf{b}_1,\mathbf{1})\le\inf(\mathbf{b}_2,\mathbf{1})\le\inf(\mathbf{b}_3,\mathbf{1})$. Recall from [31,34] that $\mathbf{1}=\deg_w(\mathrm{PA})$ where

$\mathrm{PA}=\{X\in2^\omega\mid X$ is a complete extension of Peano Arithmetic$\}$.

We have $\mathbf{0}<\inf(\mathbf{b}_1,\mathbf{1})$ because by [9] no member of $\mathrm{AED}\cup\mathrm{PA}$ is recursive. In order to prove $\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{b}_2,\mathbf{1})$, consider

$\mathrm{DNR}=\{f\in\omega^\omega\mid f$ is diagonally nonrecursive$\}$

where $f$ is said to be diagonally nonrecursive if $\forall n (f(n)\not\simeq\varphi_n^{(1)}(n))$.

Lemma 2.4   $\mathrm{DNR}\not\le_w\mathrm{AED}$.

Proof.This follows from items 1 and 2 in Lemma 2.7 below. $\Box$The next two lemmas are well known.

Lemma 2.5   $\mathrm{DNR}\le_w\mathrm{MLR}$.

Proof.Consider the recursive functional $X\mapsto f^X$ given by $f^X(n)=\sum_{i=0}^{n-1}X(i)2^i$ for all $X\in2^\omega$. Let $U_n=\{X\in2^\omega\mid f^X(n)\simeq\varphi_n^{(1)}(n)\}$. Note that $U_n$ is uniformly $\Sigma^0_1$ and $\mu(U_n)\le1/2^n$. If $X$ is random, it follows by Solovay's Lemma (see for instance [33, Lemma 3.7]) that $X\in U_n$ for only finitely many $n$. Therefore, with finitely many exceptions, $f^X$ is diagonally nonrecursive. This proves the lemma. For refinements, see Jockusch [14, Proposition 3] and Ambos-Spies/Kjos-Hanssen/Lempp/Slaman [1] and Simpson [31]. $\Box$

Lemma 2.6   $\mathrm{MLR}\le_w\mathrm{PA}$.

Proof.Since $\mathrm{MLR}$ is $\Sigma^0_2$ and nonempty, we can find a nonempty $\Pi^0_1$ set $P\subseteq\mathrm{MLR}$. Since $P$ is a nonempty $\Pi^0_1$ subset of $2^\omega$, we have $P\le_w\mathrm{PA}$ in view of Scott/Tennenbaum [30] and Scott [29]. The lemma follows. $\Box$By Lemmas 2.4 and 2.5 and 2.6 we have $\mathrm{MLR}\cup\mathrm{PA}\not\le_w\mathrm{AED}$. From this it follows trivially that $\mathrm{AED}\cup\mathrm{PA}<_w(\mathrm{MLR}\times\mathrm{AED})\cup\mathrm{PA}$. In other words, $\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{b}_2,\mathbf{1})$.

Next we prove $\inf(\mathbf{b}_2,\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})$. We use the forcing construction of Cholak/Greenberg/Miller [5] referring to $\mathrm{CGM}$-genericity.

Lemma 2.7 (Cholak/Greenberg/Miller)  

1. If $B$ is sufficiently $\mathrm{CGM}$-generic, then $B$ is almost everywhere dominating.
2. If $B$ is sufficiently $\mathrm{CGM}$-generic, then $\mathrm{DNR}\not\le_w\{B\}$.
3. For each nonrecursive $A$, if $B$ is sufficiently $\mathrm{CGM}$-generic then $A\not\le_TB$.

Proof.See Cholak/Greenberg/Miller [5, Section 4]. $\Box$We also use the following result due to Hirschfeldt and Miller, 2006.

Lemma 2.8 (Hirschfeldt/Miller)   There is a nonrecursive, recursively enumerable set $A$ such that $\{A\}\le_w\mathrm{MLR}\cap\mathrm{AED}$.

Proof.See Nies [25, Theorem 5.6]. Alternatively, see Section 4 below. $\Box$The next lemma is well known.

Lemma 2.9  

1. If $A\not\le_TB$, then $\mu(\{X\in2^\omega\mid A\not\le_TX\oplus B\})=1$.
2. If $\mathrm{PA}\not\le_w\{B\}$, then $\mu(\{X\in2^\omega\mid\mathrm{PA}\not\le_w\{X\oplus B\}\})=1$.

Proof.The first statement is a relativized form of Sacks [28, Theorem 1, page 154]. The second statement is a relativived form of Jockusch/Soare [16, Theorem 5.3]. Both statements follow from the general ``non-helping'' result in [31, Lemma 7.3]. $\Box$By Lemma 2.8 let $A$ be nonrecursive such that $\{A\}\le_w\mathrm{MLR}\cap\mathrm{AED}$. Since $A$ is nonrecursive, $\{A\}\cup\mathrm{DNR}\not\le_w\mathrm{AED}$ by Lemma 2.7. Hence $\{A\}\cup\mathrm{PA}\not\le_w\mathrm{AED}$ by Lemmas 2.5 and 2.6. But then, by Lemma 2.9, $\{A\}\cup\mathrm{PA}\not\le_w\mathrm{MLR}\times\mathrm{AED}$, since $\mu(\mathrm{MLR})=1$. It now follows by our choice of $A$ that $(\mathrm{MLR}\cap\mathrm{AED})\cup\mathrm{PA}\not\le_w\mathrm{MLR}\times\mathrm{AED}$. From this it follows trivially that $(\mathrm{MLR}\times\mathrm{AED})\cup\mathrm{PA}<_w(\mathrm{MLR}\cap\mathrm{AED})\cup\mathrm{PA}$. In other words, $\inf(\mathbf{b}_2,\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})$.

It remains to prove $\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$. We use the following results of Nies 2006 and Stephan 2002.

Lemma 2.10 (Nies)   There exists $B\in\mathrm{MLR}\cap\mathrm{AED}$ such that $0'\not\le_TB$.

Proof.See Nies [26, Theorem VI.18]. Alternatively, see Section 5 below. $\Box$

Lemma 2.11 (Stephan)   If $B\in\mathrm{MLR}$ and $0'\not\le_TB$, then $\mathrm{PA}\not\le_w\{B\}$.

Proof.See Stephan [35]. Alternatively, see Section 6 below. $\Box$By Lemma 2.10 let $B\in\mathrm{MLR}\cap\mathrm{AED}$ be such that $0'\not\le_TB$. By Lemma 2.11 we have $\mathrm{PA}\not\le_w\{B\}$. Thus $\mathrm{PA}\not\le_w\mathrm{MLR}\cap\mathrm{AED}$. It follows trivially that $(\mathrm{MLR}\cap\mathrm{AED})\cup\mathrm{PA}<_w\mathrm{PA}$. In other words, $\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$.

This completes the proof of Theorem 2.3.$\Box$

Comparison with r.e. Turing degrees

In this section we discuss the relationship between the weak degrees $\mathbf{b}_1$, $\mathbf{b}_2$, $\mathbf{b}_3$ and the recursively enumerable Turing degrees. Recall from [34, Theorem 5.5] that there is a natural one-to-one embedding of the recursively enumerable Turing degrees into $\mathcal{P}_w$ given by $\mathbf{a}\mapsto\inf(\mathbf{a},\mathbf{1})$.

Theorem 3.1   There is no recursively enumerable Turing degree $\mathbf{0}<\mathbf{a}<\mathbf{0}'$ such that $\inf(\mathbf{a},\mathbf{1})$ is comparable with $\inf(\mathbf{b}_2,\mathbf{1})$.

Proof.Let $\mathbf{a}=\deg_T(A)$ where $A$ is recursively enumerable and $0<_TA<_T0'$. Since $A$ is nonrecursive, we have $\{A\}\cup\mathrm{DNR}\not\le_w\mathrm{AED}$ by Lemma 2.7, hence $\{A\}\cup\mathrm{PA}\not\le_w\mathrm{AED}$ by Lemmas 2.5 and 2.6, hence $\{A\}\cup\mathrm{PA}\not\le_w\mathrm{MLR}\times\mathrm{AED}$ by Lemma 2.9. From this it follows trivially that $\{A\}\cup\mathrm{PA}\not\le_w(\mathrm{MLR}\times\mathrm{AED})\cup\mathrm{PA}$. In other words, $\inf(\mathbf{a},\mathbf{1})\not\le\inf(\mathbf{b}_2,\mathbf{1})$. On the other hand, since $A$ is recursively enumerable and not Turing complete, we have $\mathrm{DNR}\not\le_w\{A\}$ by the Arslanov Completeness Criterion [14], hence $\mathrm{MLR}\cup\mathrm{PA}\not\le_w\{A\}$ by Lemmas 2.5 and 2.6. From this it follows trivially that $(\mathrm{MLR}\times\mathrm{AED})\cup\mathrm{PA}\not\le_w\{A\}\cup\mathrm{PA}$. In other words, $\inf(\mathbf{b}_2,\mathbf{1})\not\le\inf(\mathbf{a},\mathbf{1})$. This completes the proof.$\Box$

Theorem 3.2   There are recursively enumerable Turing degrees $\mathbf{0}<\mathbf{a}<\mathbf{0}'$ and $\mathbf{0}<\mathbf{c}<\mathbf{0}'$ such that $\mathbf{0}<\inf(\mathbf{a},\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$ and $\mathbf{0}<\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{c},\mathbf{1})<\mathbf{1}$.

Proof.By Lemma 2.8 due to Hirschfeldt and Miller, let $A>_T0$ be recursively enumerable such that $\{A\}\le_w\mathrm{MLR}\cap\mathrm{AED}$. By Simpson [33, Example 6.8] or Cholak/Greenberg/Miller [5, Theorem 2.1], let $C<_T0'$ be recursively enumerable and almost everywhere dominating. Let $\mathbf{a}=\deg_T(A)$ and $\mathbf{c}=\deg_T(C)$. Clearly $\mathbf{0}<\inf(\mathbf{a},\mathbf{1})\le\inf(\mathbf{b}_3,\mathbf{1})<\mathbf{1}$ and $\mathbf{0}<\mathbf{a}<\mathbf{0}'$ and $\mathbf{0}<\inf(\mathbf{b}_1,\mathbf{1})\le\inf(\mathbf{c},\mathbf{1})<\mathbf{1}$ and $\mathbf{0}<\mathbf{c}<\mathbf{0}'$. By Theorems 2.3 and 3.1 it follows that $\inf(\mathbf{a},\mathbf{1})<\inf(\mathbf{b}_3,\mathbf{1})$ and $\inf(\mathbf{b}_1,\mathbf{1})<\inf(\mathbf{c},\mathbf{1})$.$\Box$

A theorem of Hirschfeldt and Miller

In this section we exposit the proof of the following theorem of Hirschfeldt and Miller 2006, generalizing a much earlier theorem of Kucera [21].

Theorem 4.1 (Hirschfeldt/Miller)   Let $S\subseteq2^\omega$ be $\Sigma^0_3$ of measure $0$. Then we can find a nonrecursive, recursively enumerable set $A$ such that $A\le_TX$ for all random $X\in S$.

Proof.We follow the writeup of Nies [25, Theorem 5.6].

We first prove the theorem for $\Pi^0_2$ sets. Let $P\subseteq2^\omega$ be $\Pi^0_2$ of measure $0$. Write $P=\bigcap_nV_n$ where $V_n$ is uniformly $\Sigma^0_1$ and $\lim_n\mu(V_n)=0$.

The construction of $A$ is as follows. At stage $s$, for each $e<s$ such that $W_{e,s}\cap A_s=\emptyset$, look for $n\in W_{e,s}$ such that $n>2e$ and $\mu(V_{n,s})<1/2^e$ and put the least such $n$ into $A_{s+1}$.

Clearly $A$ is recursively enumerable. Moreover, for each $e$, at most one $n$ gets into $A$ for the sake of $W_e$, and for this $n$ we have $n>2e$. Hence $A$ has at most $e$ members $\le2e$. Thus $\overline{A}$ is infinite.

We claim that if $W_e$ is infinite then $W_e\cap A\ne\emptyset$. To see this, fix $n\in W_e$ so large that $n>2e$ and $\mu(V_n)<1/2^e$. Let $s$ be such that $n\in W_{e,s}$. We have $\mu(V_{n,s})<1/2^e$, so by construction $W_{e,s}\cap A_{s+1}\ne\emptyset$, Q.E.D.

It follows from the previous claim that $A$ is nonrecursive. Indeed, $A$ is simple in the sense of Post (compare Rogers [27, Section 8.1]).

We claim that $A\le_TX$ for all random $X\in P$. To see this, note that by construction

$$\sum_{n\in A_{s+1}\setminus A_s}\mu(V_{n,s}) < \sum_e1/2^e = 2 < \infty .$$

Since $X$ is random, it follows by Solovay's Lemma (see [33, Lemma 3.7]) that $X\notin V_{n,s}$ for all but finitely many pairs $n,s$ such that $n\in A_{s+1}\setminus A_s$. Let $s_0$ be so large that $(\forall s>s_0) (\forall n\in A_{s+1}\setminus A_s) (X\notin V_{n,s})$. Given $n$, since $X\in V_n$ we can effectively find $s>s_0$ such that $X\in V_{n,s}$. We then have $n\in A\Longleftrightarrow n\in A_s$. Thus $A\le_TX$, Q.E.D. This proves the theorem for $\Pi^0_2$ sets.

Suppose now that $S$ is $\Sigma^0_3$ of measure $0$. Write $S=\bigcup_iP_i$ where $P_i$ is uniformly $\Pi^0_2$. Write $P_i=\bigcap_nV_{i,n}$ where $V_{i,n}$ is uniformly $\Sigma^0_1$ and $\lim_n\mu(V_{i,n})=0$ for each $i$. This implies that $\lim_n\sum_i\mu(V_{i,n})/2^i=0$, so we can build $A$ as before replacing $\mu(V_{n,s})$ by $\sum_i\mu(V_{i,n,s})/2^i$. The construction insures that

$$\sum_{n\in A_{s+1}\setminus A_s} \sum_i \mu(V_{i,n,s})/2^i < \sum_e1/2^e = 2 ,$$

hence for each $i$

$$\sum_{n\in A_{s+1}\setminus A_s}\mu(V_{i,n,s}) < 2^{i+1} < \infty ,$$

hence for any random $X$ we have by Solovay's Lemma $X\notin V_{i,n,s}$ for all but finitely many $n,s$ such that $n\in A_{s+1}\setminus A_s$. It follows as before that $A\le_TX$ for all random $X\in P_i$. This proves the theorem.$\Box$

Remark 4.2   Hirschfeldt, Miller and Nies describe the proof of Theorem 4.1 as a ``cost function'' construction. In the case of a $\Pi^0_2$ set, the cost of putting $n$ into $A$ at stage $s$ is $\mu(V_{n,s})$. In the case of a $\Sigma^0_3$ set, the cost of putting $n$ into $A$ at stage $s$ is $\sum_i\mu(V_{i,n,s})/2^i$. The construction insures that the total cost of building $A$ is finite, so that Solovay's Lemma can be applied.

The following corollary is originally due to Kucera [21].

Corollary 4.3 (Kucera)   Let $X_1,\ldots,X_n$ be random and $\le_T0'$. Then we can find a nonrecursive, recursively enumerable set $A$ such that $A\le_TX_i$ for all $i=1,\ldots,n$.

Proof.Let $S=\{X_1,\ldots,X_n\}$ and apply Theorem 4.1.$\Box$

The following lemma is well known.

Lemma 4.4   $\mu(\{X\in2^\omega\mid X'\equiv_TX\oplus0'\})=1$.

Proof.It suffices to show that $X'\equiv_TX\oplus0'$ whenever $X$ is random relative to $0'$. (Generalizations of this result are in Kautz's thesis [17, Theorem III.2.1].) Consider the sets $U_n=\{X\in2^\omega\mid n\in X'\}$. Obviously these sets are uniformly $\Sigma^0_1$. Let $f(n)=$ least $s$ such that $\mu(U_n\setminus U_{n,s})\le1/2^n$. Note that $f\le_T0'$. Thus $U_n\setminus U_{n,f(n)}$ is uniformly $\Sigma^{0,0'}_1$ and these sets form a Solovay test relative to $0'$. Now assume that $X$ is random relative to $0'$. By Solovay's Lemma relative to $0'$, we have $X\notin U_n\setminus U_{n,f(n)}$ for all but finitely many $n$. In other words, for all but finitely many $n$, $n\in X'$ if and only if $X\in U_{n,f(n)}$. Since $f\le_T0'$, it follows that $X'\le_TX\oplus0'$. This completes the proof.$\Box$

Theorem 4.5 (Hirschfeldt/Miller)   We can find a nonrecursive, recursively enumerable set $A$ such that $A\le_TX$ for all $X$ such that $X$ is random and almost everywhere dominating.

Proof.By Theorem 4.1 with $S=\mathrm{AED}$, it suffices to show that $\mathrm{AED}$ is $\Sigma^0_3$ and of measure $0$. We have seen in the proof of Theorem 2.2 that $\mathrm{AED}$ is $\Sigma^0_3$. To show that $\mu(\mathrm{AED})=0$, recall from [19] and [33, Section 8] that $\mathrm{AED}\subseteq\{X\mid X'\ge_T0''\}$. Thus $\mathrm{AED}$ is disjoint from the intersection of two sets: $\{X\mid X'\equiv_TX\oplus0'\}$ and $\{X\mid X\oplus0'\not\ge_T0''\}$. The first set is of measure $1$ by Lemma 4.4, and the second set is of measure $1$ by Lemma 2.9. This completes the proof.$\Box$

Remark 4.6   According to a theorem of Nies (see Section 5 below), there are uncountably many $X$'s as in Theorem 4.5 which are $\not\ge_T0'$. On the other hand, a result of Hirschfeldt/Nies/Stephan [13, Corollary 3.6] says that if $X$ is random and $\not\ge_T0'$ then any recursively enumerable $A\le_TX$ is $K$-trivial [24], i.e., low-for-random [22,24,33]. In particular, any $A$ as in Theorem 4.5 is low-for-random.

A theorem of Nies

In this section we present a new proof of a theorem of Nies [26, Theorem VI.18] refining the Jockusch/Shore Pseudojump Inversion Theorem [15, Theorem 2.1]. By a pseudojump operator we mean an operator $J_e:2^\omega\to2^\omega$ given by $J_e(X)=X\oplus W_e^X$ for all $X\in2^\omega$.

Theorem 5.1 (Nies)   Let $P\subseteq2^\omega$ be $\Pi^0_1$ of positive measure. For any pseudojump operator $J_e$ and any Turing oracle $A\ge_T0'$, we can find $B\in P$ such that $J_e(B)\equiv_TB\oplus0'\equiv_TA$.

Proof.Our proof is based on a sketch given by Kucera at an American Institute of Mathematics workshop on algorithmic randomness, August 7-11, 2006. The idea is to combine the proofs of the Pseudojump Inversion Theorem and the Kucera/Gács Theorem.

Let us write $Q_e=\{X\in2^\omega\mid\varphi_e^{(1),X}(e)\uparrow\}$. Note that $Q_e$, $e=0,1,2,\ldots$ is a standard, recursive enumeration of all $\Pi^0_1$ subsets of $2^\omega$. Given a $\Pi^0_1$ set $Q\subseteq2^\omega$, an index of $Q$ is any integer $e$ such that $Q=Q_e$. Let us say that a $\Pi^0_1$ set $P\subseteq2^\omega$ is rich if $\mu(P)>0$ and there exists a recursive function $h$ such that for all $e$, if $\emptyset\ne Q_e\subseteq P$ then $\mu(Q_e)\ge1/2^{h(e)}$.

We claim that every $\Pi^0_1$ set $P\subseteq2^\omega$ of positive measure includes a $\Pi^0_1$ set which is rich. To see this, let $n$ be such that $\mu(P)>1/2^n$. Write $Q_{e,s}=\{X\in2^\omega\mid\varphi_{e,s}^{(1),X}(e)\uparrow\}$ and note that $Q_{e,s}$, $s=0,1,2,\ldots$ is a uniformly recursive descending sequence of clopen sets such that $Q_e=\bigcap_sQ_{e,s}$. Define a recursive ascending sequence of clopen sets $V_s$, $s=0,1,2,\ldots$ as follows. Begin with $V_0=\emptyset$. Given $V_s$ define $V_{s+1}=V_s\cup\bigcup_{e<s}(Q_{e,s}\setminus V_s)$ where the union is taken over all $e<s$ such that $\mu(Q_{e,s}\setminus V_s)\le1/2^{n+e+1}$. Finally let $\widetilde{P}=P\setminus V$ where $V=\bigcup_sV_s$. Clearly $\widetilde{P}$ is $\Pi^0_1$. Moreover $\mu(V)\le\sum_e1/2^{n+e+1}=1/2^n$, hence $\mu(\widetilde{P})\ge\mu(P)-1/2^n>0$. If $\emptyset\ne Q_e\subseteq\widetilde{P}$ then for all $s>e$ we have $\mu(Q_{e,s}\setminus V_s)>1/2^{n+e+1}$, hence $\mu(Q_e)\ge1/2^{n+e+1}$. Thus $\widetilde{P}$ is rich via $h(e)=n+e+1$. This proves our claim.

To prove the theorem, let $P\subseteq2^\omega$ be $\Pi^0_1$ of positive measure. By our claim, we may safely assume that $P$ is rich. Under this assumption we shall carry out the proof of the Pseudojump Inversion Theorem ``within $P$'' to produce $B\in P$ with the desired properties.

For strings $\sigma\in2^{<\omega}$ let us write $N_\sigma=\{X\in2^\omega\mid\sigma\subset X\}$. For each string $\rho\in2^{<\omega}$ we define a string $f(\rho)\in2^{<\omega}$ and a nonempty $\Pi^0_1$ set $Q_\rho\subseteq P\cap N_{f(\rho)}$. Begin with $f(\langle\rangle)=\langle\rangle$ and $Q_{\langle\rangle}=P$. Assume inductively that $f(\rho)$ and $Q_\rho$ have already been defined.

In order to control the pseudojump $J_e(B)$, define a string $f^*(\rho)\supseteq f(\rho)$ and a nonempty $\Pi^0_1$ set $Q^*_\rho\subseteq Q_\rho\cap N_{f^*(\rho)}$ as follows. Let $m=\vert\rho\vert$. If $\exists X (X\in Q_\rho$ and $m\notin W^X_e)$, let $Q^*_\rho=\{X\in Q_\rho\mid m\notin W^X_e\}$ and let $f^*(\rho)=f(\rho)$. Otherwise, consider the least $\sigma\supseteq f(\rho)$ such that $Q_\rho\cap N_\sigma\ne\emptyset$ and $m\in W_e^\sigma$, and let $Q^*_\rho=Q_\rho\cap N_\sigma$ and $f^*(\rho)=\sigma$. Thus $f^*(\rho)$ ``decides'' whether $m\in W^B_e$ or not.

Because $P$ is rich, given an index of $Q^*_\rho$ we can effectively find $k$ such that $\mu(Q^*_\rho)\ge1/2^k$. But then there are at least two strings $\tau\supset f^*(\rho)$ of length $k+1$ such that $Q^*_\rho\cap N_\tau\ne\emptyset$. Let $f(\rho{{}^\smallfrown}\langle0\rangle)$ and $f(\rho{{}^\smallfrown}\langle1\rangle)$ be the lexicographically leftmost and rightmost such $\tau$. Let $Q_{\rho{{}^\smallfrown}\langle0\rangle}=Q^*_\rho\cap N_{f(\rho{{}^\smallfrown}\langle0\rangle)}$ and $Q_{\rho{{}^\smallfrown}\langle1\rangle}=Q^*_\rho\cap N_{f(\rho{{}^\smallfrown}\langle1\rangle)}$.

We have now defined $f(\rho)$, $f^*(\rho)$, $Q_\rho$, $Q^*_\rho$ for all $\rho$. It is straightforward to check that $f(\rho)$ and $f^*(\rho)$ and the indices of $Q_\rho$ and $Q^*_\rho$ are uniformly computable from $0'$.

Given $A\in2^\omega$ let $B=f(A)=\bigcup_mf(A\upharpoonright m)$. Then $m\in W_e^B$ if and only if $m\in W_e^{f^*(A\upharpoonright m)}$. Moreover, it is straightforward to show that $f(A\upharpoonright m)$ and $f^*(A\upharpoonright m)$ and the indices of $Q_{A\upharpoonright m}$ and $Q^*_{A\upharpoonright m}$ are uniformly computable from each of the Turing oracles $J_e(B)=B\oplus W_e^B$ and $B\oplus0'$ and $A\oplus0'$. From this, the desired conclusions follow easily.$\Box$

Theorem 5.2 (Nies)   For any pseudojump operator $J_e$ and any Turing oracle $A\ge_T0'$, we can find a random $B$ such that $J_e(B)\equiv_TB\oplus0'\equiv_TA$.

Proof.In Theorem 5.1 let $P$ be a nonempty $\Pi^0_1$ set such that $\forall X (X\in P\Rightarrow X$ is random$)$.$\Box$

Remark 5.3   Theorem 5.2 is a common generalization of several known theorems. If we omit the conclusion that $B$ is random, we get the Jockusch/Shore Pseudojump Inversion Theorem [15, Theorem 2.1]. If we keep the conclusion that $B$ is random but let $J_e$ be the identity operator, we get the Kucera/Gács Theorem [33, Theorem 3.5]. If we let $J_e$ be the Turing jump operator, we get the Friedberg Jump Inversion Theorem (see Rogers [27, Section 13.3]) with the additional conclusion that $B$ is random.

Corollary 5.4 (Nies)   For any $A\ge_T0'$ we can find a random $B<_TA$ such that $B\oplus0'\equiv_TA$ and $A$ is low-for-random relative to $B$.

Proof.By Theorem 5.2, it suffices to produce a psuedojump operator $J_e$ such that for all $B$, $J_e(B)>_TB$ and $J_e(B)$ is low-for-random relative to $B$. Such an operator is obtained by uniformly relativizing the Kucera/Terwijn [22] construction of a nonrecursive, recursively enumerable set which is low-for-random. See also the exposition in Simpson [33, Section 6].$\Box$

Corollary 5.5 (Nies)   We can find a random $B<_T0'$ such that $0'$ is low-for-random relative to $B$.

Proof.This is the special case of Corollary 5.4 in which we let $A=0'$.$\Box$

Corollary 5.6 (Nies)   There are uncountably many random $B\not\ge_T0'$ such that $0'$ is low-for-random relative to $B$.

Proof.This follows from Corollary 5.4 by considering uncountably many $A>_T0'$.$\Box$

Corollary 5.7 (Nies)   We can find a random $B<_T0'$ which is almost everywhere dominating.

Corollary 5.8 (Nies)   There are uncountably many random $B\not\ge_T0'$ such that $B$ is almost everywhere dominating.

Proof.Corollaries 5.7 and 5.8 are immediate from Corollaries 5.5 and 5.6 plus the following fact: If $0'$ is low-for-random relative to $B$ then $B$ is almost everywhere dominating. This fact is due to Kjos-Hanssen/Miller/Solomon [19]. See also the exposition in Simpson [33, Section 5].$\Box$

A theorem of Stephan

In this section we exposit the proof of the following theorem of Stephan [35].

Theorem 6.1 (Stephan)   If $B$ is random and $0'\not\le_TB$, then $\mathrm{PA}\not\le_w\{B\}$.

Proof.We shall define a recursively bounded, partial recursive function $\psi$ with the following property: For all random $B$, if $B\ge_T$ some total function extending $\psi$ then $B\ge_T0'$. This suffices to prove the theorem, because clearly every $\{B\}\ge_w\mathrm{PA}$ computes a total extension of every recursively bounded, partial recursive function (see for instance [31, Theorem 4.10]).

Recall that $0'$ is a recursively enumerable set. If $n\notin0'$ let $\psi(\langle e,n\rangle)$ be undefined for all $e$. If $n\in0'$, say $n\in0'_{s+1}\setminus0'_s$, then for each $i<2^n$ compute the rational numbers

$r_{e,n,i}=\mu(\{X\mid\varphi_{e,s}^{(1),X}(\langle e,n\rangle)\simeq i\})$

and define $\psi(\langle e,n\rangle)\simeq i$ chosen so as to minimize $r_{e,n,i}$. Note that $\psi$ is partial recursive, and $\psi(\langle e,n\rangle)\downarrow$ if and only if $n\in0'$. Moreover, if $\psi(\langle e,n\rangle)\downarrow$ then $\psi(\langle e,n\rangle)<2^n$, so $\psi$ is recursively bounded. In addition $\mu(V_{e,n})\le1/2^n$ where

$V_{e,n}=\{X\in2^\omega\mid\exists s (n\in0'_{s+1}\setminus0'_s$ and $\varphi_{e,s}^{(1),X}(\langle e,n\rangle)\simeq\psi(\langle e,n\rangle))\}$.

Assume now that $B$ is random and computes a total extension of $\psi$. Let $e$ be such that $\varphi_e^{(1),B}$ is total and extends $\psi$. Define $f(n)=$ least $s$ such that $\varphi_{e,s}^{(1),B}(\langle e,n\rangle)\downarrow$. Since $\varphi_e^{(1),B}$ is total, $f$ is total and $\le_TB$. Since $B$ is random, it follows by Solovay's Lemma that $B\notin V_{e,n}$ for all but finitely many $n$. In other words, for all but finitely many $n$, if $n\in0'_{s+1}\setminus0'_s$ then $\varphi_{e,s}^{(1),B}(\langle e,n\rangle)\not\simeq\psi(\langle e,n\rangle)$. But then, since $\psi(\langle e,n\rangle)\downarrow$ and $\varphi_e^{(1),B}$ extends $\psi$, it follows that $\varphi_{e,s}^{(1),B}(\langle e,n\rangle)\uparrow$, i.e., $f(n)>s$. We now see that, for all but finitely many $n$, if $n\in0'$ then $n\in0'_{f(n)}$. Thus $0'\le_Tf\le_TB$. This completes the proof.$\Box$

Remark 6.2   A similar proof yields the following more detailed result. Given a recursively enumerable set $A$, we can find recursively enumerable sets $A_1$ and $A_2$ such that $A_1\equiv_TA_2\equiv_TA$ and $A_1\cap A_2=\emptyset$ and, for all random $B$, if $(\exists Z\le_TB) (Z\supseteq A_1$ and $Z\cap A_2=\emptyset)$ then $A\le_TB$.

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, Bjørn Kjos-Hanssen, Manuel Lerman, and David Reed Solomon.
On a question of Dobrinen and Simpson concerning almost everywhere domination.
Journal of Symbolic Logic, 71:119-136, 2006.

3

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.

4

Z. Chatzidakis, P. Koepke, and W. Pohlers, editors.
Logic Colloquium '02: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Colloquium Logicum, held in Münster, Germany, August 3-11, 2002, volume 27 of Lecture Notes in Logic.
Association for Symbolic Logic, 2006.
VIII + 359 pages.

5

Peter Cholak, Noam Greenberg, and Joseph S. Miller.
Uniform almost everywhere domination.
Journal of Symbolic Logic, 71:1057-1072, 2006.

6

C.-T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors.
Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20 - August 15, 2005.
Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific Publishing Company, Ltd., 2007.
In preparation, to appear.

7

Joshua A. Cole and Stephen G. Simpson.
Mass problems and hyperarithmeticity.
28 November 2006.
Preprint, 20 pages, submitted for publication.

8

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

9

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

10

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.

11

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

12

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.

13

Denis R. Hirschfeldt, André Nies, and Frank Stephan.
Using random sets as oracles.
Journal of the London Mathematical Society, 2007.
Preprint, 17 pages, 2005, accepted for publication.

14

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

15

Carl G. Jockusch, Jr. and Richard A. Shore.
Pseudo jump operators I: the r.e. case.
Transactions of the American Mathematical Society, 275:599-609, 1983.

16

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.

17

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

18

Bjørn Kjos-Hanssen.
Low for random reals and positive-measure domination.
Proceedings of the American Mathematical Society, 2007.
Preprint, 12 pages, 2005, to appear.

19

Bjørn Kjos-Hanssen, Joseph S. Miller, and David Reed Solomon.
Lowness notions, measure and domination.
April 2006.
Preprint, 3 pages, in preparation, to appear.

20

Antonín Kucera.
Measure, $\Pi^0_1$ classes and complete extensions of PA.
In [10], pages 245-259, 1985.

21

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

22

Antonín Kucera and Sebastiaan A. Terwijn.
Lowness for the class of random sets.
Journal of Symbolic Logic, 64:1396-1402, 1999.

23

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

24

André Nies.
Lowness properties and randomness.
Advances in Mathematics, 197:274-305, 2005.

25

André Nies.
Eliminating concepts.
In [6], 2006.
Preprint, 23 pages, to appear.

26

André Nies.
Computability and Randomness.
Clarendon Press, Oxford, 9 May 2007.
Preprint, X + 291 pages, in preparation, to appear.

27

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

28

Gerald E. Sacks.
Degrees of Unsolvability.
Number 55 in Annals of Mathematics Studies. Princeton University Press, 2nd edition, 1966.

29

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

30

Dana S. Scott and Stanley Tennenbaum.
On the degrees of complete extensions of arithmetic (abstract).
Notices of the American Mathematical Society, 7:242-243, 1960.

31

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

32

Stephen G. Simpson.
Some fundamental issues concerning degrees of unsolvability.
In [6], 2005.
Preprint, 21 pages, to appear.

33

Stephen G. Simpson.
Almost everywhere domination and superhighness.
Mathematical Logic Quarterly, 53:462-482, 2007.

34

Stephen G. Simpson.
An extension of the recursively enumerable Turing degrees.
Journal of the London Mathematical Society, 75:287-297, 2007.

35

Frank Stephan.
Martin-Löf random and PA-complete sets.
In [4], pages 341-347, 2006.

About this document ...

Mass Problems and
Almost Everywhere Domination

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 massaed

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