Almost everywhere domination and superhighness

Stephen G. Simpson

Pennsylvania State University

First draft: July 5, 2006
This draft: October 29, 2009

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,B}_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,B}_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 $B$-r.e. such that $\sum_{(\sigma,\tau)\in J}1/2^{\vert\tau\vert}<\infty$.

We may safely assume that $A\in2^\omega$. Since $A\le_TB'$, let $A=\lim_sA_s$ be a $B$-recursive approximation of $A$. Let

$V_s=\{X\in2^\omega\mid\exists n \exists\sigma ((\sigma,X\upharpoonright n)\in J_s)\}$

where

$J_s=\{(\sigma,\tau)\in J\mid\exists t\ge s (\tau\in S^{A_t}$ with use $\sigma\subset A_t)\}$.

Clearly $\bigcap_sV_s$ is $\Pi^{0,B}_2$. Moreover $I\subseteq\bigcap_sJ_s$, hence $U\subseteq\bigcap_sV_s$.

Claim 1: $I=\bigcap_sJ_s$.

To see this, suppose $(\sigma,\tau)\notin I$. Then either (1) $\sigma\not\subset A$, or (2) $\sigma\subset A$ but $\tau$ is not in $S^A$ with use $\sigma$. In case (1) we have $\sigma\not\subset A_t$ for all sufficiently large $t$, hence $(\sigma,\tau)\notin\bigcap_sJ_s$. In case (2) we have $\sigma\subset A_t$ for all sufficiently large $t$, hence $\tau$ is not in $S^{A_t}$ with use $\sigma$, hence again $(\sigma,\tau)\notin\bigcap_sJ_s$, proving our claim.

Claim 2: $\mu(U)=\mu(\bigcap_sV_s)$.

To see this, fix $\epsilon>0$. Let $F$ be a finite subset of $J$ such that $\sum_{(\sigma,\tau)\in J\setminus F}1/2^{\vert\tau\vert}<\epsilon$. Let $s$ be so large that, for all $(\sigma,\tau)\in F$, if $(\sigma,\tau)\notin I$ then $(\sigma,\tau)\notin J_s$. Then

$\mu(V_s\setminus U)\le\sum_{(\sigma,\tau)\in J_s\setminus I}1/2^{\vert\tau\vert}\le\sum_{(\sigma,\tau)\in J\setminus F}1/2^{\vert\tau\vert}<\epsilon$

proving our claim.

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

Remark 5.14   Theorem 5.7 is just the special case $A=0'$ of Theorem 5.13 in light of Theorems 5.2, 5.3, 5.5.

Some examples

We have seen in Theorem 5.3 that every Turing oracle $B\ge_T0'$ is almost everywhere dominating. In this section we construct a $B<_T0'$ which is almost everywhere dominating. Such examples were first given by Cholak/Greenberg/Miller [5]. We also construct a $C$ such that $0'\le_\mathit{LR}C$ yet $0'$ is not low-for-random relative to $C$.

To obtain our examples, we combine a construction of Kucera/Terwijn [16] with the Pseudojump Inversion Theorem of Jockusch/Shore [12] and the Join Theorem of Posner/Robinson [24].

Theorem 6.1 (Kucera/Terwijn 1997)   We can find a nonrecursive r.e. set $A\subseteq\omega$ such that $A\le_\mathit{LR}0$, i.e., $A$ is low-for-random.

Proof.By Corollary 3.3 we know that $\{X\in2^\omega\mid X$ is random$\}$ is $\Sigma^0_2$ and of measure 1. Therefore, we can find a $\Pi^0_1$ set $P\subseteq2^\omega$ such that $\mu(P)>1/2$ and $\forall X (X\in P\Rightarrow X$ is random$)$. By uniformly relativizing the construction of $P$ to an arbitrary Turing oracle $C$, we obtain² a $\Pi^{0,C}_1$ set $P^C\subseteq2^\omega$ such that $\mu(P^C)>1/2$ and $\forall X (X\in P^C\Rightarrow X$ is $C$-random$)$. For $C\in2^\omega$ let $U^C=\overline{P^C}=2^\omega\setminus P^C$. Note that $U^C$ is uniformly $\Sigma^{0,C}_1$ and $\mu(U^C)<1/2$.

To prove the theorem, we shall build a nonrecursive r.e. set $A$ and a $\Sigma^0_1$ set $V\supseteq U^A$ such that $\mu(V)<1$. Letting $Q=2^\omega\setminus V$, it will follow that $Q$ is a $\Pi^0_1$ subset of $P^A$ of positive measure. Hence by Theorem 4.6 $A\le_\mathit{LR}0$, Q.E.D.

It remains to build $A$ and $V$ as specified.

We first establish some notation. Let $W_e$, $e=0,1,\ldots$ be a recursive enumeration of the r.e. subsets of $\omega$. Let $W_{e,s}$ be the set of $n\in\omega$ which get into $W_e$ by means of a computation in $\le s$ steps. Thus $W_e=\bigcup_sW_{e,s}$. Let $U^C_s$ be the set of $X\in2^\omega$ which get into $U^C$ by means of a computation in $\le s$ steps using only oracle information from $C\upharpoonright s$. Thus $U^C_s$, $s=0,1,\ldots$ is a uniformly $C$-recursive sequence of clopen sets in $2^\omega$, and $U^C=\bigcup_sU^C_s$.

Our r.e. set $A\subseteq\omega$ will be constructed as $A=\bigcup_sA_s$ where $A_0\subseteq A_1\subseteq\cdots\subseteq A_s\subseteq\cdots$ is a recursive sequence of finite sets. Let $V=\bigcup_sU^{A_s}_s$. Clearly $U^A\subseteq V\subseteq2^\omega$ and $V$ is $\Sigma^0_1$. Our construction of $A$ will insure that $\mu(V\setminus U^A)\le1/2$. Since $\mu(U^A)<1/2$, we shall have $\mu(V)<1$ as desired.

Note that $U^{A_s}_s$, $s=0,1,\ldots$ is a recursive sequence of clopen sets in $2^\omega$. Let $V_t=U^{A_t}_t\setminus\bigcup_{s<t}U^{A_s}_s$. Then $V_t$, $t=0,1,\ldots$ is a recursive, pairwise disjoint sequence of clopen sets in $2^\omega$, and $V=\bigcup_sU^{A_s}_s=\bigcup_tV_t$.

