Almost everywhere domination and superhighness

Stephen G. Simpson Pennsylvania State University

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

First draft: July 5, 2006 This draft: October 15, 2013

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 ω denote the set of natural numbers. For functions f, g : ω → ω, we say that f is dominated by g if f(n) < g(n) for all but finitely many n ∈ ω. We consider the standard “fair coin” probability measure on the space 2^{ω} 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 ∈ 2^{ω}, 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 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

Abstract 1

Contents 2

1 Introduction 2

2 Notation 3

3 Randomness 4

4 LR-reducibility 7

5 Almost everywhere domination 11

6 Some examples 14

7 Remarks on Theorem 5.13 17

8 Superhighness 18

9 Counterexamples via duality 20

10 Prefix-free Kolmogorov complexity 22

References 26

1 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, Kučera, 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, 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.

2 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 ω = {0, 1, …, n, …} to denote the set of natural numbers. We often identify Turing oracles with subsets of ω. If E is an expression denoting a natural number which may or may not be defined, we write E ↓ to mean that E is defined, and E ↑ to mean that E is undefined. If E_{1} and E_{2} are two such expressions, we write E_{1} ≃ 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 ∈ ω | φ_{e}^{(1),C}(0) ↓} = the Turing jump of C.

In particular 0′ = {e ∈ ω | φ_{e}^{(1)}(0) ↓} = a Turing oracle for the Halting Problem. For A, B ⊆ ω we write

A ⊕ B = {2n | n ∈ A} ∪ {2n + 1 | n ∈ B},

the Turing join of A and B. We write ≤_{T} to denote Turing reducibility. Thus A ≤_{T} B means that A is Turing computable from B. For A ⊆ ω we write \overline{A} = ω \ A, the complement of A. We sometimes identify A ⊆ ω with its characteristic function χ_{A} : ω → {0, 1} given by χ_{A}(n) = 1 if n ∈ A, 0 if n ∉ A.

We write 2^{ω} to denote the Cantor space, i.e., the set of total functions X : ω → {0, 1}. We write 2^{<ω} to denote the set of strings, i.e., finite sequences of 0’s and 1’s. For σ ∈ 2^{<ω} we write σ = ⟨i_{0}, …, i_{n−1}⟩ where n = |σ| = the length of σ. The empty string, denoted ⟨⟩, is the unique string of length 0. Given X ∈ 2^{ω} and n ∈ ω, we have a string X ↾ n = ⟨X(0), …, X(n − 1)⟩ of length n. For σ ∈ 2^{<ω} and X ∈ 2^{ω}, we write σ ⊂ X to mean that σ is a prefix of X, i.e., σ = X ↾ |σ|. For σ, τ ∈ 2^{<ω}, we write σ ⊂ τ to mean that σ is a prefix of τ, i.e., a proper initial segment of τ. We write σ^{⌢}τ = the concatenation, σ followed by τ. Thus |σ^{⌢}τ| = |σ| + |τ|. Moreover, σ ⊂ τ if and only if σ^{⌢}ρ = τ for some ρ ≠ ⟨⟩. For σ ∈ 2^{<ω} and X ∈ 2^{ω} we write σ^{⌢}X = the concatenation, σ followed by X. Thus σ ⊂ X if and only if σ^{⌢}Y = X for some Y.

Given σ ∈ 2^{<ω}, we write N_{σ} = {X ∈ 2^{ω} | σ ⊂ X}. Thus N_{σ} is a basic open neighborhood in the Cantor space. The fair-coin probability measure μ on 2^{ω} is defined by μ(N_{σ}) = 1/2^{|σ|}. In particular μ(2^{ω}) = 1. A set S ⊆ 2^{<ω} is said to be prefix-free if there are no σ, τ ∈ S such that σ ⊂ τ. Note that if S is prefix-free then μ(⋃_{σ∈S} N_{σ}) = ∑_{σ∈S} 1/2^{|σ|}.

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

3 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 Kučera [15] and many others.

Definition 3.1 (Martin-Löf 1966). Let C be a Turing oracle. We say that X ∈ 2^{ω} is C-random if X ∉ ⋂_{n} U_{n}^{C} for all uniformly Σ_{1}^{0,C} sequences of sets U_{n}^{C} ⊆ 2^{ω}, n = 0, 1, 2, … such that μ(U_{n}^{C}) ≤ 1/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, Kučera 1985). We can construct a universal Martin-Löf test. In other words, we can find uniformly Σ_{1}^{0,C} sets U_{n}^{C}, n = 0, 1, 2, … such that μ(U_{n}^{C}) ≤ 1/2^{n} and, for all X ∈ 2^{ω} and all Turing oracles C, X is C-random if and only if X ∉ ⋂_{n} U_{n}^{C}.

Proof. Let V_{i}^{C}, i = 0, 1, 2, … be a standard, uniform enumeration of all Σ_{1}^{0,C} subsets of 2^{ω}. For s = 0, 1, … let V_{i,s}^{C} be the set of X ∈ 2^{ω} which get into V_{i}^{C} by means of a computation in ≤ s steps using only oracle information from C ↾ s. Thus V_{i,0}^{C} ⊆ V_{i,1}^{C} ⊆ ⋯ ⊆ V_{i,s}^{C} ⊆ ⋯, s = 0, 1, … is a uniformly C-recursive sequence of clopen sets, and V_{i}^{C} = ⋃_{s} V_{i,s}^{C}. For rational numbers r let

V_{i}^{C}[r] = ⋃_{μ(V_{i,s}^{C})≤r} V_{i,s}^{C} .

Intuitively, V_{i}^{C}[r] is just V_{i}^{C} enumerated so long as its measure is ≤ r. Note that V_{i}^{C}[r] is uniformly Σ_{1}^{0,C}, and μ(V_{i}^{C}[r]) ≤ r, and V_{i}^{C}[r] = V_{i}^{C} if and only if μ(V_{i}^{C}) ≤ r. Now for all e, n ∈ ω let Ũ_{e,n}^{C} = V_{i}^{C}[1/2^{n}] if φ_{e}^{(1)}(n) ≃ i, and ∅ if φ_{e}^{(1)}(n) ↑. Again Ũ_{e,n}^{C} is uniformly Σ_{1}^{0,C}. Moreover, for each e, the sequence Ũ_{e,n}^{C}, n = 0, 1, … is a Martin-Löf test, and all Martin-Löf tests occur in this way. Finally let U_{n}^{C} = ⋃_{e} Ũ_{e,e+n+1}^{C}. Then U_{n}^{C} is uniformly Σ_{1}^{0,C}, and μ(U_{n}^{C}) ≤ ∑_{e} 1/2^{e+n+1} = 1/2^{n} for all n, so U_{n}^{C}, n = 0, 1, … is a Martin-Löf test. Moreover, for an arbitrary Martin-Löf test Ũ_{e,n}^{C}, n = 0, 1, …, we have ⋂_{n} Ũ_{e,n}^{C} ⊆ ⋂_{n} U_{n}^{C}. Thus U_{n}^{C}, n = 0, 1, … is a universal Martin-Löf test. □

Corollary 3.3 (Kučera 1985). For any Turing oracle C, the set

R^{C} = {X ∈ 2^{ω} | X is C-random}

is uniformly Σ_{2}^{0,C} and of measure 1.

Proof. By Theorem 3.2 let U_{n}^{C}, n = 0, 1, … be a universal Martin-Löf test for C-randomness. Then R^{C} = 2^{ω} \ ⋂_{n} U_{n}^{C}. Moreover U_{n}^{C} is uniformly Σ_{1}^{0,C}, hence ⋂_{n} U_{n}^{C} is uniformly Π_{2}^{0,C}, hence R^{C} is uniformly Σ_{2}^{0,C}. Also μ(U_{n}^{C}) ≤ 1/2^{n} for all n, hence μ(⋂_{n} U_{n}^{C}) = 0, hence μ(R^{C}) = 1. □

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

Lemma 3.4. Assume that A ⊕ 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 ∈ ⋂_{n} V_{n}^{A} where V_{n}^{A} is uniformly Σ_{1}^{0,A} of measure ≤ 1/2^{n}. Let W_{n} = {X ⊕ Y | X ∈ 2^{ω}, Y ∈ V_{n}^{X}[1/2^{n}]} and note that W_{n} is uniformly Σ_{1}^{0} of measure ≤ 1/2^{n}. We have A ⊕ B ∈ ⋂_{n} W_{n}, contradicting the assumption that A ⊕ B is random. □

