Almost everywhere domination and superhighness

Stephen G. Simpson

Pennsylvania State University

First draft: July 5, 2006
This draft: April 28, 2008

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

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

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

I thank Esteban Gomez-Riviere and Joseph S. Miller for useful discussions.

Mathematical Logic Quarterly, 53, 2007, pp. 462-482.

Abstract:

Let $\omega$ denote the set of natural numbers. For functions $f,g:\omega\to\omega$, we say that $f$ is dominated by $g$ if $f(n)<g(n)$ for all but finitely many $n\in\omega$. We consider the standard ``fair coin'' probability measure on the space $2^\omega$ of infinite sequences of 0's and 1's. A Turing oracle $B$ is said to be almost everywhere dominating if, for measure one many $X\in2^\omega$, each function which is Turing computable from $X$ is dominated by some function which is Turing computable from $B$. Dobrinen and Simpson have shown that the almost everywhere domination property and some of its variant properties are closely related to the reverse mathematics of measure theory. In this paper we exposit some recent results of Kjos-Hanssen, Kjos-Hanssen/Miller/Solomon, and others concerning $\mathit{LR}$-reducibility and almost everywhere domination. We also prove the following new result: If $B$ is almost everywhere dominating, then $B$ is superhigh, i.e., $0''$ is truth-table computable from $B'$, the Turing jump of $B$.

Contents

• Introduction
• Notation
• Randomness
• $\mathit{LR}$-reducibility
• Almost everywhere domination
• Some examples
• Remarks on Theorem 5.13
• Superhighness
• Counterexamples via duality
• Prefix-free Kolmogorov complexity
• Bibliography

Introduction

The concept of almost everywhere domination was originally introduced by Dobrinen and Simpson [7] with applications to the reverse mathematics of measure theory [26, Section X.1]. Subsequent work by Binns, Cholak, Greenberg, Kjos-Hanssen, Lerman, Miller, and Solomon [2,5,13,14] has greatly illuminated this concept and established its close relationship to the decisive results on $K$-triviality and low-for-randomness which are due to Downey, Hirschfeldt, Kucera, Nies, Stephan, and Terwijn [16,9,21,11]. The purpose of this paper is to update the Dobrinen/Simpson account of almost everywhere domination by expositing this subsequent research. We provide introductory accounts of Martin-Löf randomness, $\mathit{LR}$-reducibility, and prefix-free Kolmogorov complexity as they relate to almost everywhere domination. We also prove a new result: If $B$ is almost everywhere dominating, then $B$ is superhigh.

The reader who is familiar with the basic concepts and results of recursion theory will find that our exposition in this paper is self-contained, except for some peripheral remarks. Throughout this paper we give full proofs and strive for simplicity and clarity.

Notation

We use standard recursion-theoretic notation and terminology from Rogers [25]. We write r.e. as an abbreviation for ``recursively enumerable''. If $C$ is a Turing oracle, we write $C$-recursive for ``recursive relative to $C$'', $C$-r.e. for ``recursively enumerable relative to $C$'', etc. We write $\omega=\{0,1,\ldots,n,\ldots\}$ to denote the set of natural numbers. We often identify Turing oracles with subsets of $\omega$. If $E$ is an expression denoting a natural number which may or may not be defined, we write $E\downarrow$ to mean that $E$ is defined, and $E\uparrow$ to mean that $E$ is undefined. 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 undefined or both defined with the same value. If $C$ is a Turing oracle, we write

$C'=\{e\in\omega\mid\varphi_e^{(1),C}(0)\downarrow\}=$ the Turing jump of $C$.

In particular $0'=\{e\in\omega\mid\varphi_e^{(1)}(0)\downarrow\}=$ a Turing oracle for the Halting Problem. For $A,B\subseteq\omega$ we write

$A\oplus B=\{2n\mid n\in A\}\cup\{2n+1\mid n\in B\}$,

the Turing join of $A$ and $B$. We write $\le_T$ to denote Turing reducibility. Thus $A\le_TB$ means that $A$ is Turing computable from $B$. For $A\subseteq\omega$ we write $\overline{A}=\omega\setminus A$, the complement of $A$. We sometimes identify $A\subseteq\omega$ with its characteristic function $\chi_A:\omega\to\{0,1\}$ given by $\chi_A(n)=1$ if $n\in A$, $0$ if $n\notin A$.

We write $2^\omega$ to denote the Cantor space, i.e., the set of total functions $X:\omega\to\{0,1\}$. We write $2^{<\omega}$ to denote the set of strings, i.e., finite sequences of $0$'s and $1$'s. For $\sigma\in2^{<\omega}$ we write $\sigma=\langle i_0,\ldots,i_{n-1}\rangle$ where $n=\vert\sigma\vert=$ the length of $\sigma$. The empty string, denoted $\langle\rangle$, is the unique string of length $0$. Given $X\in2^\omega$ and $n\in\omega$, we have a string $X\upharpoonright n=\langle X(0),\ldots,X(n-1)\rangle$ of length $n$. For $\sigma\in2^{<\omega}$ and $X\in2^\omega$, we write $\sigma\subset X$ to mean that $\sigma$ is a prefix of $X$, i.e., $\sigma=X\upharpoonright \vert\sigma\vert$. For $\sigma,\tau\in2^{<\omega}$, we write $\sigma\subset\tau$ to mean that $\sigma$ is a prefix of $\tau$, i.e., a proper initial segment of $\tau$. We write $\sigma{{}^\smallfrown}\tau=$ the concatenation, $\sigma$ followed by $\tau$. Thus $\vert\sigma{{}^\smallfrown}\tau\vert=\vert\sigma\vert+\vert\tau\vert$. Moreover, $\sigma\subset\tau$ if and only if $\sigma{{}^\smallfrown}\rho=\tau$ for some $\rho\ne\langle\rangle$. For $\sigma\in2^{<\omega}$ and $X\in2^\omega$ we write $\sigma{{}^\smallfrown}X=$ the concatenation, $\sigma$ followed by $X$. Thus $\sigma\subset X$ if and only if $\sigma{{}^\smallfrown} Y=X$ for some $Y$.