Our construction of $A$ is as follows. At stage 0 let $A_0=\emptyset$. At stage $s+1$, for each $e<s$ such that $A_s\cap W_{e,s}=\emptyset$, look for $n\in W_{e,s}$ such that $n\ge2e$ and $\sum_{n<t\le s}\mu(V_t)\le1/2^{e+2}$ and put the least such $n$ into $A_{s+1}$.

Finally let $A=\bigcup_sA_s$. Clearly $A$ is r.e. By construction, for each $e$ at most one $n$ is put into $A$ for the sake of $W_e$. Therefore, our condition $n\ge2e$ insures that $\overline{A}=\omega\setminus A$ is infinite.

Lemma 6.2   For each $e$, if $W_e$ is infinite then $A\cap W_e\ne\emptyset$.

Proof.Since the $V_t$'s are pairwise disjoint, we have $\sum_t\mu(V_t)=\mu(\bigcup_tV_t)=\mu(V)\le1$. Assume that $W_e$ is infinite. Let $n\in W_e$ be so large that $n\ge2e$ and $\sum_{n<t}\mu(V_t)\le1/2^{e+2}$. Let $s$ be so large that $n\in W_{e,s}$. Then by construction $A_{s+1}\cap W_{e,s}\ne\emptyset$.$\Box$

Since $\overline{A}$ is infinite, it follows that $A$ is nonrecursive. (Actually, $A$ is a simple r.e. set. Compare Post's original construction of a simple r.e. set, as exposited in Rogers [25, Section 8.1].)

Lemma 6.3   We have $\mu(V\setminus U^A)\le1/2$.

Proof.Given $X\in V\setminus U^A$, let $t$ be such that $X\in V_t$. Then $X\in U^{A_t}_t\setminus U^A$, hence $A\upharpoonright t\ne A_t\upharpoonright t$. In other words, at some stage $s+1>t$, some $n<t$ is put into $A_{s+1}$ for the sake of $W_e$ for some $e<s$. For this particular $e$, the set of such $X$'s is $\subseteq\bigcup_{n<t\le s}V_t$, hence of measure $\le\sum_{n<t\le s}\mu(V_t)\le1/2^{e+2}$. Hence the set of all such $X$'s is of measure $\le\sum_e1/2^{e+2}=1/2$.$\Box$

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

We now present the Pseudojump Inversion Theorem.

Definition 6.4   For an arbitrary Turing oracle $C$, let $W_e^C$, $e=0,1,\ldots$ be a standard, uniform enumeration of all $C$-r.e. subsets of $\omega$. For each fixed $e$, the operator $J_e:2^\omega\to2^\omega$ given by $J_e(C)=C\oplus W_e^C$ is called a pseudojump operator or an $\mathit{REA}$-operator. (The acronym REA stands for ``r.e. and above''.)

Remark 6.5   Note that the Turing jump operator $J(C)=C\oplus C'$ is an example of a pseudojump operator. The Pseudojump Inversion Theorem 6.6, due to Jockusch/Shore [12, Theorem 2.1], is a generalization of the Jump Inversion Theorem due to Friedberg (see Rogers [25, Chapter 13, Corollary IX(a)]), replacing the Turing jump operator by an arbitrary pseudojump operator.

Theorem 6.6 (Pseudojump Inversion Theorem)   For any pseudojump operator $J_e$ and any $A\ge_T0'$, we can find a $B$ such that $J_e(B)\equiv_TB\oplus0'\equiv_TA$.

Proof.For $C\in2^\omega$ and $e\in\omega$, we write $W_{e,s}^C$ to denote the set of $n\in\omega$ which get into $W_e^C$ by means of a computation in $\le s$ steps using only oracle information from $C\upharpoonright s$. Note that $W_e^C=\bigcup_sW_{e,s}^C$. We also write $W_{e,s}^C=W_e^\tau$ where $\tau=C\upharpoonright s$.

Given $A\in2^\omega$, our construction of $B$ is as follows. We define a sequence of strings $\tau_0\subseteq\tau_1\subseteq\cdots\subseteq\tau_n\subseteq\cdots$, $n=0,1,\ldots$. Let $\tau_0=\langle\rangle$. For each $n$, given $\tau_{2n}$, if there exists $\tau\supseteq\tau_{2n}$ such that $n\in W_e^\tau$, let $\tau_{2n+1}$ be the least such $\tau$. Otherwise let $\tau_{2n+1}=\tau_{2n}$. For each $n$ let $\tau_{2n+2}=\tau_{2n+1}{{}^\smallfrown}\langle A(n)\rangle$. Finally let $B=\bigcup_n\tau_n$. By construction, the sequence $\langle\tau_n\mid n\in\omega\rangle$ is easily seen to be recursive in 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$

We now use the Pseudojump Inversion Theorem to obtain an example of a $B<_T0'$ such that $B$ is almost everywhere dominating.

Theorem 6.7   There exists $B<_T0'$ such that $B$ is almost everywhere dominating.

Proof.By uniformly relativizing Theorem 6.1 to an arbitrary Turing oracle $C$, we obtain a pseudojump operator $J_e$ such that for all $C$, $J_e(C)$ is $>_TC$ and $\le_\mathit{LR}C$. Applying the Pseudojump Inversion Theorem 6.6 to this operator, we see that for all $A\ge_T0'$ there exists $B<_TA$ such that $A\equiv_TB\oplus0'$ and $A\le_\mathit{LR}B$. (Then by Theorem 8.9 we necessarily have $A'\le_{tt}B'$.) In particular, letting $A=0'$, we obtain $B<_T0'$ such that $0'\le_\mathit{LR}B$. (Then by Theorem 8.9 we necessarily have $0''\le_{tt}B'$.) By Theorem 5.7 $B$ is almost everywhere dominating.$\Box$

Remark 6.8   In the example of Theorem 6.7, we have $0'\oplus B\equiv_T0'\le_\mathit{LR}B$, hence $0'$ is low-for-random relative to $B$. We now use the Join Theorem of Posner/Robinson [24] to obtain a different kind of example, namely a $C$ such that $0'\le_\mathit{LR}C$, hence $C$ is almost everywhere dominating, yet $0'$ is not low-for-random relative to $C$.