Lemma 3.5 (Solovay’s Lemma). Assume A is random. Let U_{n} ⊆ 2^{ω}, n = 0, 1, … be uniformly Σ_{1}^{0} such that ∑_{n=0}^{∞} μ(U_{n}) < ∞. Then ∃^{<∞}n (A ∈ U_{n}), i.e., {n | A ∈ U_{n}} is finite.

Proof. For each k let W_{k} = {X | ∃^{≥k}n (X ∈ U_{n})}. Let c be such that ∑_{n=0}^{∞} μ(U_{n}) ≤ c. We claim that μ(W_{k}) ≤ c/k. To see this, let W_{k}^{N} = {X | (∃^{≥k}n ≤ N) (X ∈ U_{n})} and note that W_{k} = ⋃_{N} W_{k}^{N}. For all N we have

\begin{aligned}c & ≥ ∑_{n=0}^{∞} μ(U_{n}) ≥ ∑_{n=0}^{N} μ(U_{n}) = ∑_{n=0}^{N} ∫_{2^{ω}} U_{n}(X) dX \\ & = ∫_{2^{ω}} ∑_{n=0}^{N} U_{n}(X) dX ≥ ∫_{2^{ω}} k W_{k}^{N}(X) dX = k μ(W_{k}^{N}) \end{aligned}

so μ(W_{k}^{N}) ≤ c/k for all N. It follows that μ(W_{k}) ≤ c/k, and our claim is proved. Since A is random and W_{k} is uniformly Σ_{1}^{0}, we have A ∉ ⋂_{k} W_{k}, hence A ∉ W_{k} for some k, hence ∃^{<k}n (A ∈ U_{n}). This proves the lemma. □

Theorem 3.6 (van Lambalgen’s Theorem). A ⊕ 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 ⊕ B is not random. We have A ⊕ B ∈ ⋂_{n} W_{n} where W_{n} is uniformly Σ_{1}^{0} with μ(W_{n}) ≤ 1/2^{n}. By passing to a subsequence, we may assume that μ(W_{n}) ≤ 1/2^{2n}. Let U_{n} = {X | μ({Y | X ⊕ Y ∈ W_{n}}) > 1/2^{n}} and note that U_{n} is uniformly Σ_{1}^{0}. Moreover μ(U_{n}) ≤ 1/2^{n} for all n, because otherwise we would have

μ(W_{n}) > μ(U_{n}) · \frac{1}{2^{n}} > \frac{1}{2^{n}} · \frac{1}{2^{n}} = \frac{1}{2^{2n}} ,

a contradiction. Since A is random, it follows by Lemma 3.5 that {n | A ∈ U_{n}} is finite. Thus for all but finitely many n we have A ∉ U_{n}, i.e., μ({Y | A ⊕ Y ∈ W_{n}}) ≤ 1/2^{n}. Let V_{n}^{A} = {Y | A ⊕ Y ∈ W_{n}}. Then μ(V_{n}^{A}) ≤ 1/2^{n} for all but finitely many n, and V_{n}^{A} is uniformly Σ_{1}^{0,A}. Moreover B ∈ ⋂_{n} V_{n}^{A}, contradicting the assumption that B is A-random. □

Next we present the Kučera/Gács Theorem, from Kučera [15].

Lemma 3.7. Let P ⊆ 2^{ω} be Π_{1}^{0} of positive measure. Then for all X ∈ 2^{ω} there exists Y ∈ P such that Y ≤_{T} X ⊕ 0′ and X ≤_{T} Y.

Proof. Claim: If μ(P ∩ N_{σ}) ≥ 1/2^{k} where k ≥ 1, then there are at least two strings τ ⊃ σ such that |τ| = 2k and μ(P ∩ N_{τ}) ≥ 1/2^{4k}.

To prove the claim, note first that μ(N_{σ}) = 1/2^{|σ|} ≥ 1/2^{k}, hence |σ| ≤ k < 2k since k ≥ 1. If the conclusion of the claim were false, we would have

\begin{aligned}μ(P ∩ N_{σ}) & = & ∑_{τ⊃σ, |τ|=2k} μ(P ∩ N_{τ}) \\ & ≤ & \frac{1}{2^{2k}} + (2^{2k−|σ|} − 1) \frac{1}{2^{4k}} & < & \frac{1}{2^{2k}} + 2^{2k} \frac{1}{2^{4k}} & ≤ & \frac{1}{2^{k}} \end{aligned}

contradicting the hypothesis of the claim.

To prove Lemma 3.7, assume that P ⊆ 2^{ω} is Π_{1}^{0} with μ(P) > 0, say μ(P) ≥ 1/2^{k} where k ≥ 1. Note that N_{⟨⟩} = 2^{ω}, hence μ(P ∩ N_{⟨⟩}) = μ(P) ≥ 1/2^{k}. Applying our claim repeatedly, define f : 2^{<ω} → 2^{<ω} as follows. Let f(⟨⟩) = ⟨⟩. Suppose inductively that f(ρ) has already been defined. Let k_{i} = 4^{i}k where i = |ρ|. Let f(ρ^{⌢}⟨0⟩) (respectively f(ρ^{⌢}⟨1⟩)) be the lexicographically leftmost (respectively rightmost) τ ⊃ f(ρ) such that |τ| = 2k_{i} and μ(P ∩ N_{τ}) ≥ 1/2^{4k_{i}}. Our claim implies that f(ρ^{⌢}⟨0⟩) and f(ρ^{⌢}⟨1⟩) exist and are incompatible. It is straightforward to check that f ≤_{T} 0′.

Given X ∈ 2^{ω}, let Y = f(X) = ⋃_{i} f(X ↾ i). Clearly Y ∈ P and Y ≤_{T} X⊕0′. We claim that X ≤_{T} Y. To prove this, we describe how to compute X using an oracle for Y. Let P = ⋂_{s} P_{s} where P_{0} ⊇ P_{1} ⊇ ⋯ ⊇ P_{s} ⊇ ⋯ is a recursive sequence of clopen sets. Suppose we have already computed ρ = X ↾ i. We also have f(ρ) = Y ↾ 2k_{i−1} if i > 0, or ⟨⟩ if i = 0. Our construction implies that Y ↾ 2k_{i} is either the leftmost or the rightmost τ ⊃ f(ρ) of length 2k_{i} such that μ(P ∩ N_{τ}) ≥ 1/2^{4k_{i}}. Therefore, for all sufficiently large stages s, we will have μ(P_{s} ∩ N_{τ}) < 1/2^{4k_{i}} for all τ ⊃ f(ρ) of length 2k_{i} lying to the left (respectively right) of Y ↾ 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. □

Theorem 3.8 (Kučera/Gács Theorem). For any X ≥_{T} 0′ we can find a random Y such that Y ≡_{T} X.

Proof. By Corollary 3.3 let P ⊆ 2^{ω} be Π_{1}^{0} of positive measure such that ∀Y (Y ∈ P ⇒ Y is random). Applying Lemma 3.7 to any X ≥_{T} 0′, we obtain Y ∈ P such that X ≡_{T} Y. □

Corollary 3.9. Assume that A is random and A ≤_{T} B and B is C-random and C ≥_{T} 0′. Then A is C-random.

Proof. Since C ≥_{T} 0′, we may assume by the Kučera/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 ⊕C is random, hence C is B-random. Since A ≤_{T} B, it follows that C is A-random. Now, since A is random, it follows that A ⊕ C is random, hence A is C-random. □

Remarkably, the previous corollary holds even without the assumption C ≥_{T} 0′. We mention without proof the following theorem of Miller/Yu [18].

Theorem 3.10 (Miller/Yu 2004). If A is random and A ≤_{T} B where B is C-random, then A is C-random.

4 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 LR-reducible to B, abbreviated A ≤_{LR} B, if

∀X (X is B-random ⇒ X is A-random).

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