Given $\sigma\in2^{<\omega}$, we write $N_\sigma=\{X\in2^\omega\mid\sigma\subset X\}$. Thus $N_\sigma$ is a basic open neighborhood in the Cantor space. The fair-coin probability measure $\mu$ on $2^\omega$ is defined by $\mu(N_\sigma)=1/2^{\vert\sigma\vert}$. In particular $\mu(2^\omega)=1$. A set $S\subseteq2^{<\omega}$ is said to be prefix-free if there are no $\sigma,\tau\in S$ such that $\sigma\subset\tau$. Note that if $S$ is prefix-free then $\mu(\bigcup_{\sigma\in S}N_\sigma)=\sum_{\sigma\in S}1/2^{\vert\sigma\vert}$.

We make extensive use of the relativized arithmetical hierarchy of subsets of $2^\omega$. See Rogers [25, Section 15.1]. If $C$ is a Turing oracle, then by definition $U\subseteq2^\omega$ is $\Sigma^{0,C}_1$ if and only if $U=\bigcup_{\sigma\in S}N_\sigma$ for some $C$-r.e. set $S\subseteq2^{<\omega}$. A well known fact is that for any such $U$ we can find such an $S$ which is prefix-free. By definition, $P\subseteq2^\omega$ is $\Pi^{0,C}_1$ if and only if its complement $\overline{P}=2^\omega\setminus P$ is $\Sigma^{0,C}_1$. Note that $\mu(P)=1-\mu(\overline P)$. Because $2^\omega$ is compact, a $\Sigma^{0,C}_1$ set $U\subseteq2^\omega$ is $\Pi^{0,C}_1$ if and only if $U=\bigcup_{\sigma\in F}N_\sigma$ for some finite $F\subseteq2^{<\omega}$. This is the same as saying that $U$ is clopen, i.e., closed and open, in $2^\omega$. Again, we may take $F$ to be prefix-free.

Randomness

Our work in this paper is based on a robust concept of randomness relative to a Turing oracle. The original, unrelativized concept is due to Martin-Löf [17] and has been studied by Kucera [15] and many others.

Definition 3.1 (Martin-Löf 1966)   Let $C$ be a Turing oracle. We say that $X\in2^\omega$ is $C$-random if $X\notin\bigcap_nU^C_n$ for all uniformly $\Sigma^{0,C}_1$ sequences of sets $U_n^C\subseteq2^\omega$, $n=0,1,2,\ldots$ such that $\mu(U^C_n)\le1/2^n$ for all $n$. Such a sequence is called a Martin-Löf test for $C$-randomness.

Theorem 3.2 (Martin-Löf 1966, Kucera 1985)   We can construct a universal Martin-Löf test. In other words, we can find uniformly $\Sigma^{0,C}_1$ sets $U_n^C$, $n=0,1,2,\ldots$ such that $\mu(U_n^C)\le1/2^n$ and, for all $X\in2^\omega$ and all Turing oracles $C$, $X$ is $C$-random if and only if $X\notin\bigcap_nU_n^C$.

Proof.Let $V^C_i$, $i=0,1,2,\ldots$ be a standard, uniform enumeration of all $\Sigma^{0,C}_1$ subsets of $2^\omega$. For $s=0,1,\ldots$ let $V^C_{i,s}$ be the set of $X\in2^\omega$ which get into $V^C_i$ by means of a computation in $\le s$ steps using only oracle information from $C\upharpoonright s$. Thus $V^C_{i,0}\subseteq V^C_{i,1}\subseteq\cdots\subseteq V^C_{i,s}\subseteq\cdots$, $s=0,1,\ldots$ is a uniformly $C$-recursive sequence of clopen sets, and $V_i^C=\bigcup_sV^C_{i,s}$. For rational numbers $r$ let

$$V^C_i[r]=\bigcup_{\mu(V^C_{i,s})\le r}V^C_{i,s} .$$

Intuitively, $V^C_i[r]$ is just $V^C_i$ enumerated so long as its measure is $\le r$. Note that $V^C_i[r]$ is uniformly $\Sigma^{0,C}_1$, and $\mu(V^C_i[r])\le r$, and $V^C_i[r]=V^C_i$ if and only if $\mu(V^C_i)\le r$. Now for all $e,n\in\omega$ let $\widetilde{U}^C_{e,n}=V_i^C[1/2^n]$ if $\varphi^{(1)}_e(n)\simeq i$, and $\emptyset$ if $\varphi^{(1)}_e(n)\uparrow$. Again $\widetilde{U}^C_{e,n}$ is uniformly $\Sigma^{0,C}_1$. Moreover, for each $e$, the sequence $\widetilde{U}^C_{e,n}$, $n=0,1,\ldots$ is a Martin-Löf test, and all Martin-Löf tests occur in this way. Finally let $U^C_n=\bigcup_e\widetilde{U}^C_{e,e+n+1}$. Then $U^C_n$ is uniformly $\Sigma^{0,C}_1$, and $\mu(U^C_n)\le\sum_e1/2^{e+n+1}=1/2^n$ for all $n$, so $U^C_n$, $n=0,1,\ldots$ is a Martin-Löf test. Moreover, for an arbitrary Martin-Löf test $\widetilde{U}^C_{e,n}$, $n=0,1,\ldots$, we have $\bigcap_n\widetilde{U}^C_{e,n}\subseteq\bigcap_nU^C_n$. Thus $U^C_n$, $n=0,1,\ldots$ is a universal Martin-Löf test.$\Box$

Corollary 3.3 (Kucera 1985)   For any Turing oracle $C$, the set