Theorem 6.9 (Join Theorem)   Given $A$ such that $0<_TA\le_T0'$, we can find a $C$ such that $A\oplus C\equiv_TC'\equiv_T0'$.

Proof.See Posner/Robinson [24].$\Box$

Theorem 6.10   There exists $C$ such that $C$ is almost everywhere dominating yet $0'$ is not low-for-random relative to $C$.

Proof.Let $B$ be as in Theorem 6.7, i.e., $B<_T0'$ and $0'\le_\mathit{LR}B$. Relativizing the Join Theorem 6.9 to $B$ and letting $A=0'$, we obtain $C$ such that $B\le_TC$ and $0'\oplus C\equiv_TC'\equiv_T B'$. We then have $0'\le_\mathit{LR}B\le_TC$, hence $0'\le_\mathit{LR}C$. (It follows that $C'\le_T0''$ and $0''\le_{tt}C'$.) By Theorem 5.7 $C$ is almost everywhere dominating. We claim that $0'\oplus C\not\le_\mathit{LR}C$, i.e., $0'$ is not low-for-random relative to $C$. To see this, note that $0'\oplus C\le_\mathit{LR}C$ would imply $(0'\oplus C)'\le_TC'$ (see Theorem 8.8) which would imply $C''\le_TC'$, a contradiction.$\Box$

Remarks on Theorem 5.13

This section consists of some technical remarks showing that Theorem 5.13 is, in various senses, best possible.

Remark 7.1   The converse of Theorem 5.13 holds. In other words, if every $\Pi^{0,A}_1$ set includes a $\Sigma^{0,B}_2$ set of the same measure, then $A\le_\mathit{LR}B$ and $A\le_TB'$.

To see this, assume the conclusion of Theorem 5.13, i.e., every $\Pi^{0,A}_1$ set includes a $\Sigma^{0,B}_2$ set of the same measure. Then $A\le_\mathit{LR}B$ in view of Theorem 4.6. It remains to prove $A\le_TB'$. Consider the $\Sigma^{0,A}_1$ set $U=\bigcup_{n\in A}O_n$ where

$$O_n=\{X\in2^\omega\mid\langle\underbrace{0,\ldots,0}_n,1\rangle \subset X\} .$$

Note that $\mu(U)=\sum_{n\in A}1/2^{n+1}$. Our assumption implies that $U\subseteq Q$ for some $\Pi^{0,B}_2$ set $Q$ such that $\mu(U)=\mu(Q)$. Write $Q=\bigcap_kV_k$ where $V_k$ is uniformly $\Sigma^{0,B}_1$. Then $n\in A$ if and only if $O_n\subseteq Q$, if and only if $\forall k (O_n\subseteq V_k)$, if and only if $\forall k \exists s (O_n\subseteq V_{k,s})$. Thus $A$ is $\Pi^{0,B}_2$. Similarly we can show that $\overline{A}=\omega\setminus A$ is $\Pi^{0,B}_2$. Thus $A$ is $\Delta^{0,B}_2$, i.e., $A\le_TB'$, Q.E.D.

Remark 7.2   The hypothesis $A\le_TB'$ cannot be dropped from Theorem 5.13. To see this, recall from Remark 4.4 that there exists a $B$ such that $A\le_\mathit{LR}B$ for uncountably many $A$. In particular, there are uncountably many $A$ such that $A\le_\mathit{LR}B$ yet $A\not\le_TB'$. For such $A$ and $B$, the conclusion of Theorem 5.13 cannot hold, in view of Remark 7.1.

The following special case of Theorem 5.13 seems interesting in view of Remarks 4.3 and 4.4.

Theorem 7.3   Assume $A\oplus B\le_\mathit{LR}B$, i.e., $A$ is low-for-random relative to $B$. Then every $\Pi^{0,A\oplus B}_1$ subset of $2^\omega$ includes a $\Sigma^{0,B}_2$ set of the same measure.

Proof.We first prove a lemma which is well known. See also Remark 10.12 below.

Lemma 7.4   If $A\oplus B\le_\mathit{LR}B$ then $A\oplus B\le_TB'$.

Proof.Assume $A\oplus B\le_\mathit{LR}B$. By Theorem 10.10 we have $A\oplus B\le_\mathit{LK}B$, i.e., $K^B(\tau)\le K^{A\oplus B}(\tau)+O(1)$. From this it follows easily that $K^B(A\upharpoonright n)\le K^B(n)+O(1)$. In other words, using the terminology of Nies [21], $A$ is $K$-trivial relative to $B$. By Chaitin's Theorem (see Downey/Hirschfeldt/Nies/Stephan [9, Corollary 6.7(ii)]) relative to $B$, it follows that $A$ is $\Delta^{0,B}_2$, i.e., $A\le_TB'$, hence $A\oplus B\le_TB'$. $\Box$

Theorem 7.3 is now immediate from Theorem 5.13 plus Lemma 7.4.$\Box$

Remark 7.5   Comparison of Theorems 5.13 and 7.3 suggests the following question. If $A\le_\mathit{LR}B$ and $A\le_TB'$, does it follow that $A\oplus B\le_\mathit{LR}B$? The answer to this question is negative. Indeed, letting $C$ be as in Theorem 6.10, we have $0'\le_\mathit{LR}C$ and $0''\le_{tt}C'$ yet $0'\oplus C\not\le_\mathit{LR}C$.

Question 7.6   If $A\le_\mathit{LR}B$ and $(A\oplus B)'\le_{tt}B'$, does it follow that $A\oplus B\le_\mathit{LR}B$? (Compare Theorem 8.9 below.)

Superhighness

In this section we present some new results concerning the relationship between $\mathit{LR}$-reducibility and truth-table reducibility.

Remark 8.1   Recall from Rogers [25, Chapters 8 and 9] the notion of truth-table reducibility, denoted $\le_{tt}$. A result of Nerode (see Rogers [25, Chapter 9, Theorem XIX]) says that for all $A,B\in2^\omega$, $A\le_{tt}B$ if and only if $A=\Phi(B)$ for some total recursive functional $\Phi:2^\omega\to2^\omega$. Thus truth-table reducibility is a special case of Turing reducibility.