Remark 4.3. Evidently the reducibility relation ≤_{LR} is closely related to the notion of low-for-randomness, which was first introduced by Zambella [31] and has been studied extensively by Kučera/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 ≤_{LR} 0. Relativizing to B, we see that A is low-for-random relative to B if and only if A ⊕ B ≤_{LR} B.

However, caution is required, because in general A ≤_{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′ ≤_{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 ≤_{T} 0′ ≤_{LR} B ≤_{T} C, 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 ≤_{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 ≤_{T} B′, hence for each B there are only countably many such A. But Miller and Yu [18, 19] have constructed a B such that {A | A ≤_{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 ≡_{LR} defined by letting A ≡_{LR} B if and only if A ≤_{LR} B and B ≤_{LR} A. It can be shown (see Remark 10.12) that if A ≡_{LR} B then A is low-for-random relative to B and B is low-for-random relative to A. It follows that each ≡_{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 ≤_{LR} B.

2. Each Π_{1}^{0,A} set of positive measure includes a Π_{1}^{0,B} set of positive measure.

3. There exists a Π_{1}^{0,A} set P such that ∀X (X ∈ P ⇒ X is A-random) and P includes a Π_{1}^{0,B} set of positive measure.

4. There exists a Π_{1}^{0,B} set Q of positive measure such that ∀Y (Y ∈ Q ⇒ 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 ⊆ 2^{ω} be Π_{1}^{0,B}. The following statements are pairwise equivalent.

(a) P is of positive measure.

(b) ∃Q (Q ⊆ P and Q is nonempty Π_{1}^{0,B} and ∀X (X ∈ Q ⇒ X is B-random)).

(c) ∃X (X ∈ P and X is B-random).

Proof. By Corollary 3.3, {X ∈ 2^{ω} | X is B-random} is Σ_{2}^{0,B} and of measure 1. From this it follows easily that (a) ⇒ (b). Trivially (b) ⇒ (c). In order to prove (c) ⇒ (a), assume μ(P) = 0. We have P = ⋂_{s} P_{s} where P_{0} ⊇ P_{1} ⊇ ⋯ ⊇ P_{s} ⊇ ⋯ is a B-recursive sequence of clopen sets. Hence lim_{s} μ(P_{s}) = μ(P) = 0. Let U_{k} = P_{f(k)} where f(k) = least s such that μ(P_{s}) ≤ 1/2^{k}. Then U_{k}, k = 1, 2, … is a Martin-Löf test for B-randomness, and P = ⋂_{k} U_{k}. Hence no X ∈ P is B-random, Q.E.D. □

Lemma 4.8. Assume that Q is Π_{1}^{0,B} such that ∀X (X ∈ Q ⇒ X is B-random). Then ∀σ (Q ∩ N_{σ} ≠ ∅ ⇒ Q ∩ N_{σ} is of positive measure).

Proof. This follows easily from Lemma 4.7. □

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

Definition 4.9 (Kučera 1985). Let U, V ⊆ 2^{ω} be Σ_{1}^{0,A}. We define a product operation. Let U = ⋃_{σ∈S} N_{σ} and V = ⋃_{τ∈T} N_{τ} where S, T ⊆ 2^{<ω} are A-r.e. and prefix-free. We define the product

UV = ⋃_{σ∈S,τ∈T} N_{σ^{⌢}τ} .

Note that {σ^{⌢}τ | σ ∈ S, τ ∈ T } is again A-r.e. and prefix-free. Note also that:

(a) UV is Σ_{1}^{0,A}.

(b) Given indices of U and V qua Σ_{1}^{0,A} sets, we can compute an index of UV qua Σ_{1}^{0,A} set.

(c) UV ⊆ U.

(d) μ(UV) = μ(U)μ(V).

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

Definition 4.10 (Kučera 1985). Dually, let P, Q ⊆ 2^{ω} be Π_{1}^{0,A}. We define the product P Q = \overline{\overline{P} \overline{Q}}, where \overline{P} = 2^{ω} \ P. Note that:

(a) P Q is Π_{1}^{0,A}.

(b) Given indices of P and Q qua Π_{1}^{0,A} sets, we can compute an index of P Q qua Π_{1}^{0,A} set.

(c) P Q ⊇ P.

(d) μ(P Q) = 1 − (1 − μ(P))(1 − μ(Q)).

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

We now begin the proof of Theorem 4.6. Let us say that P ⊆ 2^{ω} is fat if it includes a Π_{1}^{0,B} set of positive measure. The implication 1 ⇒ 2 of Theorem 4.6 may be rephrased as follows:

If A ≤_{LR} B, then every Π_{1}^{0,A} 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 ⊆ 2^{ω} be Π_{1}^{0,A}. If P Q is fat, then at least one of P and Q is fat.

Proof. Let U = \overline{P}. Then U is Σ_{1}^{0,A}, say U = ⋃_{σ∈S} N_{σ} where S ⊆ 2^{<ω} is A-r.e. and prefix-free. We have P Q = P ∪⋃_{σ∈S}(σ^{⌢}Q) where σ^{⌢}Q = {σ^{⌢}X | X ∈ Q}. Suppose now that P Q is fat, say R ⊆ P Q where R is Π_{1}^{0,B} and μ(R) > 0. By Lemmas 4.7 and 4.8 we may safely assume that ∀X (X ∈ R ⇒ X is B-random), hence ∀σ (R ∩ N_{σ} ≠ ∅ ⇒ μ(R ∩ N_{σ}) > 0). If R ⊆ P then P is fat and we are done. Otherwise there exists σ ∈ S such that R ∩ N_{σ} ≠ ∅, hence μ(R ∩ N_{σ}) > 0. But R ∩ N_{σ} = R ∩ (σ^{⌢}Q) ⊆ σ^{⌢}Q, hence σ^{⌢}Q is fat, hence Q is fat, Q.E.D. □

We now prove the implication 1 ⇒ 2 of Theorem 4.6. Assume A ≤_{LR} B and suppose that P is Π_{1}^{0,A} of positive measure. We must show that P is fat.

Let U = \overline{P}, so μ(U) = 1 − μ(P) < 1. Let n be such that μ(U)^{n} < 1/2. Let U^{k} = U ⋯ U (k times) and P^{k} = P ⋯ P (k times). Note that U^{k} = \overline{P^{k}}. We have μ(U^{nk}) = μ(U)^{nk} < 1/2^{k}, hence U^{nk}, k = 1, 2, … is a Martin-Löf test for A-randomness. It follows that ∀X (X ∈ ⋂_{k} U^{k} ⇒ X is not A-random).

By Lemma 4.7 let Q be nonempty Π_{1}^{0,B} such that ∀X (X ∈ Q ⇒ X is B-random). By Lemma 4.8 we have ∀σ (Q ∩ N_{σ} ≠ ∅ ⇒ μ(Q ∩ N_{σ}) > 0).

We claim that ∃σ ∃k (Q∩N_{σ} ≠ ∅ and Q∩N_{σ} ∩U^{k} = ∅). Otherwise we would have ∀σ ∀k (Q ∩ N_{σ} ≠ ∅ ⇒ Q ∩ N_{σ} ∩ U^{k} ≠ ∅). Therefore, since U^{k} is Σ_{1}^{0,A}, we would be able to find σ_{0} ⊂ σ_{1} ⊂ ⋯ ⊂ σ_{k} ⊂ ⋯ such that N_{σ_{k}} ∩ Q ≠ ∅ and N_{σ_{k}} ⊆ U^{k} for all k. Setting X = ⋃_{k} σ_{k} we would have X ∈ Q and X ∈ ⋂_{k} U^{k}. Thus X would be B-random but not A-random, contradicting our assumption A ≤_{LR} B. This proves our claim.

Let σ and k be as in our claim. We then have Q ∩ N_{σ} ⊆ P^{k}, hence P^{k} is fat. It follows by Lemma 4.11 that P is fat. This completes the proof of 1 ⇒ 2.

It remains to prove 2 ⇒ 3 and 3 ⇒ 4 and 4 ⇒ 1. The implication 2 ⇒ 3 follows easily from Lemma 4.7. The implication 3 ⇒ 4 is trivial. In order to prove 4 ⇒ 1, we first prove the following lemma due to Kučera [15].

Lemma 4.12 (Kučera 1985). Let P be Π_{1}^{0,A} of positive measure. Then for all A-random X there exist σ and Y such that X = σ^{⌢}Y and Y ∈ P.

Proof. Suppose P is Π_{1}^{0,A} of positive measure. As before let U = \overline{P} = ⋃_{σ∈S} N_{σ} 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, … is a Martin-Löf test for A-randomness, we have X ∉ U^{k} for some k. Choosing the least such k, we have X ∈ U^{k−1} ∩ P^{k}, i.e., X = σ_{1}^{⌢} ⋯^{⌢}σ_{k−1}^{⌢}Y for some σ_{1}, …, σ_{k−1} ∈ S and Y ∈ P. Letting σ = σ_{1}^{⌢} ⋯^{⌢}σ_{k−1} we have X = σ^{⌢}Y, Q.E.D. □

We now prove 4 ⇒ 1. Assuming 4, let Q be Π_{1}^{0,B} of positive measure such that ∀Y (Y ∈ Q ⇒ 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 = σ^{⌢}Y for some Y ∈ Q. It follows that Y is A-random. Hence X is A-random. Thus A ≤_{LR} B, Q.E.D.

This completes the proof of Theorem 4.6. □

Corollary 4.13 (Kjos-Hanssen 2005). The binary relation A ≤_{LR} B is Σ_{3}^{0}.

Proof. Let P_{i}^{C}, i ∈ ω be a standard, uniform enumeration of all Π_{1}^{0,C} subsets of 2^{ω}, where C is a Turing oracle. Fix e ∈ ω such that for all C, P_{e}^{C} is of positive measure^{1} and ∀X (X ∈ P_{e}^{C} ⇒ X is C-random). By Theorem 4.6, A ≤_{LR} B is equivalent to ∃i (μ(P_{i}^{B}) > 0 and P_{i}^{B} ⊆ P_{e}^{A}). A Tarski/Kuratowski computation (see Rogers [25, Section 14.3]) shows that this is Σ_{3}^{0}. □

Similarly one can prove:

Corollary 4.14 (Kjos-Hanssen 2005). The ternary relation A′ ⊕ B ≤_{LR} C is Σ_{3}^{0}. More generally, for each k the k + 2-ary relation A′_{1} ⊕ ⋯ ⊕ A′_{k} ⊕ B ≤_{LR} C is Σ_{3}^{0}.

1For example, we may take P_{e}^{C} = 2^{ω} \U_{1}^{C} where U_{n}^{C}, n = 0, 1, … is a universal Martin-Löf test for C-randomness as in Theorem 3.2.

Remark 4.15. Earlier Nies had proved that {A | A ≤_{LR} 0} is Σ_{3}^{0}. Another interesting result due to Nies and Hirschfeldt (see Remark 10.12 below) is that if A ≤_{LR} 0 and B ≤_{LR} 0 then A ⊕ B ≤_{LR} 0. Thus {A | A ≤_{LR} 0} is a Σ_{3}^{0} Turing ideal. See Nies [21, Theorems 6.2 and 7.9].

5 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 : ω → ω 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 ∈ 2^{ω}, 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 ∈ 2^{ω}.

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

1. B is uniformly almost everywhere dominating.

2. Every Π_{2}^{0} subset of 2^{ω} includes a Σ_{2}^{0,B} set of the same measure.

3. Every Π_{1}^{0,0′} subset of 2^{ω} includes a Σ_{2}^{0,B} set of the same measure.

Proof. See Dobrinen/Simpson [7, Theorem 3.2]. □

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

1. B is almost everywhere dominating.

2. Given a Π_{2}^{0} set Q ⊆ 2^{ω}, and given ϵ > 0, we can find a Π_{1}^{0,B} set P ⊆ Q such that μ(P) ≥ μ(Q) − ϵ.

3. Given a Π_{1}^{0,0′} set Q ⊆ 2^{ω}, and given ϵ > 0, we can find a Π_{1}^{0,B} set P ⊆ Q such that μ(P) ≥ μ(Q) − ϵ.

Proof. See Dobrinen/Simpson [7, Theorem 3.3]. □

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 Π_{2}^{0} subset of 2^{ω} of positive measure includes a Π_{1}^{0,B} set of positive measure. Equivalently, every Π_{1}^{0,0′} subset of 2^{ω} of positive measure includes a Π_{1}^{0,B} set of positive measure.

We then have: Theorem 5.5 (Kjos-Hanssen 2005). B is positive-measure dominating if and only if 0′ ≤_{LR} B. Proof. This is immediate from the special case A = 0′ of Theorem 4.6. □ Corollary 5.6 (Kjos-Hanssen 2005). The set

PMD = {B | B is positive-measure dominating}

is Σ_{3}^{0}. Proof. This is immediate from Theorem 5.5 and Corollary 4.14. □

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′ ≤_{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

AED = {B | B is almost everywhere dominating}

and

UAED = {B | B is uniformly almost everywhere dominating} are Σ_{3}^{0}. In fact, AED = UAED = PMD. Proof. This is immediate from Corollary 5.6 and Theorem 5.7. □

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 Π_{1}^{0} subsets of 2^{ω}. 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 ≤_{LR} B. Let f : ω → ω be recursive. For all A-r.e. sets I such that ∑_{i∈I} 1/2^{f(i)} < ∞, there exists a B-r.e. set J ⊇ I such that ∑_{i∈J} 1/2^{f(i)} < ∞.

Proof. We use the following fact from analysis. Given 0 < a_{i} < 1, i = 0, 1, …, we have

∑_{i=0}^{∞} a_{i} < ∞ if and only if ∏_{i=0}^{∞}(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) ≠ 0 for all i. Let

D_{i} = {X ∈ 2^{ω} | ∃n (X(n) = 1 and g(i) ≤ n < g(i + 1))}

where g(i) = ∑_{k=0}^{i−1} f(k). Note that the D_{i}’s are mutually independent and clopen and μ(D_{i}) = 1 − 1/2^{f(i)}. Consider the Π_{1}^{0,A} set P = ⋂_{i∈I} D_{i}. By hypothesis ∑_{i∈I} 1/2^{f(i)} < ∞, hence

μ(P) = ∏_{i∈I} μ(D_{i}) = ∏_{i∈I}(1 − 1/2^{f(i)}) > 0.

Let Q ⊆ P be Π_{1}^{0,B} such that μ(Q) > 0. Let J = {i | D_{i} ⊇ Q}. Clearly J ⊇ I and J is B-r.e. Moreover ⋂_{i∈J} D_{i} ⊇ Q, hence

∏_{i∈J}(1 − 1/2^{f(i)}) = ∏_{i∈J} μ(D_{i}) = μ(⋂_{i∈J} D_{i}) ≥ μ(Q) > 0,

hence ∑_{i∈J} 1/2^{f(i)} < ∞, Q.E.D. □

Remark 5.12. Under the same hypothesis, A ≤_{LR} B, we can obtain the following stronger conclusion. Given a recursive sequence of recursive real numbers r_{i} ≥ 0, i = 0, 1, …, and given an A-r.e. set I such that ∑_{i∈I} r_{i} < ∞, we can effectively find a B-r.e. set J ⊇ I such that ∑_{i∈J} r_{i} < ∞.

Theorem 5.13 (Kjos-Hanssen/Miller/Solomon 2006). Assume A ≤_{LR} B and A ≤_{T} B′. Then every Π_{1}^{0,A} subset of 2^{ω} includes a Σ_{2}^{0,B} set of the same measure.

Proof. Assume A ≤_{LR} B and A ≤_{T} B′. We must show that every Π_{1}^{0,A} set includes a Σ_{2}^{0,B} set of the same measure. Equivalently, we shall show that every Σ_{1}^{0,A} set is included a Π_{2}^{0,B} set of the same measure.

Let U ⊆ 2^{ω} be Σ_{1}^{0,A}. Write

U = {X | ∃n (X ↾ n ∈ S^{A})}

where S^{A} ⊆ 2^{<ω} is A-r.e. and prefix-free. Let

I = {(σ, τ) | τ ∈ S^{A} with use σ ⊂ A}.

Thus U = {X | ∃n ∃σ ((σ, X ↾ n) ∈ I)}. Clearly I is A-r.e. and

∑_{(σ,τ)∈I} 1/2^{|τ|} = ∑_{τ∈S^{A}} 1/2^{|τ|} ≤ 1.

By Lemma 5.11 let J ⊇ I be B-r.e. such that ∑_{(σ,τ)∈J} 1/2^{|τ|} < ∞.

We may safely assume that A ∈ 2^{ω}. Since A ≤_{T} B′, let A = lim_{s} A_{s} be a B-recursive approximation of A. Let

V_{s} = {X ∈ 2^{ω} | ∃n ∃σ ((σ, X ↾ n) ∈ J_{s})}

where

J_{s} = {(σ, τ) ∈ J | ∃t ≥ s (τ ∈ S^{A_{t}} with use σ ⊂ A_{t})}.

Clearly ⋂_{s} V_{s} is Π_{2}^{0,B}. Moreover I ⊆ ⋂_{s} J_{s}, hence U ⊆ ⋂_{s} V_{s}.

Claim 1: I = ⋂_{s} J_{s}.

To see this, suppose (σ, τ) ∉ I. Then either (1) σ ⊄ A, or (2) σ ⊂ A but τ is not in S^{A} with use σ. In case (1) we have σ ⊄ A_{t} for all sufficiently large t, hence (σ, τ) ∉ ⋂_{s} J_{s}. In case (2) we have σ ⊂ A_{t} for all sufficiently large t, hence τ is not in S^{A_{t}} with use σ, hence again (σ, τ) ∉ ⋂_{s} J_{s}, proving our claim.

Claim 2: μ(U) = μ(⋂_{s} V_{s}).

To see this, fix ϵ > 0. Let F be a finite subset of J such that ∑_{(σ,τ)∈J\F} 1/2^{|τ|} < ϵ. Let s be so large that, for all (σ, τ) ∈ F, if (σ, τ) ∉ I then (σ, τ) ∉ J_{s}. Then

μ(V_{s} \ U) ≤ ∑_{(σ,τ)∈J_{s}\I} 1/2^{|τ|} ≤ ∑_{(σ,τ)∈J\F} 1/2^{|τ|} < ϵ

proving our claim.

This completes the proof of Theorem 5.13. □

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.

6 Some examples

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

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

Theorem 6.1 (Kučera/Terwijn 1997). We can find a nonrecursive r.e. set A ⊆ ω such that A ≤_{LR} 0, i.e., A is low-for-random.

Proof. By Corollary 3.3 we know that {X ∈ 2^{ω} | X is random} is Σ_{2}^{0} and of measure 1. Therefore, we can find a Π_{1}^{0} set P ⊆ 2^{ω} such that μ(P) > 1/2 and ∀X (X ∈ P ⇒ X is random). By uniformly relativizing the construction of P to an arbitrary Turing oracle C, we obtain^{2} a Π_{1}^{0,C} set P^{C} ⊆ 2^{ω} such that μ(P^{C}) > 1/2 and ∀X (X ∈ P^{C} ⇒ X is C-random). For C ∈ 2^{ω} let U^{C} = \overline{P^{C}} = 2^{ω} \ P^{C}. Note that U^{C} is uniformly Σ_{1}^{0,C} and μ(U^{C}) < 1/2.

To prove the theorem, we shall build a nonrecursive r.e. set A and a Σ_{1}^{0} set V ⊇ U^{A} such that μ(V) < 1. Letting Q = 2^{ω} \ V, it will follow that Q is a Π_{1}^{0} subset of P^{A} of positive measure. Hence by Theorem 4.6 A ≤_{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, … be a recursive enumeration of the r.e. subsets of ω. Let W_{e,s} be the set of n ∈ ω which get into W_{e} by means of a computation in ≤ s steps. Thus W_{e} = ⋃_{s} W_{e,s}. Let U_{s}^{C} be the set of X ∈ 2^{ω} which get into U^{C} by means of a computation in ≤ s steps using only oracle information from C ↾ s. Thus U_{s}^{C}, s = 0, 1, … is a uniformly C-recursive sequence of clopen sets in 2^{ω}, and U^{C} = ⋃_{s} U_{s}^{C}.

Our r.e. set A ⊆ ω will be constructed as A = ⋃_{s} A_{s} where A_{0} ⊆ A_{1} ⊆ ⋯ ⊆ A_{s} ⊆ ⋯ is a recursive sequence of finite sets. Let V = ⋃_{s} U_{s}^{A_{s}}. Clearly U^{A} ⊆ V ⊆ 2^{ω} and V is Σ_{1}^{0}. Our construction of A will insure that μ(V \ U^{A}) ≤ 1/2. Since μ(U^{A}) < 1/2, we shall have μ(V) < 1 as desired.

Note that U_{s}^{A_{s}}, s = 0, 1, … is a recursive sequence of clopen sets in 2^{ω}. Let V_{t} = U_{t}^{A_{t}} \ ⋃_{s<t} U_{s}^{A_{s}}. Then V_{t}, t = 0, 1, … is a recursive, pairwise disjoint sequence of clopen sets in 2^{ω}, and V = ⋃_{s} U_{s}^{A_{s}} = ⋃_{t} V_{t}.

Our construction of A is as follows. At stage 0 let A_{0} = ∅. At stage s + 1, for each e < s such that A_{s} ∩ W_{e,s} = ∅, look for n ∈ W_{e,s} such that n ≥ 2e and ∑_{n<t≤s} μ(V_{t}) ≤ 1/2^{e+2} and put the least such n into A_{s+1}.

Finally let A = ⋃_{s} A_{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 ≥ 2e insures that \overline{A} = ω \ A is infinite.

Lemma 6.2. For each e, if W_{e} is infinite then A ∩ W_{e} ≠ ∅.

Proof. Since the V_{t}’s are pairwise disjoint, we have ∑_{t} μ(V_{t}) = μ(⋃_{t} V_{t}) = μ(V) ≤ 1. Assume that W_{e} is infinite. Let n ∈ W_{e} be so large that n ≥ 2e and ∑_{n<t} μ(V_{t}) ≤ 1/2^{e+2}. Let s be so large that n ∈ W_{e,s}. Then by construction A_{s+1} ∩ W_{e,s} ≠ ∅. □

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 μ(V \ U^{A}) ≤ 1/2.

2For example, we may take P^{C} = 2^{ω} \ U_{2}^{C} where U_{n}^{C}, n = 0, 1, 2, … is a universal Martin-Löf test for C-randomness as in Theorem 3.2.

Proof. Given X ∈ V \ U^{A}, let t be such that X ∈ V_{t}. Then X ∈ U_{t}^{A_{t}} \ U^{A}, hence A ↾ t ≠ A_{t} ↾ 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 ⊆ ⋃_{n<t≤s} V_{t}, hence of measure ≤ ∑_{n<t≤s} μ(V_{t}) ≤ 1/2^{e+2}. Hence the set of all such X’s is of measure ≤ ∑_{e} 1/2^{e+2} = 1/2. □

This completes the proof of Theorem 6.1. □

We now present the Pseudojump Inversion Theorem.

Definition 6.4. For an arbitrary Turing oracle C, let W_{e}^{C}, e = 0, 1, … be a standard, uniform enumeration of all C-r.e. subsets of ω. For each fixed e, the operator J_{e} : 2^{ω} → 2^{ω} given by J_{e}(C) = C⊕W_{e}^{C} is called a pseudojump operator or an REA-operator. (The acronym REA stands for “r.e. and above”.)

Remark 6.5. Note that the Turing jump operator J(C) = C ⊕ 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 ≥_{T} 0′, we can find a B such that J_{e}(B) ≡_{T} B ⊕ 0′ ≡_{T} A.

Proof. For C ∈ 2^{ω} and e ∈ ω, we write W_{e,s}^{C} to denote the set of n ∈ ω which get into W_{e}^{C} by means of a computation in ≤ s steps using only oracle information from C ↾ s. Note that W_{e}^{C} = ⋃_{s} W_{e,s}^{C}. We also write W_{e,s}^{C} = W_{e}^{τ} where τ = C ↾ s.

Given A ∈ 2^{ω}, our construction of B is as follows. We define a sequence of strings τ_{0} ⊆ τ_{1} ⊆ ⋯ ⊆ τ_{n} ⊆ ⋯, n = 0, 1, . . .. Let τ_{0} = ⟨⟩. For each n, given τ_{2n}, if there exists τ ⊇ τ_{2n} such that n ∈ W_{e}^{τ}, let τ_{2n+1} be the least such τ. Otherwise let τ_{2n+1} = τ_{2n}. For each n let τ_{2n+2} = τ_{2n+1}^{⌢}⟨A(n)⟩. Finally let B = ⋃_{n} τ_{n}. By construction, the sequence ⟨τ_{n} | n ∈ ω⟩ is easily seen to be recursive in each of the Turing oracles J_{e}(B) = B ⊕ W_{e}^{B} and B ⊕ 0′ and A ⊕ 0′. From this, the desired conclusions follow easily. □

We now use the Pseudojump Inversion Theorem to obtain an example of a B <_{T} 0′ such that B is almost everywhere dominating.

Theorem 6.7. There exists B <_{T} 0′ 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 >_{T} C and ≤_{LR} C. Applying the Pseudojump Inversion Theorem 6.6 to this operator, we see that for all A ≥_{T} 0′ there exists B <_{T} A such that A ≡_{T} B ⊕ 0′ and A ≤_{LR} B. (Then by Theorem 8.9 we necessarily have A′ ≤_{tt} B′.) In particular, letting A = 0′, we obtain B <_{T} 0′ such that 0′ ≤_{LR} B. (Then by Theorem 8.9 we necessarily have 0′′ ≤_{tt} B′.) By Theorem 5.7 B is almost everywhere dominating. □

Remark 6.8. In the example of Theorem 6.7, we have 0′ ⊕ B ≡_{T} 0′ ≤_{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′ ≤_{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 <_{T} A ≤_{T} 0′, we can find a C such that A ⊕ C ≡_{T} C′ ≡_{T} 0′.

Proof. See Posner/Robinson [24]. □

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 <_{T} 0′ and 0′ ≤_{LR} B. Relativizing the Join Theorem 6.9 to B and letting A = 0′, we obtain C such that B ≤_{T} C and 0′ ⊕ C ≡_{T} C′ ≡_{T} B′. We then have 0′ ≤_{LR} B ≤_{T} C, hence 0′ ≤_{LR} C. (It follows that C′ ≤_{T} 0′′ and 0′′ ≤_{tt} C′.) By Theorem 5.7 C is almost everywhere dominating. We claim that 0′ ⊕ C ≰_{LR} C, i.e., 0′ is not low-for-random relative to C. To see this, note that 0′ ⊕ C ≤_{LR} C would imply (0′ ⊕ C)′ ≤_{T} C′ (see Theorem 8.8) which would imply C′′ ≤_{T} C′, a contradiction. □

7 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 Π_{1}^{0,A} set includes a Σ_{2}^{0,B} set of the same measure, then A ≤_{LR} B and A ≤_{T} B′.

To see this, assume the conclusion of Theorem 5.13, i.e., every Π_{1}^{0,A} set includes a Σ_{2}^{0,B} set of the same measure. Then A ≤_{LR} B in view of Theorem 4.6. It remains to prove A ≤_{T} B′. Consider the Σ_{1}^{0,A} set U = ⋃_{n∈A} O_{n} where

O_{n} = \{X ∈ 2^{ω} | ⟨\underbrace{0, …, 0}_{n}, 1⟩ ⊂ X\} .

Note that μ(U) = ∑_{n∈A} 1/2^{n+1}. Our assumption implies that U ⊆ Q for some Π_{2}^{0,B} set Q such that μ(U) = μ(Q). Write Q = ⋂_{k} V_{k} where V_{k} is uniformly Σ_{1}^{0,B}. Then n ∈ A if and only if O_{n} ⊆ Q, if and only if ∀k (O_{n} ⊆ V_{k}), if and only if ∀k ∃s (O_{n} ⊆ V_{k,s}). Thus A is Π_{2}^{0,B}. Similarly we can show that \overline{A} = ω \ A is Π_{2}^{0,B}. Thus A is Δ_{2}^{0,B}, i.e., A ≤_{T} B′, Q.E.D.

Remark 7.2. The hypothesis A ≤_{T} B′ cannot be dropped from Theorem 5.13. To see this, recall from Remark 4.4 that there exists a B such that A ≤_{LR} B for uncountably many A. In particular, there are uncountably many A such that A ≤_{LR} B yet A ≰_{T} B′. 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 ⊕ B ≤_{LR} B, i.e., A is low-for-random relative to B. Then every Π_{1}^{0,A⊕B} subset of 2^{ω} includes a Σ_{2}^{0,B} 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 ⊕ B ≤_{LR} B then A ⊕ B ≤_{T} B′.

Proof. Assume A ⊕ B ≤_{LR} B. By Theorem 10.10 we have A ⊕ B ≤_{LK} B, i.e., K^{B}(τ) ≤ K^{A⊕B}(τ) + O(1). From this it follows easily that K^{B}(A ↾ n) ≤ 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 Δ_{2}^{0,B}, i.e., A ≤_{T} B′, hence A ⊕ B ≤_{T} B′. □

Theorem 7.3 is now immediate from Theorem 5.13 plus Lemma 7.4. □

Remark 7.5. Comparison of Theorems 5.13 and 7.3 suggests the following question. If A ≤_{LR} B and A ≤_{T} B′, does it follow that A ⊕ B ≤_{LR} B? The answer to this question is negative. Indeed, letting C be as in Theorem 6.10, we have 0′ ≤_{LR} C and 0′′ ≤_{tt} C′ yet 0′ ⊕ C ≰_{LR} C.

Question 7.6. If A ≤_{LR} B and (A⊕B)′ ≤_{tt} B′, does it follow that A⊕B ≤_{LR} B? (Compare Theorem 8.9 below.)

8 Superhighness

In this section we present some new results concerning the relationship between LR-reducibility and truth-table reducibility.

Remark 8.1. Recall from Rogers [25, Chapters 8 and 9] the notion of truthtable reducibility, denoted ≤_{tt}. A result of Nerode (see Rogers [25, Chapter 9, Theorem XIX]) says that for all A, B ∈ 2^{ω}, A ≤_{tt} B if and only if A = Φ(B) for some total recursive functional Φ : 2^{ω} → 2^{ω}. 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′′ ≤_{T} B′, i.e., 0′′ is Turing reducible to B′. We say that superhigh if 0′′ ≤_{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 ψ^{A}(n) there exist recursive functions f(n) and g(n) such that ∀n (ψ^{A}(n)↓ ⇒ ψ^{A}(n) ∈ W_{f(n)}^{B}) and ∀n (|W_{f(n)}^{B}| ≤ g(n)).

2. We say that A is weakly jump-traceable by B if for each partial A-recursive function ψ^{A}(n) there exists a recursive function f(n) such that ∀n (ψ^{A}(n) ↓ ⇒ ψ^{A}(n) ∈ W_{f(n)}^{B}) and ∀n (W_{f(n)}^{B} is finite).

Lemma 8.4. If A ≤_{LR} B then A is jump-traceable by B.

Proof. Consider the A-r.e. set I = {(n, m) | ψ^{A}(n) ≃ m}. We have

∑_{(n,m)∈I} 1/2^{n} = ∑_{n∈dom(ψ^{A})} 1/2^{n} ≤ 2 < ∞.

By Lemma 5.11 let J ⊇ I be B-r.e. such that ∑_{(n,m)∈J} 1/2^{n} < ∞, say

∑_{(n,m)∈J} 1/2^{n} ≤ 2^{c}.

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

W_{f(n)}^{B} = {m | (n, m) ∈ 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. □

Lemma 8.5. If A is weakly jump-traceable by B, then A′ ≤_{T} A ⊕ B′.

Proof. Consider the partial A-recursive function ψ^{A}(e) ≃ least s such that φ_{e,s}^{(1),A}(e) ↓. Note that A′ = dom(ψ^{A}). By weak jump-traceability, let f(e) be recursive such that ∀e (ψ^{A}(e) ↓ ⇒ ψ^{A}(e) ∈ W_{f(e)}^{B}) and ∀e (W_{f(e)}^{B} is finite). Consider the total function h(e) = max(W_{f(e)}^{B}∪{0}). Note that h(e) is recursive

relative to B′, and e ∈ A′ if and only if φ_{e,h(e)}^{(1),A}(e) ↓. Thus A′ ≤_{T} A ⊕ B′. □

Lemma 8.6. If A is jump-traceable by B and B-r.e., then A′ ≤_{tt} B′.

Proof. Since A is B-r.e., let A = ⋃_{s} A_{s} where A_{s}, s = 0, 1, … is a B-recursive sequence of finite sets with A_{0} ⊆ A_{1} ⊆ ⋯ ⊆ A_{s} ⊆ A_{s+1} ⊆ · · ·. We identify the sets A and A_{s} with their characteristic functions. Consider the partial Arecursive function θ^{A}(e) ≃ the least σ ⊂ A such that φ_{e,|σ|}^{(1),σ}(e) ↓. Clearly A′ = dom(θ^{A}) = {e | θ^{A}(e) ↓}. By jump-traceability let f(e) and g(e) be recursive functions such that ∀e (θ^{A}(e) ↓ ⇒ θ^{A}(e) ∈ W_{f(e)}^{B}) and ∀e (|W_{f(e)}^{B}| ≤ g(e)). We

may safely assume that each σ ∈ W_{f(e)}^{B} satisfies φ_{e,|σ|}^{(1),σ}(e) ↓. For all e and all i < g(e) let σ_{e,i} ≃ the ith member of W_{f(e)}^{B} 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 ∃s (σ_{e,i} ↓ ⊂ A_{s}) and whether ∃s ∃t (s < t and σ_{e,i} ↓ ⊂ A_{s} and σ_{e,i} ⊄ A_{t}). Upon receiving the answers to these 2g(e)-many questions, we know the finite set F_{e} = {i < g(e) | σ_{e,i} ↓ ⊂ A}. Then e ∈ A′ if and only if F_{e} is nonempty. Thus A′ ≤_{tt} B′, Q.E.D. □

Remark 8.7. In the proof of Lemma 8.6 we have φ_{e}^{(1),A}(e) ≃ φ_{e,|σ_{e,i}|}^{(1),σ_{e,i}}(e) for any i ∈ F_{e}. Thus we see that, under the hypotheses of Lemma 8.6, the function

h^{A}(e) = \{ \begin{matrix}φ_{e}^{(1),A}(e) + 1 & if φ_{e}^{(1),A}(e) ↓, \\ 0 & otherwise \end{matrix}

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′ ≤_{tt} B′ and A jump-traceable by B. However, it is equivalent to their conjunction if A ≥_{T} B, and it is equivalent to each of them individually if A ≥_{T} B and A is B-r.e.

Theorem 8.8. If A ≤_{LR} B then A′ ≤_{T} A ⊕ B′.

Proof. This is immediate from Lemmas 8.4 and 8.5. □

Theorem 8.9. If A ≤_{LR} B and A is B-r.e., then A′ ≤_{tt} B′.

Proof. This is immediate from Lemmas 8.4 and 8.6. □

Theorem 8.10. If 0′ ≤_{LR} B then 0′′ ≤_{tt} B′.

Proof. This is the special case A = 0′ of Theorem 8.9. □

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. □

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 ≤_{LR} 0 then A is superlow, i.e., A′ ≤_{tt} 0′ (see Nies [21, Corollary 7.6]). Relativizing the arguments of Nies to a Turing oracle B, one can show that if A ⊕ B ≤_{LR} B then (A ⊕ B)′ ≤_{tt} B′. (See also Remark 10.12 below.) In particular, if 0′ ⊕ B ≤_{LR} B then 0′′ ≤_{tt} B′. Our Theorem 8.10 improves this by weakening the hypothesis 0′⊕B ≤_{LR} B to 0′ ≤_{LR} B. In addition, Nies [21, paragraph preceding Proposition 8.3] announced that if A and B are r.e. and A ≤_{LR} B then A′ ≤_{tt} B′. Our Theorem 8.9 improves this by eliminating the hypothesis that B is r.e.

Question 8.13. If A ≤_{LR} B and A ≤_{T} 0′, does it follow that A′ ≤_{tt} B′?

9 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) ≡_{T} 0′.

Proof. See Jockusch/Shore [12, Theorem 3.1]. □

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.

≤_{T} 0  ≥_{T} 0′
low  high
superlow  superhigh
≤_{LR} 0  ≥_{LR} 0′
low-for-random  a. e. dominating

Table 1: Duality

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 <_{T} 0′ and almost everywhere dominating.

Proof. In Theorem 6.1 we have constructed an r.e. set A which is >_{T} 0 and ≤_{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 >_{T} C and ≤_{LR} C. Applying the Duality Theorem 9.1 to this operator, we obtain an r.e. set B which is <_{T} 0′ and ≥_{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]. □

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. □

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)′ ≤_{tt} C′ and J_{e}(C) ≰_{LR} C. Applying the Duality Theorem 9.1, we obtain an r.e. set B such that 0′′ ≤_{tt} B′ and 0′ ≰_{LR} B. It follows by Theorem 5.7 that B is superhigh and not almost everywhere dominating. □

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]). □

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 ≤_{T} C′ and ≰_{tt} C′. Applying the Duality Theorem 9.1, we obtain an r.e. set B such that 0′′ is ≤_{T} B′ and ≰_{tt} B′. In other words, B is high and not superhigh. □

10 Prefix-free Kolmogorov complexity

In our exposition of Martin-Löf randomness and LR-reducibility in Sections 3 through 8 above, we have followed the effective measure-theoretic and descriptive set-theoretic approach due to Kučera [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, … such that ∑_{i=0}^{∞} 1/2^{m_{i}} ≤ 1, we can effectively find a recursive, one-to-one, prefixfree sequence of strings σ_{i}, i = 0, 1, … such that |σ_{i}| = m_{i} for all i.

Proof. Assume inductively that we have chosen σ_{i}, 0 ≤ 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} = {⟨⟩} and assume inductively that D_{k} has the following properties:

(a) D_{k} ∩ {σ_{i} | 0 ≤ i < k} = ∅.

(b) D_{k} ∪ {σ_{i} | 0 ≤ i < k} is a partition.

(c) The strings in D_{k} are all of different lengths. I.e., for all ρ, σ ∈ D_{k}, if ρ ≠ σ then |ρ| ≠ |σ|.

In fact we shall have a stronger property: ∀ρ, σ ∈ D_{k} (ρ <_{lex} σ ⇒ |ρ| > |σ|), where <_{lex} denotes the lexicographical order.

We claim that m_{k} ≥ min{|ρ| | ρ ∈ D_{k}}.

Otherwise m_{k} < min{|ρ| | ρ ∈ D_{k}}, hence by (c) we have

\frac{1}{2^{m_{k}}} > ∑_{ρ∈D_{k}} \frac{1}{2^{|ρ|}} ,

hence by (b) we have

∑_{i=0}^{k} \frac{1}{2^{m_{i}}} = \frac{1}{2^{m_{k}}} + ∑_{i=0}^{k−1} \frac{1}{2^{m_{i}}} > ∑_{ρ∈D_{k}} \frac{1}{2^{|ρ|}} + ∑_{i=0}^{k−1} \frac{1}{2^{|σ_{i}|}} = 1 ,

a contradiction.

By the above claim, let ρ_{k} ∈ D_{k} be such that |ρ_{k}| ≤ m_{k} and |ρ_{k}| is as large as possible. Let

σ_{k} = ρ_{k}^{⌢}⟨\underbrace{0, …, 0}_{m_{k}−|ρ_{k}|}⟩ .

Then |σ_{k}| = m_{k} and σ_{k} ⊈ σ_{i}, σ_{i} ⊈ σ_{k} for 0 ≤ i < k. Let

D_{k+1} = D_{k} \ \{ρ_{k}\} ∪ \{ρ_{k}^{⌢}⟨\underbrace{0, …, 0}_{j}, 1⟩ | 0 ≤ j < m_{k} − |ρ_{k}|\} .

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

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

dom(M) = {σ ∈ 2^{<ω} | M(σ) ↓}

is prefix-free.

If M is a prefix-free machine, then clearly ∑_{M(σ)↓} 1/2^{|σ|} ≤ 1, 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 ω × 2^{<ω} such that ∑_{(m,τ)∈L} 1/2^{m} ≤ 1. Then we can effectively find a prefix-free machine M such that for all (m, τ) ∈ L there exists σ such that |σ| = m and M(σ) ≃ τ.

Proof. Let (m_{i}, τ_{i}), i = 0, 1, … be a one-to-one recursive enumeration of L. By Lemma 10.1 let σ_{i}, i = 0, 1, … be a recursive, prefix-free sequence of strings such that |σ_{i}| = m_{i} for all i. Define M(σ_{i}) = τ_{i} for all i. □

Remark 10.4. In the Kraft/Chaitin Theorem 10.3, the pairs (m, τ) ∈ 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 ρ such that for all strings σ, M(σ) ≃ U(ρ^{⌢}σ). The prefix-free Kolmogorov complexity of a string τ is defined to be

K(τ) = min{|σ| | U(σ) ≃ τ}

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

K̂(τ) = min{|σ| | Û(σ) ≃ τ}

where Û is another universal prefix-free machine, then |K(τ) − K̂(τ)| ≤ O(1), i.e., ∃c ∀τ (|K(τ) − K̂(τ)| ≤ c).

Corollary 10.6. Let L be an r.e. subset of ω ×2^{<ω} such that ∑_{(m,τ)∈L} 1/2^{m} < ∞. Then for all (m, τ) ∈ L we have K(τ) ≤ m + O(1).

Proof. Let c be such that ∑_{(m,τ)∈L} 1/2^{m} ≤ 2^{c}. Then ∑_{(m,τ)∈L} 1/2^{m+c} ≤ 1, so by the Kraft/Chaitin Theorem 10.3 let M be a prefix-free machine such that for all (m, τ) ∈ L there exists σ such that |σ| = m + c and M(σ) = τ. Let ρ be such that M(σ) ≃ U(ρ^{⌢}σ) for all σ. Then for all (m, τ) ∈ L we have K(τ) ≤ m + c + |ρ|. This completes the proof. □

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 ∈ 2^{ω}, we have that X is random if and only if K(X ↾ n) ≥ n − O(1), i.e., ∃c ∀n (K(X ↾ n) ≥ n − c).

Proof. For c = 1, 2, … let V_{c} = {X | ∃n (K(X ↾ n) < n−c)}. Note that V_{c} ⊆ 2^{ω} is uniformly Σ_{1}^{0}. We claim that μ(V_{c}) < 1/2^{c}. To see this, for each τ such that K(τ) < |τ| − c choose σ such that U(σ) = τ and |σ| < |τ| − c. Here U is a universal prefix-free machine. By the Kraft Inequality we have

∑_{σ} \frac{1}{2^{|σ|}} ≤ 1

hence

μ(V_{c}) ≤ ∑_{τ} \frac{1}{2^{|τ|}} < ∑_{σ} \frac{1}{2^{|σ|+c}} ≤ \frac{1}{2^{c}}

thus proving the claim. We now see that V_{c}, c = 1, 2, … is a Martin-Löf test. Therefore, if X is random, we have ∃c (X ∉ V_{c}), i.e., ∃c ∀n (K(X ↾ n) ≥ n − c), i.e., K(X ↾ n) ≥ n − O(1). This is one direction of the theorem.

For the converse, assume X is not random, say X ∈ ⋂_{n} U_{n} where U_{n} ⊆ 2^{ω} is uniformly Σ_{1}^{0} and μ(U_{n}) ≤ 1/2^{n}, n = 1, 2, . . .. Let T_{n} be uniformly r.e. and prefix-free such that U_{n} = ⋃_{τ∈T_{n}} N_{τ}. We have

∑_{n} ∑_{τ∈T_{2n}} \frac{1}{2^{|τ|−n}} = ∑_{n} 2^{n}μ(U_{2n}) ≤ ∑_{n} \frac{2^{n}}{2^{2n}} = ∑_{n} \frac{1}{2^{n}} = 1 .

Hence by Corollary 10.6, K(τ) ≤ |τ| − n + O(1) for all n and all τ ∈ T_{2n}. Since X ∈ U_{2n} for all n, it follows that K(X ↾ n) ≱ n − O(1). □

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^{<ω} to 2^{<ω} such that dom(M) is prefix-free. We define K^{C}(τ) = min{|σ| | U^{C}(σ) ≃ τ} where U^{C} is a universal prefix-free Cmachine. The relativization of Schnorr’s Theorem says that X ∈ 2^{ω} is C-random if and only if K^{C}(X ↾ n) ≥ n − O(1).

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

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

1. A ≤_{LK} B.

2. A ≤_{LR} B.

3. For any A-r.e. set I ⊆ ω × ω such that ∑_{(m,n)∈I} 1/2^{m} < ∞, there exists a B-r.e. set J ⊇ I such that ∑_{(m,n)∈J} 1/2^{m} < ∞.

Proof. The implication 1 ⇒ 2 follows from Schnorr’s Theorem relativized to A and B. The implication 2 ⇒ 3 follows from Lemma 5.11. Now assume 3 and let I = {(m, τ) | K^{A}(τ) ≤ m}. Clearly I is A-r.e. and ∑_{(m,τ)∈I} 1/2^{m} < 2 < ∞, so let J ⊇ I be B-r.e. such that ∑_{(m,τ)∈J} 1/2^{m} < ∞. By Corollary 10.6 relative to B we have K^{B}(τ) ≤ m + O(1) for all (m, τ) ∈ J. Since I ⊆ J it follows that K^{B}(τ) ≤ K^{A}(τ) + O(1) for all τ. This proves 3 ⇒ 1. □

Remark 10.11. The reducibilities ≤_{LK} and ≤_{LR} were originally defined by Nies [21, Section 8]. In the direction of Theorem 10.10, Nies proved the equivalence A ≤_{LK} 0 ⟺ A ≤_{LR} 0 (see [21, Corollary 5.3]) and noted that A ≤_{LK} B implies A ≤_{LR} B. The full equivalence A ≤_{LK} B ⟺ A ≤_{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 ≤_{LR} for which no other proofs are presently known. Among these results are:

1. If A ≤_{LR} 0 and B ≤_{LR} 0 then A ⊕ B ≤_{LR} 0. (See Nies [21, Theorem 6.2] and Downey/Hirschfeldt/Nies/Stephan [9, Theorem 7.2].) More generally, if A ⊕ C ≤_{LR} C and B ⊕ C ≤_{LR} C then A ⊕ B ⊕ C ≤_{LR} C.

Caution: It is not in general true that if A ≤_{LR} C and B ≤_{LR} C then A ⊕ B ≤_{LR} C. Indeed, in Theorem 6.10 above we have constructed a C such that 0′ ≤_{LR} C yet 0′ ⊕ C ≰_{LR} C.

2. If A ≤_{LR} 0 then A ≤_{T} 0′, in fact A′ ≤_{tt} 0′ (see Nies [21, Corollary 7.6]). More generally, if A ⊕ B ≤_{LR} B then A ≤_{T} B′ (see Lemma 7.4 above), in fact (A ⊕ B)′ ≤_{tt} B′.

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

4. If A ≡_{LR} B then A⊕B ≤_{LR} A and A⊕B ≤_{LR} A (see Nies [21, Proposition 8.3(iii)]), hence A ≤_{T} B′ and B ≤_{T} A′, in fact A′ ≡_{tt} B′ ≡_{tt} (A ⊕ B)′.

In particular, for each B there are only countably many A such that A ≡_{LR} B.

Caution: By Miller/Yu [18, 19], there exists a B such that {A | A ≤_{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.

References

[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. VIII + 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. Proceedings of the London Mathematical Society, 85(3):869–888, 2012.

[15] Antonín Kučera. Measure, Π_{1}^{0} classes and complete extensions of PA. In [10], pages 245–259, 1985.

[16] Antonín Kučera 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. On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society, 360:3193–3210, 2008.

[19] Joseph S. Miller and Liang Yu. Oscillation in the initial segment complexity of random reals. Advances in Mathematics, 2010. Preprint, 24 pages, accepted for publication.

[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; Second Edition, Perspectives in Logic, Association for Symbolic Logic, Cambridge University Press, 2009, XVI+ 444 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.