$R^C=\{X\in2^\omega\mid X$ is $C$-random$\}$

is uniformly $\Sigma^{0,C}_2$ and of measure $1$.

Proof.By Theorem 3.2 let $U^C_n$, $n=0,1,\ldots$ be a universal Martin-Löf test for $C$-randomness. Then $R^C=2^\omega\setminus\bigcap_nU^C_n$. Moreover $U_n^C$ is uniformly $\Sigma^{0,C}_1$, hence $\bigcap_nU^C_n$ is uniformly $\Pi^{0,C}_2$, hence $R^C$ is uniformly $\Sigma^{0,C}_2$. Also $\mu(U_n^C)\le1/2^n$ for all $n$, hence $\mu(\bigcap_nU_n^C)=0$, hence $\mu(R^C)=1$.$\Box$

We now present van Lambalgen's Theorem, from [30].

Lemma 3.4   Assume that $A\oplus B$ is random. Then $A$ is $B$-random, and $B$ is $A$-random. In particular, $A$ and $B$ are random.

Proof.Suppose for instance that $B$ is not $A$-random. Then $B\in\bigcap_nV_n^A$ where $V_n^A$ is uniformly $\Sigma^{0,A}_1$ of measure $\le1/2^n$. Let $W_n=\{X\oplus Y\mid X\in2^\omega,Y\in V_n^X[1/2^n]\}$ and note that $W_n$ is uniformly $\Sigma^0_1$ of measure $\le1/2^n$. We have $A\oplus B\in\bigcap_nW_n$, contradicting the assumption that $A\oplus B$ is random. $\Box$

Lemma 3.5 (Solovay's Lemma)   Assume $A$ is random. Let $U_n\subseteq2^\omega$, $n=0,1,\ldots$ be uniformly $\Sigma^0_1$ such that $\sum_{n=0}^\infty\mu(U_n)<\infty$. Then $\exists^{<\infty}n (A\in U_n)$, i.e., $\{n\mid A\in U_n\}$ is finite.

Proof.For each $k$ let $W_k=\{X\mid\exists^{\ge k}n (X\in U_n)\}$. Let $c$ be such that $\sum_{n=0}^\infty\mu(U_n)\le c$. We claim that $\mu(W_k)\le c/k$. To see this, let $W_k^N=\{X\mid(\exists^{\ge k}n\le N) (X\in U_n)\}$ and note that $W_k=\bigcup_NW_k^N$. For all $N$ we have

$$\begin{array}{rl} c & \ge \sum_{n=0}^\infty\mu(U_n) ... ...^\omega}k W_k^N(X) dX = k \mu(W_k^N) \end{array}$$

so $\mu(W_k^N)\le c/k$ for all $N$. It follows that $\mu(W_k)\le c/k$, and our claim is proved. Since $A$ is random and $W_k$ is uniformly $\Sigma^0_1$, we have $A\notin\bigcap_kW_k$, hence $A\notin W_k$ for some $k$, hence $\exists^{<k}n (A\in U_n)$. This proves the lemma.$\Box$