Definition 8.2   Let $B$ be a Turing oracle. We say that $B$ is high if $0''\le_TB'$, i.e., $0''$ is Turing reducible to $B'$. We say that superhigh if $0''\le_{tt}B'$, i.e., $0''$ is truth-table reducible to $B'$.

Among other things, we are going to prove that if $B$ is almost everywhere dominating then $B$ is superhigh. We begin with the following definition and lemma.

Definition 8.3   Let $A$ and $B$ be Turing oracles.

1. We say that $A$ is jump-traceable by $B$ if for each partial $A$-recursive function $\psi^A(n)$ there exist recursive functions $f(n)$ and $g(n)$ such that $\forall n (\psi^A(n){\downarrow}\Rightarrow \psi^A(n)\in W^B_{f(n)})$ and $\forall n (\vert W^B_{f(n)}\vert\le g(n))$.
2. We say that $A$ is weakly jump-traceable by $B$ if for each partial $A$-recursive function $\psi^A(n)$ there exists a recursive function $f(n)$ such that $\forall n (\psi^A(n)\downarrow \Rightarrow \psi^A(n)\in W^B_{f(n)})$ and $\forall n (W^B_{f(n)}$ is finite$)$.

Lemma 8.4   If $A\le_\mathit{LR}B$ then $A$ is jump-traceable by $B$.

Proof.Consider the $A$-r.e. set $I=\{(n,m)\mid\psi^A(n)\simeq m\}$. We have

$\sum_{(n,m)\in I}1/2^n=\sum_{n\in\mathrm{dom}(\psi^A)}1/2^n\le2<\infty$.

By Lemma 5.11 let $J\supseteq I$ be $B$-r.e. such that $\sum_{(n,m)\in J}1/2^n<\infty$, say

$\sum_{(n,m)\in J}1/2^n\le2^c$.

Let $f$ be a recursive function such that for all $n$,

$W^B_{f(n)}=\{m\mid(n,m)\in J\}$.

Setting $g(n)=2^{n+c}$ we obtain the desired conclusions. Note that the bounding function $g(n)$ is not only recursive but primitive recursive.$\Box$

Lemma 8.5   If $A$ is weakly jump-traceable by $B$, then $A'\le_TA\oplus B'$.

Proof.Consider the partial $A$-recursive function $\psi^A(e)\simeq$ least $s$ such that $\varphi^{(1),A}_{e,s}(e)\downarrow$. Note that $A'=\mathrm{dom}(\psi^A)$. By weak jump-traceability, let $f(e)$ be recursive such that $\forall e (\psi^A(e)\downarrow \Rightarrow \psi^A(e)\in W^B_{f(e)})$ and $\forall e (W^B_{f(e)}$ is finite$)$. Consider the total function $h(e)=\max(W^B_{f(e)}\cup\{0\})$. Note that $h(e)$ is recursive relative to $B'$, and $e\in A'$ if and only if $\varphi^{(1),A}_{e,h(e)}(e)\downarrow$. Thus $A'\le_TA\oplus B'$.$\Box$

Lemma 8.6   If $A$ is jump-traceable by $B$ and $B$-r.e., then $A'\le_{tt}B'$.

Proof.Since $A$ is $B$-r.e., let $A=\bigcup_sA_s$ where $A_s$, $s=0,1,\ldots$ is a $B$-recursive sequence of finite sets with $A_0\subseteq A_1\subseteq\cdots\subseteq A_s\subseteq A_{s+1}\subseteq\cdots$. We identify the sets $A$ and $A_s$ with their characteristic functions. Consider the partial $A$-recursive function $\theta^A(e)\simeq$ the least $\sigma\subset A$ such that $\varphi_{e,\vert\sigma\vert}^{(1),\sigma}(e)\downarrow$. Clearly $A'=\mathrm{dom}(\theta^A)=\{e\mid\theta^A(e)\downarrow\}$. By jump-traceability let $f(e)$ and $g(e)$ be recursive functions such that $\forall e (\theta^A(e)\downarrow \Rightarrow \theta^A(e)\in W^B_{f(e)})$ and $\forall e (\vert W^B_{f(e)}\vert\le g(e))$. We may safely assume that each $\sigma\in W^B_{f(e)}$ satisfies $\varphi_{e,\vert\sigma\vert}^{(1),\sigma}(e)\downarrow$. For all $e$ and all $i<g(e)$ let $\sigma_{e,i}\simeq$ the $i$th member of $W^B_{f(e)}$ in order of $B$-recursive enumeration. We may now compute $A'$ from $B'$ as follows. Given $e$, for each $i<g(e)$ ask the $B'$ oracle whether $\exists s (\sigma_{e,i}\downarrow \subset A_s)$ and whether $\exists s \exists t (s<t$ and $\sigma_{e,i}\downarrow \subset A_s$ and $\sigma_{e,i}\not\subset A_t)$. Upon receiving the answers to these $2g(e)$-many questions, we know the finite set $F_e=\{i<g(e)\mid\sigma_{e,i}\downarrow \subset A\}$. Then $e\in A'$ if and only if $F_e$ is nonempty. Thus $A'\le_{tt}B'$, Q.E.D.$\Box$

Remark 8.7   In the proof of Lemma 8.6 we have $\varphi_e^{(1),A}(e)\simeq\varphi_{e,\vert\sigma_{e,i}\vert}^{(1),\sigma_{e,i}}(e)$ for any $i\in F_e$. Thus we see that, under the hypotheses of Lemma 8.6, the function