Theorem 3.6 (van Lambalgen's Theorem)   $A\oplus B$ is random if and only if $A$ is random and $B$ is $A$-random.

Proof.The ``only if'' direction follows from Lemma 3.4. For the ``if'' direction, assume that $A\oplus B$ is not random. We have $A\oplus B\in\bigcap_nW_n$ where $W_n$ is uniformly $\Sigma^0_1$ with $\mu(W_n)\le1/2^n$. By passing to a subsequence, we may assume that $\mu(W_n)\le1/2^{2n}$. Let $U_n=\{X\mid\mu(\{Y\mid X\oplus Y\in W_n\})>1/2^n\}$ and note that $U_n$ is uniformly $\Sigma^0_1$. Moreover $\mu(U_n)\le1/2^n$ for all $n$, because otherwise we would have

$$\mu(W_n) > \mu(U_n)\cdot\frac1{2^n} > \frac1{2^n}\cdot\frac1{2^n} = \frac1{2^{2n}} ,$$

a contradiction. Since $A$ is random, it follows by Lemma 3.5 that $\{n\mid A\in U_n\}$ is finite. Thus for all but finitely many $n$ we have $A\notin U_n$, i.e., $\mu(\{Y\mid A\oplus Y\in W_n\})\le1/2^n$. Let $V_n^A=\{Y\mid A\oplus Y\in W_n\}$. Then $\mu(V_n^A)\le1/2^n$ for all but finitely many $n$, and $V_n^A$ is uniformly $\Sigma^{0,A}_1$. Moreover $B\in\bigcap_nV_n^A$, contradicting the assumption that $B$ is $A$-random.$\Box$

Next we present the Kucera/Gács Theorem, from Kucera [15].

Lemma 3.7   Let $P\subseteq2^\omega$ be $\Pi^0_1$ of positive measure. Then for all $X\in2^\omega$ there exists $Y\in P$ such that $Y\le_TX\oplus0'$ and $X\le_TY$.

Proof.Claim: If $\mu(P\cap N_\sigma)\ge1/2^k$ where $k\ge1$, then there are at least two strings $\tau\supset\sigma$ such that $\vert\tau\vert=2k$ and $\mu(P\cap N_\tau)\ge1/2^{4k}$.

To prove the claim, note first that $\mu(N_\sigma)=1/2^{\vert\sigma\vert}\ge1/2^k$, hence $\vert\sigma\vert\le k<2k$ since $k\ge1$. If the conclusion of the claim were false, we would have

$$\begin{array}{lclclcl} \mu(P\cap N_\sigma) & = & \displays... ...\frac1{2^{4k}} & \le & \displaystyle\frac1{2^k} \end{array}$$

contradicting the hypothesis of the claim.

To prove Lemma 3.7, assume that $P\subseteq2^\omega$ is $\Pi^0_1$ with $\mu(P)>0$, say $\mu(P)\ge1/2^k$ where $k\ge1$. Note that $N_{\langle\rangle}=2^\omega$, hence $\mu(P\cap N_{\langle\rangle})=\mu(P)\ge1/2^k$. Applying our claim repeatedly, define $f:2^{<\omega}\to2^{<\omega}$ as follows. Let $f(\langle\rangle)=\langle\rangle$. Suppose inductively that $f(\rho)$ has already been defined. Let $k_i=4^ik$ where $i=\vert\rho\vert$. Let $f(\rho{{}^\smallfrown}\langle0\rangle)$ (respectively $f(\rho{{}^\smallfrown}\langle1\rangle)$) be the lexicographically leftmost (respectively rightmost) $\tau\supset f(\rho)$ such that $\vert\tau\vert=2k_i$ and $\mu(P\cap N_\tau)\ge1/2^{4k_i}$. Our claim implies that $f(\rho{{}^\smallfrown}\langle0\rangle)$ and $f(\rho{{}^\smallfrown}\langle1\rangle)$ exist and are incompatible. It is straightforward to check that $f\le_T0'$.

Given $X\in2^\omega$, let $Y=f(X)=\bigcup_if(X\upharpoonright i)$. Clearly $Y\in P$ and $Y\le_TX\oplus0'$. We claim that $X\le_TY$. To prove this, we describe how to compute $X$ using an oracle for $Y$. Let $P=\bigcap_sP_s$ where $P_0\supseteq P_1\supseteq\cdots\supseteq P_s\supseteq\cdots$ is a recursive sequence of clopen sets. Suppose we have already computed $\rho=X\upharpoonright i$. We also have $f(\rho)=Y\upharpoonright 2k_{i-1}$ if $i>0$, or $\langle\rangle$ if $i=0$. Our construction implies that $Y\upharpoonright 2k_i$ is either the leftmost or the rightmost $\tau\supset f(\rho)$ of length $2k_i$ such that $\mu(P\cap N_\tau)\ge1/2^{4k_i}$. Therefore, for all sufficiently large stages $s$, we will have $\mu(P^s\cap N_\tau)<1/2^{4k_i}$ for all $\tau\supset f(\rho)$ of length $2k_i$ lying to the left (respectively right) of $Y\upharpoonright 2k_i$. When such a stage $s$ is reached, then at that point we see that $X(i)=0$ (respectively $X(i)=1$). This completes the proof.$\Box$

Theorem 3.8 (Kucera/Gács Theorem)   For any $X\ge_T0'$ we can find a random $Y$ such that $Y\equiv_TX$.

Proof.By Corollary 3.3 let $P\subseteq2^\omega$ be $\Pi^0_1$ of positive measure such that $\forall Y (Y\in P\Rightarrow Y$ is random$)$. Applying Lemma 3.7 to any $X\ge_T0'$, we obtain $Y\in P$ such that $X\equiv_TY$.$\Box$

Corollary 3.9   Assume that $A$ is random and $A\le_TB$ and $B$ is $C$-random and $C\ge_T0'$. Then $A$ is $C$-random.

Proof.Since $C\ge_T0'$, we may assume by the Kucera/Gács Theorem that $C$ is random. Since $B$ is $C$-random and $C$ is random, it follows by van Lambalgen's Theorem that $B\oplus C$ is random, hence $C$ is $B$-random. Since $A\le_TB$, it follows that $C$ is $A$-random. Now, since $A$ is random, it follows that $A\oplus C$ is random, hence $A$ is $C$-random.$\Box$

Remarkably, the previous corollary holds even without the assumption $C\ge_T0'$. We mention without proof the following theorem of Miller/Yu [19].

Theorem 3.10 (Miller/Yu 2004)   If $A$ is random and $A\le_TB$ where $B$ is $C$-random, then $A$ is $C$-random.

$\mathit{LR}$-reducibility

In this section we study the following reducibility notion, which was originally introduced by Nies [21, Section 8].

Definition 4.1 (Nies 2002)   Let $A$ and $B$ be Turing oracles. We say that $A$ is $\mathit{LR}$-reducible to $B$, abbreviated $A\le_\mathit{LR}B$, if

$\forall X (X$ is $B$-random $\Rightarrow X$ is $A$-random$)$.

Remark 4.2   Obviously the binary relation $\le_\mathit{LR}$ is transitive and reflexive. Note also that, as a reducibility relation, $\le_\mathit{LR}$ is at least as coarse as Turing reducibility. In other words, $A\le_TB$ implies $A\le_\mathit{LR}B$. In Section 6 we shall construct an $A\le_\mathit{LR}0$ such that $A\not\le_T0$, i.e., $A$ is not recursive. Thus $\le_\mathit{LR}$ does not coincide with $\le_T$.

Remark 4.3   Evidently the reducibility relation $\le_\mathit{LR}$ is closely related to the notion of low-for-randomness, which was first introduced by Zambella [31] and has been studied extensively by Kucera/Terwijn [16], Terwijn/Zambella [29], Downey/Hirschfeldt/Nies/Stephan [9], Hirschfeldt/Nies/Stephan [11], and Nies [21]. By definition, $A$ is low-for-random if and only if $A\le_\mathit{LR}0$. Relativizing to $B$, we see that $A$ is low-for-random relative to $B$ if and only if $A\oplus B\le_\mathit{LR}B$.

However, caution is required, because in general $A\le_\mathit{LR}B$ is not equivalent to $A$ being low-for-random relative to $B$. In Section 6 we shall construct a Turing oracle $C$ such that $0'\le_\mathit{LR}C$ yet $0'$ is not low-for-random relative to $C$. We shall also see that the binary relation ``$A$ is low-for-random relative to $B$'' is not transitive. Indeed, we shall construct Turing oracles $B$ and $C$ such that $B\le_T0'\le_\mathit{LR}B\le_TC$, hence $0'$ is low-for-random relative to $B$ and $B$ is low-for-random relative to $C$, yet $0'$ is not low-for-random relative to $C$. See Theorem 6.10.

Remark 4.4   Another way to distinguish $\le_\mathit{LR}$ from relative low-for-randomness is as follows. It can be shown (see Lemma 7.4 and Remark 10.12) that if $A$ is low-for-random relative to $B$ then $A\le_TB'$, hence for each $B$ there are only countably many such $A$. But Miller and Yu [19,18] have constructed a $B$ such that $\{A\mid A\le_\mathit{LR}B\}$ is uncountable. Recently Barmpalias/Lewis/Soskova [1] have shown that this holds for any $B$ which is generalized superhigh.

Remark 4.5   On the other hand, consider the equivalence relation $\equiv_\mathit{LR}$ defined by letting $A\equiv_\mathit{LR}B$ if and only if $A\le_\mathit{LR}B$ and $B\le_\mathit{LR}A$. It can be shown (see Remark 10.12) that if $A\equiv_\mathit{LR}B$ then $A$ is low-for-random relative to $B$ and $B$ is low-for-random relative to $A$. It follows that each $\equiv_\mathit{LR}$-equivalence class is countable.

We now prove the following theorem due to Kjos-Hanssen [13].

Theorem 4.6 (Kjos-Hanssen 2005)   The following statements are pairwise equivalent.

1. $A\le_\mathit{LR}B$.
2. Each $\Pi^{0,A}_1$ set of positive measure includes a $\Pi^{0,B}_1$ set of positive measure.
3. There exists a $\Pi^{0,A}_1$ set $P$ such that $\forall X (X\in P\Rightarrow X$ is $A$-random$)$ and $P$ includes a $\Pi^{0,B}_1$ set of positive measure.
4. There exists a $\Pi^{0,B}_1$ set $Q$ of positive measure such that $\forall Y (Y\in Q\Rightarrow Y$ is $A$-random$)$.

Proof.In order to prove Theorem 4.6, we first prove several lemmas.

Lemma 4.7   Fix a Turing oracle $B$, and let $P\subseteq2^\omega$ be $\Pi^{0,B}_1$. The following statements are pairwise equivalent.

(a)

$P$ is of positive measure.

(b)

$\exists Q (Q\subseteq P$ and $Q$ is nonempty $\Pi^{0,B}_1$ and $\forall X (X\in Q\Rightarrow X$ is $B$-random$))$.

(c)

$\exists X (X\in P$ and $X$ is $B$-random$)$.

Proof.By Corollary 3.3, $\{X\in2^\omega\mid X$ is $B$-random$\}$ is $\Sigma^{0,B}_2$ and of measure 1. From this it follows easily that (a) ${}\Rightarrow {}$(b). Trivially (b) ${}\Rightarrow {}$(c). In order to prove (c) ${}\Rightarrow {}$(a), assume $\mu(P)=0$. We have $P=\bigcap_sP_s$ where $P_0\supseteq P_1\supseteq\cdots\supseteq P_s\supseteq\cdots$ is a $B$-recursive sequence of clopen sets. Hence $\lim_s\mu(P_s)=\mu(P)=0$. Let $U_k=P_{f(k)}$ where $f(k)=$ least $s$ such that $\mu(P_s)\le1/2^k$. Then $U_k$, $k=1,2,\ldots$ is a Martin-Löf test for $B$-randomness, and $P=\bigcap_kU_k$. Hence no $X\in P$ is $B$-random, Q.E.D.$\Box$

Lemma 4.8   Assume that $Q$ is $\Pi^{0,B}_1$ such that $\forall X (X\in Q\Rightarrow X$ is $B$-random$)$. Then $\forall\sigma (Q\cap N_\sigma\ne\emptyset\Rightarrow Q\cap N_\sigma$ is of positive measure$)$.

Proof.This follows easily from Lemma 4.7.$\Box$

The proof of Theorem 4.6 is based on the following idea, which goes back to Kucera [15].

Definition 4.9 (Kucera 1985)   Let $U,V\subseteq2^\omega$ be $\Sigma^{0,A}_1$. We define a product operation. Let $U=\bigcup_{\sigma\in S}N_\sigma$ and $V=\bigcup_{\tau\in T}N_\tau$ where $S,T\subseteq2^{<\omega}$ are $A$-r.e. and prefix-free. We define the product

$$UV=\bigcup_{\sigma\in S,\tau\in T}N_{\sigma{{}^\smallfrown}\tau} .$$

Note that $\{\sigma{{}^\smallfrown}\tau\mid\sigma\in S,\tau\in T\}$ is again $A$-r.e. and prefix-free. Note also that:

(a)

$UV$ is $\Sigma^{0,A}_1$.

(b)

Given indices of $U$ and $V$ qua $\Sigma^{0,A}_1$ sets, we can compute an index of $UV$ qua $\Sigma^{0,A}_1$ set.

(c)

$UV\subseteq U$.

(d)

$\mu(UV)=\mu(U)\mu(V)$.

(e)

The product is associative, i.e., $(UV)W=U(VW)$.

Definition 4.10 (Kucera 1985)   Dually, let $P,Q\subseteq2^\omega$ be $\Pi^{0,A}_1$. We define the product $PQ=\overline{\overline P \overline Q}$, where $\overline P=2^\omega\setminus P$. Note that:

(a)

$PQ$ is $\Pi^{0,A}_1$.

(b)

Given indices of $P$ and $Q$ qua $\Pi^{0,A}_1$ sets, we can compute an index of $PQ$ qua $\Pi^{0,A}_1$ set.

(c)

$PQ\supseteq P$.

(d)

$\mu(PQ)=1-(1-\mu(P))(1-\mu(Q))$.

(e)

The product is associative, i.e., $(PQ)R=P(QR)$.

We now begin the proof of Theorem 4.6. Let us say that $P\subseteq2^\omega$ is fat if it includes a $\Pi^{0,B}_1$ set of positive measure. The implication $1\Rightarrow 2$ of Theorem 4.6 may be rephrased as follows:

If $A\le_\mathit{LR}B$, then every $\Pi^{0,A}_1$ set of positive measure is fat.

Our proof of this statement will use the following lemma.

Lemma 4.11 (Kjos-Hanssen 2005)   Let $P,Q\subseteq2^\omega$ be $\Pi^{0,A}_1$. If $PQ$ is fat, then at least one of $P$ and $Q$ is fat.

Proof.Let $U=\overline P$. Then $U$ is $\Sigma^{0,A}_1$, say $U=\bigcup_{\sigma\in S}N_\sigma$ where $S\subseteq2^{<\omega}$ is $A$-r.e. and prefix-free. We have $PQ=P\cup\bigcup_{\sigma\in S}(\sigma{{}^\smallfrown}Q)$ where $\sigma{{}^\smallfrown}Q=\{\sigma{{}^\smallfrown}X\mid X\in Q\}$. Suppose now that $PQ$ is fat, say $R\subseteq PQ$ where $R$ is $\Pi^{0,B}_1$ and $\mu(R)>0$. By Lemmas 4.7 and 4.8 we may safely assume that $\forall X (X\in R\Rightarrow X$ is $B$-random$)$, hence $\forall\sigma (R\cap N_\sigma\ne\emptyset\Rightarrow \mu(R\cap N_\sigma)>0)$. If $R\subseteq P$ then $P$ is fat and we are done. Otherwise there exists $\sigma\in S$ such that $R\cap N_\sigma\ne\emptyset$, hence $\mu(R\cap N_\sigma)>0$. But $R\cap N_\sigma=R\cap(\sigma{{}^\smallfrown} Q)\subseteq\sigma{{}^\smallfrown}Q$, hence $\sigma{{}^\smallfrown}Q$ is fat, hence $Q$ is fat, Q.E.D.$\Box$

We now prove the implication $1\Rightarrow 2$ of Theorem 4.6. Assume $A\le_\mathit{LR}B$ and suppose that $P$ is $\Pi^{0,A}_1$ of positive measure. We must show that $P$ is fat.

Let $U=\overline P$, so $\mu(U)=1-\mu(P)<1$. Let $n$ be such that $\mu(U)^n<1/2$. Let $U^k=U\cdots U$ ($k$ times) and $P^k=P\cdots P$ ($k$ times). Note that $U^k=\overline{P^k}$. We have $\mu(U^{nk})=\mu(U)^{nk}<1/2^k$, hence $U^{nk}$, $k=1,2,\dots$ is a Martin-Löf test for $A$-randomness. It follows that $\forall X (X\in\bigcap_kU^k\Rightarrow X$ is not $A$-random$)$.

By Lemma 4.7 let $Q$ be nonempty $\Pi^{0,B}_1$ such that $\forall X (X\in Q\Rightarrow X$ is $B$-random$)$. By Lemma 4.8 we have $\forall\sigma (Q\cap N_\sigma\ne\emptyset\Rightarrow \mu(Q\cap N_\sigma)>0)$.

We claim that $\exists\sigma \exists k (Q\cap N_\sigma\ne\emptyset$ and $Q\cap N_\sigma\cap U^k=\emptyset)$. Otherwise we would have $\forall\sigma \forall k (Q\cap N_\sigma\ne\emptyset\Rightarrow Q\cap N_\sigma\cap U^k\ne\emptyset)$. Therefore, since $U^k$ is $\Sigma^{0,A}_1$, we would be able to find $\sigma_0\subset\sigma_1\subset\cdots\subset\sigma_k\subset\cdots$ such that $N_{\sigma_k}\cap Q\ne\emptyset$ and $N_{\sigma_k}\subseteq U^k$ for all $k$. Setting $X=\bigcup_k\sigma_k$ we would have $X\in Q$ and $X\in\bigcap_kU^k$. Thus $X$ would be $B$-random but not $A$-random, contradicting our assumption $A\le_\mathit{LR}B$. This proves our claim.

Let $\sigma$ and $k$ be as in our claim. We then have $Q\cap N_\sigma\subseteq P^k$, hence $P^k$ is fat. It follows by Lemma 4.11 that $P$ is fat. This completes the proof of $1\Rightarrow 2$.

It remains to prove $2\Rightarrow 3$ and $3\Rightarrow 4$ and $4\Rightarrow 1$. The implication $2\Rightarrow 3$ follows easily from Lemma 4.7. The implication $3\Rightarrow 4$ is trivial. In order to prove $4\Rightarrow 1$, we first prove the following lemma due to Kucera [15].

Lemma 4.12 (Kucera 1985)   Let $P$ be $\Pi^{0,A}_1$ of positive measure. Then for all $A$-random $X$ there exist $\sigma$ and $Y$ such that $X=\sigma{{}^\smallfrown} Y$ and $Y\in P$.

Proof.Suppose $P$ is $\Pi^{0,A}_1$ of positive measure. As before let $U=\overline{P}=\bigcup_{\sigma\in S}N_\sigma$ where $S$ is $A$-r.e. and prefix-free. Define $U^k$ and $P^k$ as before. Suppose $X$ is $A$-random. Since $U^k$, $k=1,2,\ldots$ is a Martin-Löf test for $A$-randomness, we have $X\notin U^k$ for some $k$. Choosing the least such $k$, we have $X\in U^{k-1}\cap P^k$, i.e., $X=\sigma_1{{}^\smallfrown}\cdots{{}^\smallfrown}\sigma_{k-1}{{}^\smallfrown}Y$ for some $\sigma_1,\ldots,\sigma_{k-1}\in S$ and $Y\in P$. Letting $\sigma=\sigma_1{{}^\smallfrown}\cdots{{}^\smallfrown}\sigma_{k-1}$ we have $X=\sigma{{}^\smallfrown} Y$, Q.E.D.$\Box$

We now prove $4\Rightarrow 1$. Assuming 4, let $Q$ be $\Pi^{0,B}_1$ of positive measure such that $\forall Y (Y\in Q\Rightarrow Y$ is $A$-random$)$. To prove 1, suppose $X$ is $B$-random. Applying Lemma 4.12 with $Q$ and $B$ in place of $P$ and $A$, we have $X=\sigma{{}^\smallfrown} Y$ for some $Y\in Q$. It follows that $Y$ is $A$-random. Hence $X$ is $A$-random. Thus $A\le_\mathit{LR}B$, Q.E.D.

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

Corollary 4.13 (Kjos-Hanssen 2005)   The binary relation $A\le_\mathit{LR}B$ is $\Sigma^0_3$.

Proof.Let $P_i^C$, $i\in\omega$ be a standard, uniform enumeration of all $\Pi^{0,C}_1$ subsets of $2^\omega$, where $C$ is a Turing oracle. Fix $e\in\omega$ such that for all $C$, $P_e^C$ is of positive measure¹ and $\forall X (X\in P_e^C\Rightarrow X$ is $C$-random$)$. By Theorem 4.6, $A\le_\mathit{LR}B$ is equivalent to $\exists i (\mu(P_i^B)>0$ and $P_i^B\subseteq P_e^A)$. A Tarski/Kuratowski computation (see Rogers [25, Section 14.3]) shows that this is $\Sigma^0_3$.$\Box$

Similarly one can prove:

Corollary 4.14 (Kjos-Hanssen 2005)   The ternary relation $A'\oplus B\le_\mathit{LR}C$ is $\Sigma^0_3$. More generally, for each $k$ the $k+2$-ary relation $A_1'\oplus\cdots\oplus A_k'\oplus B\le_\mathit{LR}C$ is $\Sigma^0_3$.

Remark 4.15   Earlier Nies had proved that $\{A\mid A\le_\mathit{LR}0\}$ is $\Sigma^0_3$. Another interesting result due to Nies and Hirschfeldt (see Remark 10.12 below) is that if $A\le_\mathit{LR}0$ and $B\le_\mathit{LR}0$ then $A\oplus B\le_\mathit{LR}0$. Thus $\{A\mid A\le_\mathit{LR}0\}$ is a $\Sigma^0_3$ Turing ideal. See Nies [21, Theorems 6.2 and 7.9].

Almost everywhere domination

In this section we exposit some recent results of Kjos-Hanssen/Miller/Solomon [14] concerning almost everywhere domination. We begin by reviewing some earlier definitions and results of Dobrinen/Simpson [7] and Kjos-Hanssen [13].

Definition 5.1 (Dobrinen/Simpson 2003)  

1. Let $f,g:\omega\to\omega$ be total functions. We say that $f$ is dominated by $g$ if $f(n)<g(n)$ for all but finitely many $n$.
2. We say that $B$ is almost everywhere dominating if, for measure 1 many $X\in2^\omega$, each $X$-recursive function is dominated by some $B$-recursive function.
3. We say that $B$ is uniformly almost everywhere dominating if there is a fixed $B$-recursive function which dominates all $X$-recursive functions for measure 1 many $X\in2^\omega$.

Theorem 5.2 (Dobrinen/Simpson 2003)   The following statements are pairwise equivalent.

1. $B$ is uniformly almost everywhere dominating.
2. Every $\Pi^0_2$ subset of $2^\omega$ includes a $\Sigma^{0,B}_2$ set of the same measure.
3. Every $\Pi^{0,0'}_1$ subset of $2^\omega$ includes a $\Sigma^{0,B}_2$ set of the same measure.

Proof.See Dobrinen/Simpson [7, Theorem 3.2].$\Box$

Theorem 5.3 (Dobrinen/Simpson 2003)   The following statements are pairwise equivalent.

1. $B$ is almost everywhere dominating.
2. Given a $\Pi^0_2$ set $Q\subseteq2^\omega$, and given $\epsilon>0$, we can find a $\Pi^{0,A}_1$ set $P\subseteq Q$ such that $\mu(P)\ge\mu(Q)-\epsilon$.
3. Given a $\Pi^{0,0'}_1$ set $Q\subseteq2^\omega$, and given $\epsilon>0$, we can find a $\Pi^{0,A}_1$ set $P\subseteq Q$ such that $\mu(P)\ge\mu(Q)-\epsilon$.

Proof.See Dobrinen/Simpson [7, Theorem 3.3].$\Box$

In light of the above results plus Dobrinen/Simpson [7, Conjecture 3.1, Statement 4], the following definition has been made by Kjos-Hanssen [13].

Definition 5.4 (Kjos-Hanssen 2005)   We say that $B$ is positive-measure dominating if every $\Pi^0_2$ subset of $2^\omega$ of positive measure includes a $\Pi^{0,B}_1$ set of positive measure. Equivalently, every $\Pi^{0,0'}_1$ subset of $2^\omega$ of positive measure includes a $\Pi^{0,B}_1$ set of positive measure.

We then have:

Theorem 5.5 (Kjos-Hanssen 2005)   $B$ is positive-measure dominating if and only if $0'\le_\mathit{LR}B$.

Proof.This is immediate from the special case $A=0'$ of Theorem 4.6.$\Box$

Corollary 5.6 (Kjos-Hanssen 2005)   The set

$\mathrm{PMD}=\{B\mid B$ is positive-measure dominating$\}$

is $\Sigma^0_3$.

Proof.This is immediate from Theorem 5.5 and Corollary 4.14.$\Box$

Our main goal in this section will be to prove the following theorem.

Theorem 5.7 (Kjos-Hanssen/Miller/Solomon 2006)  
The following properties of a Turing oracle $B$ are pairwise equivalent.

1. $B$ is uniformly almost everywhere dominating.
2. $B$ is almost everywhere dominating.
3. $B$ is positive-measure dominating.
4. $0'\le_\mathit{LR}B$.

Remark 5.8   Theorems 5.2, 5.3, 5.5, and 5.7 have implications for the reverse mathematics of measure-theoretic regularity. See Dobrinen/Simpson [7], Binns/Kjos-Hanssen/Lerman/Solomon [2], Cholak/Greenberg/Miller [5], Kjos-Hanssen [13], and Kjos-Hanssen/Miller/Solomon [14]. Namely, it now appears likely that all of the measure-theoretic regularity statements considered by Dobrinen/Simpson [7] are in some sense equivalent.

Corollary 5.9 (Kjos-Hanssen/Miller/Solomon 2006)  
The sets

$\mathrm{AED}=\{B\mid B$ is almost everywhere dominating$\}$

and

$\mathrm{UAED}=\{B\mid B$ is uniformly almost everywhere dominating$\}$

are $\Sigma^0_3$. In fact, $\mathrm{AED}=\mathrm{UAED}=\mathrm{PMD}$.

Proof.This is immediate from Corollary 5.6 and Theorem 5.7.$\Box$

Remark 5.10   Corollaries 5.6 and 5.9 are of significance for the study of weak degrees (a.k.a., Muchnik degrees) of mass problems associated with nonempty $\Pi^0_1$ subsets of $2^\omega$. This aspect has been examined in Kjos-Hanssen [13] and in Simpson [28]. See also Simpson [27] for some newer results.

We now turn to the proof of Theorem 5.7. The proof (see Remark 5.14 below) will be based on the following lemma and theorem.

Lemma 5.11 (Kjos-Hanssen/Miller/Solomon 2006)  
Assume $A\le_\mathit{LR}B$. Let $f:\omega\to\omega$ be recursive. For all $A$-r.e. sets $I$ such that $\sum_{i\in I}1/2^{f(i)}<\infty$, there exists a $B$-r.e. set $J\supseteq I$ such that $\sum_{i\in J}1/2^{f(i)}<\infty$.

Proof.We use the following fact from analysis. Given $0<a_i<1$, $i=0,1,\ldots$, we have

$\sum_{i=0}^\infty a_i<\infty\quad{}$ if and only if $\quad\prod_{i=0}^\infty(1-a_i)>0$.

See for instance Olmstead [23, Theorem III, page 525].

To prove our lemma, let $A,B,f,I$ be as in the hypotheses of the lemma. We may safely assume that $f(i)\ne0$ for all $i$. Let

$D_i=\{X\in2^\omega\mid\exists n (X(n)=1$ and $g(i)\le n<g(i+1))\}$

where $g(i)=\sum_{k=0}^{i-1}f(k)$. Note that the $D_i$'s are mutually independent and clopen and $\mu(D_i)=1-1/2^{f(i)}$. Consider the $\Pi^{0,A}_1$ set $P=\bigcap_{i\in I}D_i$. By hypothesis $\sum_{i\in I}1/2^{f(i)}<\infty$, hence

$\mu(P)=\prod_{i\in I}\mu(D_i)=\prod_{i\in I}(1-1/2^{f(i)})>0$.

Let $Q\subseteq P$ be $\Pi^{0,B}_1$ such that $\mu(Q)>0$. Let $J=\{i\mid D_i\supseteq Q\}$. Clearly $J\supseteq I$ and $J$ is $B$-r.e. Moreover $\bigcap_{i\in J}D_i\supseteq Q$, hence

$\prod_{i\in J}(1-1/2^{f(i)})=\prod_{i\in J}\mu(D_i)=\mu(\bigcap_{i\in J}D_i)\ge\mu(Q)>0$,

hence $\sum_{i\in J}1/2^{f(i)}<\infty$, Q.E.D.$\Box$

Remark 5.12   Under the same hypothesis, $A\le_\mathit{LR}B$, we can obtain the following stronger conclusion. Given a recursive sequence of recursive real numbers $r_i\ge0$, $i=0,1,\ldots$, and given an $A$-r.e. set $I$ such that $\sum_{i\in I}r_i<\infty$, we can effectively find a $B$-r.e. set $J\supseteq I$ such that $\sum_{i\in J}r_i<\infty$.

Theorem 5.13 (Kjos-Hanssen/Miller/Solomon 2006)  
Assume $A\le_\mathit{LR}B$ and $A\le_TB'$. Then every $\Pi^{0,A}_1$ subset of $2^\omega$ includes a $\Sigma^{0,B}_2$ set of the same measure.

Proof.Assume $A\le_\mathit{LR}B$ and $A\le_TB'$. We must show that every $\Pi^{0,A}_1$ set includes a $\Sigma^{0,B}_2$ set of the same measure. Equivalently, we shall show that every $\Sigma^{0,A}_1$ set is included a $\Pi^{0,B}_2$ set of the same measure.

Let $U\subseteq2^\omega$ be $\Sigma^{0,A}_1$. Write

$U=\{X\mid\exists n (X\upharpoonright n\in S^A)\}$

where $S^A\subseteq2^{<\omega}$ is $A$-r.e. and prefix-free. Let

$I=\{(\sigma,\tau)\mid\tau\in S^A$ with use $\sigma\subset A\}$.

Thus $U=\{X\mid\exists n \exists\sigma ((\sigma,X\upharpoonright n)\in I)\}$. Clearly $I$ is $A$-r.e. and

$\sum_{(\sigma,\tau)\in I}1/2^{\vert\tau\vert}=\sum_{\tau\in S^A}1/2^{\vert\tau\vert}\le1$.

By Lemma 5.11 let $J\supseteq I$ be