$$h^A(e)=\left\{ \begin{array}{ll} \varphi_e^{(1),A}(e)+1 &... ...downarrow, [5pt] 0 & \hbox{otherwise} \end{array} \right.$$

is $B'$-recursive with recursively bounded use of $B'$ and unbounded use of $B$. This conclusion is in general strictly stronger than either of the conditions $A'\le_{tt}B'$ and $A$ jump-traceable by $B$. However, it is equivalent to their conjunction if $A\ge_TB$, and it is equivalent to each of them individually if $A\ge_TB$ and $A$ is $B$-r.e.

Theorem 8.8   If $A\le_\mathit{LR}B$ then $A'\le_TA\oplus B'$.

Proof.This is immediate from Lemmas 8.4 and 8.5.$\Box$

Theorem 8.9   If $A\le_\mathit{LR}B$ and $A$ is $B$-r.e., then $A'\le_{tt}B'$.

Proof.This is immediate from Lemmas 8.4 and 8.6.$\Box$

Theorem 8.10   If $0'\le_\mathit{LR}B$ then $0''\le_{tt}B'$.

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

Theorem 8.11   If $B$ is almost everywhere dominating, then $B$ is superhigh.

Proof.This is a restatement of Theorem 8.10 in light of Theorem 5.7.$\Box$

Remark 8.12   Our Theorems 8.8, 8.9, 8.10, 8.11 are closely related to some results of Nies [21,22]. Nies proved that if $A\le_\mathit{LR}0$ then $A$ is superlow, i.e., $A'\le_{tt}0'$ (see Nies [21, Corollary 7.6]). Relativizing the arguments of Nies to a Turing oracle $B$, one can show that if $A\oplus B\le_\mathit{LR}B$ then $(A\oplus B)'\le_{tt}B'$. (See also Remark 10.12 below.) In particular, if $0'\oplus B\le_\mathit{LR}B$ then $0''\le_{tt}B'$. Our Theorem 8.10 improves this by weakening the hypothesis $0'\oplus B\le_\mathit{LR}B$ to $0'\le_\mathit{LR}B$. In addition, Nies [21, paragraph preceding Proposition 8.3] announced that if $A$ and $B$ are r.e. and $A\le_\mathit{LR}B$ then $A'\le_{tt}B'$. Our Theorem 8.9 improves this by eliminating the hypothesis that $B$ is r.e.

Question 8.13   If $A\le_\mathit{LR}B$ and $A\le_T0'$, does it follow that $A'\le_{tt}B'$?

Counterexamples via duality

In the previous section we have seen that if $B$ is almost everywhere dominating then $B$ is superhigh, which implies that $B$ is high. In this section we present counterexamples showing that neither of these implications can be reversed.

In order to obtain our counterexamples, we use a duality technique which has been used previously by Jockusch/Shore [12], Mohrherr [20], Nies [21], and Kjos-Hanssen [13]. The technique is based on the following theorem due to Jockusch/Shore [12] which we call the Duality Theorem.

Theorem 9.1 (Duality Theorem)   Given a pseudojump operator $J_e$, we can find an r.e. set $B$ such that $J_e(B)\equiv_T0'$.

Proof.See Jockusch/Shore [12, Theorem 3.1].$\Box$

We shall see that the Duality Theorem provides a powerful method of passing from ``lowness properties'' to ``highness properties'' as in Table 1. The meaning of Table 1 is that, if we have a uniformly relativizable construction of an r.e. set $A$ with some but not all of the properties on the left side of the table, then we can apply the Duality Theorem to obtain an r.e. set $B$ with corresponding properties on the right side of the table.

Table 1: Duality

$\le_T0$		$\ge_T0'$
low		high
superlow		superhigh
$\le_\mathit{LR}0$		$\ge_\mathit{LR}0'$
low-for-random		a. e. dominating

As our first application of the Duality Theorem, we note the following improvement of the counterexample in Theorem 6.7. A similar result was first obtained by Cholak/Greenberg/Miller [5] using a different method.

Theorem 9.2 (Cholak/Greenberg/Miller 2004)   There exists an r.e. set $B$ which is ${}<_T0'$ and almost everywhere dominating.

Proof.In Theorem 6.1 we have constructed an r.e. set $A$ which is $>_T0$ and $\le_\mathit{LR}0$. By uniformly relativizing this construction to an arbitrary Turing oracle $C$, we obtain a pseudojump operator $J_e$ such that for all $C$, $J_e(C)$ is $>_TC$ and $\le_\mathit{LR}C$. Applying the Duality Theorem 9.1 to this operator, we obtain an r.e. set $B$ which is $<_T0'$ and $\ge_\mathit{LR}0'$. It follows by Theorems 5.7 and 8.11 that $B$ is almost everywhere dominating and therefore superhigh. Examples of this kind were first obtained by Cholak/Greenberg/Miller [5, Section 2]. See also Binns/Kjos-Hanssen/Lerman/Solomon [2].$\Box$

We now apply the Duality Theorem to obtain additional counterexamples.

Lemma 9.3   There exists an r.e. set which is superlow and not low-for-random.

Proof.We omit the proof, which is fairly straightforward.$\Box$

Theorem 9.4   There exists an r.e. set $B$ which is superhigh and not almost everywhere dominating.

Proof.By uniformly relativizing the proof of Lemma 9.3, we obtain a pseudojump operator $J_e$ such that for all $C$, $J_e(C)$ is superlow relative to $C$ and not low-for-random relative to $C$. In other words, $J_e(C)'\le_{tt}C'$ and $J_e(C)\not\le_\mathit{LR}C$. Applying the Duality Theorem 9.1, we obtain an r.e. set $B$ such that $0''\le_{tt}B'$ and $0'\not\le_\mathit{LR}B$. It follows by Theorem 5.7 that $B$ is superhigh and not almost everywhere dominating.$\Box$

The next lemma is due to Bickford/Mills and Mohrherr [20].

Lemma 9.5   There exists an r.e. set $A$ which is low and not superlow.

Proof.See Mohrherr [20, Theorem 3] and Bickford/Mills (reference in Mohrherr [20]).$\Box$

The following counterexample is due to Mohrherr [20].

Theorem 9.6   There exists an r.e. set $B$ which is high and not superhigh.

Proof.We argue as in Mohrherr [20, Theorem 5]. By uniformly relativizing the proof of Lemma 9.5, we obtain a pseudojump operator $J_e$ such that for all $C$, $J_e(C)$ is low and not superlow relative to $C$. In other words, $J_e(C)'$ is $\le_TC'$ and $\not\le_{tt}C'$. Applying the Duality Theorem 9.1, we obtain an r.e. set $B$ such that $0''$ is $\le_TB'$ and $\not\le_{tt}B'$. In other words, $B$ is high and not superhigh.$\Box$

Prefix-free Kolmogorov complexity

In our exposition of Martin-Löf randomness and $\mathit{LR}$-reducibility in Sections 3 through 8 above, we have followed the effective measure-theoretic and descriptive set-theoretic approach due to Kucera [15]. The purpose of this section is to explain an alternative approach in terms of relativized prefix-free Kolmogorov complexity. This approach is the one which has been followed by Downey/Hirschfeldt/Nies/Stephan [9] and Nies [21].

Lemma 10.1   Given a recursive sequence of natural numbers $m_i$, $i=0,1,\ldots$ such that $\sum_{i=0}^\infty1/2^{m_i}\le1$, we can effectively find a recursive, one-to-one, prefix-free sequence of strings $\sigma_i$, $i=0,1,\ldots$ such that $\vert\sigma_i\vert=m_i$ for all $i$.

Proof.Assume inductively that we have chosen $\sigma_i$, $0\le i<k$. Assume also that we have chosen another finite set of strings, $D_k$. Define a partition to be a finite, maximal, prefix-free set of strings. We start with $D_0=\{\langle\rangle\}$ and assume inductively that $D_k$ has the following properties:

(a)

$D_k\cap\{\sigma_i\mid0\le i<k\}=\emptyset$.

(b)

$D_k\cup\{\sigma_i\mid0\le i<k\}$ is a partition.

(c)

The strings in $D_k$ are all of different lengths. I.e., for all $\rho,\sigma\in D_k$, if $\rho\ne\sigma$ then $\vert\rho\vert\ne\vert\sigma\vert$.

In fact we shall have a stronger property: $\forall\rho,\sigma\in D_k (\rho<_\mathrm{lex}\sigma\Rightarrow \vert\rho\vert>\vert\sigma\vert)$, where $<_\mathrm{lex}$ denotes the lexicographical order.

We claim that $m_k\ge\min\{\vert\rho\vert\mid\rho\in D_k\}$.

Otherwise $m_k<\min\{\vert\rho\vert\mid\rho\in D_k\}$, hence by (c) we have

$$\frac1{2^{m_k}}>\sum_{\rho\in D_k}\frac1{2^{\vert\rho\vert}} ,$$

hence by (b) we have

$$\sum_{i=0}^k\frac1{2^{m_i}} =\frac1{2^{m_k}}+\sum_{i=0}^{k... ...ert}} +\sum_{i=0}^{k-1}\frac1{2^{\vert\sigma_i\vert}} =1 ,$$

a contradiction.

By the above claim, let $\rho_k\in D_k$ be such that $\vert\rho_k\vert\le m_k$ and $\vert\rho_k\vert$ is as large as possible. Let

$$\sigma_k=\rho_k{{}^\smallfrown}\langle\underbrace{0,\ldots,0}_{m_k-\vert\rho_k\vert}\rangle .$$

Then $\vert\sigma_k\vert=m_k$ and $\sigma_k\not\subseteq\sigma_i$, $\sigma_i\not\subseteq\sigma_k$ for $0\le i<k$. Let

$$D_{k+1}=D_k\setminus\{\rho_k\}\cup \{\rho_k{{}^\smallfrown... ...e{0,\ldots,0}_j,1\rangle\mid0\le j<m_k-\vert\rho_k\vert\} .$$

It is easy to verify that (a), (b), (c) hold with $k+1$ in place of $k$.$\Box$

Definition 10.2   We define a machine to be a partial recursive function from $2^{<\omega}$ into $2^{<\omega}$. A machine $M$ is said to be prefix-free if its domain

$$\mathrm{dom}(M)=\{\sigma\in2^{<\omega}\mid M(\sigma)\downarrow\}$$

is prefix-free.

If $M$ is a prefix-free machine, then clearly $\sum_{M(\sigma)\downarrow}1/2^{\vert\sigma\vert}\le1$, and this is known as the Kraft Inequality. Conversely we have the following theorem attributed by Nies [21, Theorem 3.2] and Downey/Hirschfeldt/Nies/Stephan [9, Theorem 2.1] to Chaitin [3].

Theorem 10.3 (Kraft/Chaitin Theorem)   Let $L$ be an r.e. subset of $\omega\times2^{<\omega}$ such that $\sum_{(m,\tau)\in L}1/2^m\le1$. Then we can effectively find a prefix-free machine $M$ such that for all $(m,\tau)\in L$ there exists $\sigma$ such that $\vert\sigma\vert=m$ and $M(\sigma)\simeq\tau$.

Proof.Let $(m_i,\tau_i)$, $i=0,1,\ldots$ be a one-to-one recursive enumeration of $L$. By Lemma 10.1 let $\sigma_i$, $i=0,1,\ldots$ be a recursive, prefix-free sequence of strings such that $\vert\sigma_i\vert=m_i$ for all $i$. Define $M(\sigma_i)=\tau_i$ for all $i$.$\Box$

Remark 10.4   In the Kraft/Chaitin Theorem 10.3, the pairs $(m,\tau)\in L$ are sometimes called axioms for the prefix-free machine $M$. The idea of the theorem is that we can construct a prefix-free machine given only an abstract description of the machine in terms of axioms.

Definition 10.5 (prefix-free Kolmogorov complexity)   A prefix-free machine $U$ is said to be universal if for all prefix-free machines $M$ there exists a string $\rho$ such that for all strings $\sigma$, $M(\sigma)\simeq U(\rho{{}^\smallfrown}\sigma)$. The prefix-free Kolmogorov complexity of a string $\tau$ is defined to be

$$K(\tau) = \min\{\vert\sigma\vert\mid U(\sigma)\simeq\tau\}$$

where $U$ is a universal prefix-free machine. Note that $K(\tau)$ is well defined up to within $O(1)$. In other words, if we let

$$\widehat{K}(\tau) = \min\{\vert\sigma\vert\mid\widehat{U}(\sigma)\simeq\tau\}$$

where $\widehat{U}$ is another universal prefix-free machine, then $\vert K(\tau)-\widehat{K}(\tau)\vert\le O(1)$, i.e., $\exists c \forall\tau (\vert K(\tau)-\widehat{K}(\tau)\vert\le c)$.

Corollary 10.6   Let $L$ be an r.e. subset of $\omega\times2^{<\omega}$ such that $\sum_{(m,\tau)\in L}1/2^m<\infty$. Then for all $(m,\tau)\in L$ we have $K(\tau)\le m+O(1)$.

Proof.Let $c$ be such that $\sum_{(m,\tau)\in L}1/2^m\le2^c$. Then $\sum_{(m,\tau)\in L}1/2^{m+c}\le1$, so by the Kraft/Chaitin Theorem 10.3 let $M$ be a prefix-free machine such that for all $(m,\tau)\in L$ there exists $\sigma$ such that $\vert\sigma\vert=m+c$ and $M(\sigma)=\tau$. Let $\rho$ be such that $M(\sigma)\simeq U(\rho{{}^\smallfrown}\sigma)$ for all $\sigma$. Then for all $(m,\tau)\in L$ we have $K(\tau)\le m+c+\vert\rho\vert$. This completes the proof.$\Box$

The following theorem has been attributed by Chaitin [3, Remark following Theorem 4.2] and Nies [21, Section 1] to Claus Peter Schnorr.

Theorem 10.7 (Schnorr's Theorem)   Given $X\in2^\omega$, we have that $X$ is random if and only if $K(X\upharpoonright n)\ge n-O(1)$, i.e., $\exists c \forall n (K(X\upharpoonright n)\ge n-c)$.

Proof.For $c=1,2,\ldots$ let $V_c=\{X\mid\exists n (K(X\upharpoonright n)<n-c)\}$. Note that $V_c\subseteq2^\omega$ is uniformly $\Sigma^0_1$. We claim that $\mu(V_c)<1/2^c$. To see this, for each $\tau$ such that $K(\tau)<\vert\tau\vert-c$ choose $\sigma$ such that $U(\sigma)=\tau$ and $\vert\sigma\vert<\vert\tau\vert-c$. Here $U$ is a universal prefix-free machine. By the Kraft Inequality we have

$$\sum_\sigma\frac1{2^{\vert\sigma\vert}} \le 1$$

hence

$$\mu(V_c) \le \sum_\tau\frac1{2^{\vert\tau\vert}} \... ...um_\sigma\frac1{2^{\vert\sigma\vert+c}} \le \frac1{2^c}$$

thus proving the claim. We now see that $V_c$, $c=1,2,\ldots$ is a Martin-Löf test. Therefore, if $X$ is random, we have $\exists c (X\notin V_c)$, i.e., $\exists c \forall n (K(X\upharpoonright n)\ge n-c)$, i.e., $K(X\upharpoonright n)\ge n-O(1)$. This is one direction of the theorem.

For the converse, assume $X$ is not random, say $X\in\bigcap_nU_n$ where $U_n\subseteq2^\omega$ is uniformly $\Sigma^0_1$ and $\mu(U_n)\le1/2^n$, $n=1,2,\ldots$. Let $T_n$ be uniformly r.e. and prefix-free such that $U_n=\bigcup_{\tau\in T_n}N_\tau$. We have

$$\sum_n\sum_{\tau\in T_{2n}}\frac1{2^{\vert\tau\vert-n}} ... ..._n\frac{2^n}{2^{2n}} = \sum_n\frac1{2^n} = 1 .$$

Hence by Corollary 10.6, $K(\tau)\le\vert\tau\vert-n+O(1)$ for all $n$ and all $\tau\in T_{2n}$. Since $X\in U_{2n}$ for all $n$, it follows that $K(X\upharpoonright n)\not\ge n-O(1)$.$\Box$

Remark 10.8   The above definitions and results can be uniformly relativized to an arbitrary Turing oracle $C$. Thus, a prefix-free $C$-machine is a partial $C$-recursive function $M$ from $2^{<\omega}$ to $2^{<\omega}$ such that $\mathrm{dom}(M)$ is prefix-free. We define $K^C(\tau)=\min\{\vert\sigma\vert\mid U^C(\sigma)\simeq\tau\}$ where $U^C$ is a universal prefix-free $C$-machine. The relativization of Schnorr's Theorem says that $X\in2^\omega$ is $C$-random if and only if $K^C(X\upharpoonright n)\ge n-O(1)$.

Definition 10.9 (Nies 2002)   Let $A$ and $B$ be Turing oracles. We say that $A$ is $\mathit{LK}$-reducible to $B$, abbreviated $A\le_\mathit{LK}B$, if $K^B(\tau)\le K^A(\tau)+O(1)$. In other words, for some constant $c$ we have $K^B(\tau)\le K^A(\tau)+c$ for all strings $\tau$.

Theorem 10.10 (Kjos-Hanssen/Miller/Solomon 2006)  
The following statements are pairwise equivalent.

1. $A\le_\mathit{LK}B$.
2. $A\le_\mathit{LR}B$.
3. For any $A$-r.e. set $I\subseteq\omega\times\omega$ such that $\sum_{(m,n)\in I}1/2^m<\infty$, there exists a $B$-r.e. set $J\supseteq I$ such that $\sum_{(m,n)\in J}1/2^m<\infty$.

Proof.The implication $1\Rightarrow 2$ follows from Schnorr's Theorem relativized to $A$ and $B$. The implication $2\Rightarrow 3$ follows from Lemma 5.11. Now assume $3$ and let $I=\{(m,\tau)\mid K^A(\tau)\le m\}$. Clearly $I$ is $A$-r.e. and $\sum_{(m,\tau)\in I}1/2^m<2<\infty$, so let $J\supseteq I$ be $B$-r.e. such that $\sum_{(m,\tau)\in J}1/2^m<\infty$. By Corollary 10.6 relative to $B$ we have $K^B(\tau)\le m+O(1)$ for all $(m,\tau)\in J$. Since $I\subseteq J$ it follows that $K^B(\tau)\le K^A(\tau)+O(1)$ for all $\tau$. This proves $3\Rightarrow 1$.$\Box$

Remark 10.11   The reducibilities $\le_\mathit{LK}$ and $\le_\mathit{LR}$ were originally defined by Nies [21, Section 8]. In the direction of Theorem 10.10, Nies proved the equivalence $A\le_\mathit{LK}0\Longleftrightarrow A\le_\mathit{LR}0$ (see [21, Corollary 5.3]) and noted that $A\le_\mathit{LK}B$ implies $A\le_\mathit{LR}B$. The full equivalence $A\le_\mathit{LK} B\Longleftrightarrow A\le_\mathit{LR}B$ is due to Kjos-Hanssen/Miller/Solomon [14].

Remark 10.12   By means of relativized prefix-free Kolmogorov complexity, one can prove a number of interesting results concerning $\le_\mathit{LR}$ for which no other proofs are presently known. Among these results are:

1. If $A\le_\mathit{LR}0$ and $B\le_\mathit{LR}0$ then $A\oplus B\le_\mathit{LR}0$. (See Nies [21, Theorem 6.2] and Downey/Hirschfeldt/Nies/Stephan [9, Theorem 7.2].) More generally, if $A\oplus C\le_\mathit{LR}C$ and $B\oplus C\le_\mathit{LR}C$ then $A\oplus B\oplus C\le_\mathit{LR}C$.

   Caution: It is not in general true that if $A\le_\mathit{LR}C$ and $B\le_\mathit{LR}C$ then $A\oplus B\le_\mathit{LR}C$. Indeed, in Theorem 6.10 above we have constructed a $C$ such that $0'\le_\mathit{LR}C$ yet $0'\oplus C\not\le_\mathit{LR}C$.

2. If $A\le_\mathit{LR}0$ then $A\le_T0'$, in fact $A'\le_{tt}0'$ (see Nies [21, Corollary 7.6]). More generally, if $A\oplus B\le_\mathit{LR}B$ then $A\le_TB'$ (see Lemma 7.4 above), in fact $(A\oplus B)'\le_{tt}B'$.

3. If $A\le_\mathit{LR}0$ then we can find an r.e. set $D$ such that $D\le_\mathit{LR}0$ and $A\le_TD$, in fact $A\le_{tt}D$. (See Nies [21, Theorems 7.4 and 6.2].) More generally, if $A\oplus B\le_\mathit{LR}B$ then we can find a $B$-r.e. set $D$ such that $D\oplus B\le_\mathit{LR}B$ and $A\le_TD$, in fact $A\le_{tt}D$. See also Theorem 8.9 above.

4. If $A\equiv_\mathit{LR}B$ then $A\oplus B\le_\mathit{LR}A$ and $A\oplus B\le_\mathit{LR}A$ (see Nies [21, Proposition 8.3(iii)]), hence $A\le_TB'$ and $B\le_TA'$, in fact $A'\equiv_{tt}B'\equiv_{tt}(A\oplus B)'$.

   In particular, for each $B$ there are only countably many $A$ such that $A\equiv_\mathit{LR}B$.

   Caution: By Miller/Yu [19,18], there exists a $B$ such that $\{A\mid A\le_\mathit{LR}B\}$ is uncountable. In fact, Barmpalias/Lewis/Soskova [1] have shown that this holds for any $B$ which is generalized superhigh.

The presently available proofs of most of these results use not only relativized prefix-free Kolmogorov complexity but also the formidable ``golden run'' machinery of Nies [21, Section 6]. It would be desirable to find alternative proofs in the style of Sections 3-8 above.

Bibliography

1

George Barmpalias, Andrew E. M. Lewis, and Mariya Soskova.
Randomness, lowness and degrees.
Journal of Symbolic Logic, 73:559-577, 2008.

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

Gregory J. Chaitin.
A theory of program size formally identical to information theory.
Journal of the Association for Computing Machinery, 2:329-340, 1975.

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.
Number 27 in 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, Part II: Presented Talks.
Number 15 in Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific, 2008.
432 pages.

7

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

8

R. Downey, D. Ding, S.-P. Tung, Y. H. Qiu, and M. Yasugi, editors.
Proceedings of the 7th and 8th Asian Logic Conferences.
World Scientific Publishing Company, Ltd., 2003.
480 pages.

9

Rodney G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan.
Trivial reals.
In [8], pages 103-131, 2003.

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

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.

12

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.

13

Bjørn Kjos-Hanssen.
Low-for-random reals and positive-measure domination.
Proceedings of the American Mathematical Society, 135:3703-3709, 2007.

14

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.

15

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

16

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

17

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

18

Joseph S. Miller and Liang Yu.
In preparation, 2006, to appear.

19

Joseph S. Miller and Liang Yu.
On initial segment complexity and degrees of randomness.
Transactions of the American Mathematical Society, 2005.
Preprint, 18 pages, to appear.

20

Jeanleah Mohrherr.
A refinement of low $n$ and high $n$ for the r.e. degrees.
Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 32:5-12, 1986.

21

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

22

André Nies.
Reals which compute little.
In [4], pages 260-274, 2006.

23

John M. H. Olmstead.
Real Variables.
Appleton-Century-Crofts, 1959.
VIII + 621 pages.

24

David B. Posner and Robert W. Robinson.
Degrees joining to $0'$.
Journal of Symbolic Logic, 46:714-722, 1981.

25

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

26

Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

27

Stephen G. Simpson.
Mass problems and almost everywhere domination.
Mathematical Logic Quarterly, 53:483-492, 2007.

28

Stephen G. Simpson.
Some fundamental issues concerning degrees of unsolvability.
In [6], pages 313-332, 2008.

29

Sebastiaan A. Terwijn and Domenico Zambella.
Algorithmic randomness and lowness.
Journal of Symbolic Logic, 66:1199-1205, 2001.

30

Michiel van Lambalgen.
Random Sequences.
PhD thesis, University of Amsterdam, 1987.
178 pages.

31

Domenico Zambella.
On sequences with simple initial segments.
ILLC prepublication series, University of Amsterdam, 1990.
ML-90-05, 19 pages.

About this document ...

Almost everywhere domination and superhighness

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 aedsh

The translation was initiated by Stephen G Simpson on 2009-10-29

Footnotes

... measure¹

For example, we may take $P_e^C=2^\omega\setminus U_1^C$ where $U_n^C$, $n=0,1,\ldots$ is a universal Martin-Löf test for $C$-randomness as in Theorem 3.2.

... obtain²

For example, we may take $P^C=2^\omega\setminus U_2^C$ where $U_n^C$, $n=0,1,2,\ldots$ is a universal Martin-Löf test for $C$-randomness as in Theorem 3.2.