Mass Problems and Almost Everywhere Domination

Stephen G. Simpson Pennsylvania State University

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

First draft: September 15, 2006 This draft: April 9, 2009

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

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

Accepted April 24, 2007 for Mathematical Logic Quarterly.

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

Abstract

We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the set of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let b_{1}, b_{2}, b_{3} be the degrees of unsolvability of the mass problems associated with the sets AED, MLR×AED, MLR∩AED respectively. Let P_{w} be the lattice of degrees of unsolvability of mass problems associated with nonempty Π_{1}^{0} subsets of 2^{ω}. Let 1 and 0 be the top and bottom elements of P_{w}. We show that inf(b_{1}, 1) and inf(b_{2}, 1) and inf(b_{3}, 1) belong to P_{w} and that 0 < inf(b_{1}, 1) < inf(b_{2}, 1) < inf(b_{3}, 1) < 1. Under the natural embedding of the recursively enumerable Turing degrees into P_{w}, we show that inf(b_{1}, 1) and inf(b_{3}, 1) but not inf(b_{2}, 1) are comparable with some recursively enumerable Turing degrees other than 0 and 0′. In order to make this paper more self-contained, we exposit the proofs of some recent theorems due to Hirschfeldt, Miller, Nies, and Stephan.

Contents

Abstract 1

Contents 2

1 Introduction 2

2 Some mass problem inequalities 3

3 Comparison with r.e. Turing degrees 6

4 A theorem of Hirschfeldt and Miller 7

5 A theorem of Nies 9

6 A theorem of Stephan 11

References 12

1 Introduction

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

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

In order to succinctly state our results, let MLR = {X ∈ 2^{ω} | X is Martin-Löf random} and AED = {Y ∈ 2^{ω} | Y is almost everywhere dominating}. For P, Q ⊆ 2^{ω} we write P × Q = {X ⊕ Y | X ∈ P and Y ∈ Q} and P ∩ Q = the intersection of P and Q. With these conventions, let b_{1}, b_{2}, b_{3} be the respective degrees of unsolvability of the mass problems associated with AED, MLR × AED, MLR ∩ AED. Trivially b_{1} ≤ b_{2} ≤ b_{3}. Our main results may be summarized by saying that the degrees inf(b_{1}, 1), inf(b_{2}, 1), inf(b_{3}, 1) belong to P_{w} and

0 < inf(b_{1}, 1) < inf(b_{2}, 1) < inf(b_{3}, 1) < 1.

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

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

Our work in this paper owes much to conversations with Bjørn Kjos-Hanssen, Antonín Kučera, and Joseph S. Miller. In particular, the fact that inf(b_{1}, 1) belongs to P_{w} was already implicit in Kjos-Hanssen [18], and Miller corrected an error in one of our early proofs of the inequality inf(b_{2}, 1) < inf(b_{3}, 1).

The reader who is familiar with the basics of recursion theory will find that this paper is largely self-contained. If E is an expression which may or may not denote a natural number, we write E ↓ to mean that E is defined (i.e., E denotes a natural number), otherwise E ↑. 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 defined and equal, or both undefined. Throughout this paper, a convenient background reference is our recent paper [33], which includes a fairly thorough exposition of almost everywhere domination and Martin-Löf randomness.

2 Some mass problem inequalities

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

Our notion of reducibility for decision problems is standard. Given X, Y ∈ 2^{ω}, we say that X is Turing reducible to Y, abbreviated X ≤_{T} Y, if X is computable using Y as an oracle. A Turing degree is an equivalence class of elements of 2^{ω} under mutual Turing reducibility. The Turing degree of X is denoted deg_{T} (X).

Our notion of reducibility for mass problems is as follows. Given P, Q ⊆ 2^{ω}, we say that P is weakly reducible to Q, abbreviated P ≤_{w} Q, if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of subsets of 2^{ω} under mutual weak reducibility. The weak degree of P is denoted deg_{w}(P). Weak degrees have sometimes been known as Muchnik degrees [23].

Note that for p = deg_{w}(P) and q = deg_{w}(Q) we have inf(p, q) = deg_{w}(P ∪ Q) and sup(p, q) = deg_{w}(P × Q). Note also that for X, Y ∈ 2^{ω} we have X ≤_{T} Y if and only if {X} ≤_{w} {Y }. Here {X} denotes the singleton set whose only element is X. Therefore, the Turing degree deg_{T} (X) is sometimes identified with the weak degree deg_{w}({X}).

Definition 2.1.

1. Let b_{1} = deg_{w}(AED) where

AED = {Y ∈ 2^{ω} | Y is almost everywhere dominating}.

2. Let b_{2} = deg_{w}(MLR × AED) where

MLR = {X ∈ 2^{ω} | X is Martin-Löf random}.

3. Let b_{3} = deg_{w}(MLR ∩ AED).

Theorem 2.2. The weak degrees inf(b_{1}, 1), inf(b_{2}, 1), inf(b_{3}, 1) belong to P_{w}.

Proof. An important tool in the study of P_{w} is the Embedding Lemma [34, Lemma 3.3], [32, Lemma 4]. The Embedding Lemma says: For any s = deg_{w}(S) where S is Σ_{3}^{0}, we have inf(s, 1) ∈ P_{w}. Therefore, in order to prove Theorem 2.2, it suffices to show that AED and MLR are Σ_{3}^{0}.

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

One way to see that AED is Σ_{3}^{0} is to use the characterization in terms of LK -reducibility. We know that B ∈ AED if and only if 0′ ≤_{LK} B, i.e., K^{B}(τ) ≤ K^{0′}(τ) + O(1), i.e., ∃c ∀τ (K^{B}(τ) ≤ K^{0′}(τ) + c). But K^{B}(τ) ≤ K^{0′}(τ) + c if and only if ∀ρ (U^{0′}(ρ) ≃ τ ⇒ ∃σ (|σ| ≤ |ρ| + c and U^{B}(σ) ≃ τ)). Here U^{B} is a universal prefix-free oracle machine. The last satement is Π_{2}^{0}, so AED is Σ_{3}^{0}. The fact that AED is Σ_{3}^{0} has previously been noted by Kjos-Hanssen [18] and Kjos-Hanssen/Miller/Solomon [19]. See also [33, Corollary 5.9].

It remains to show that MLR is Σ_{3}^{0}. In fact, MLR is Σ_{2}^{0} in view of the existence of a universal Martin-Löf test. See for instance [20] or [31, Theorem 8.3] or [33, Theorem 3.2]. This completes the proof of Theorem 2.2. □

Theorem 2.3. In P_{w} we have 0 < inf(b_{1}, 1) < inf(b_{2}, 1) < inf(b_{3}, 1) < 1.

Proof. Trivially b_{1} ≤ b_{2} ≤ b_{3}, hence inf(b_{1}, 1) ≤ inf(b_{2}, 1) ≤ inf(b_{3}, 1). Recall from [31, 34] that 1 = deg_{w}(PA) where

PA = {X ∈ 2^{ω} | X is a complete extension of Peano Arithmetic}.

We have 0 < inf(b_{1}, 1) because by [9] no member of AED ∪ PA is recursive. In order to prove inf(b_{1}, 1) < inf(b_{2}, 1), consider

DNR = {f ∈ ω^{ω} | f is diagonally nonrecursive}

where f is said to be diagonally nonrecursive if ∀n (f(n) ≄ φ_{n}^{(1)}(n)).

Lemma 2.4. DNR ≰_{w} AED.

Proof. This follows from items 1 and 2 in Lemma 2.7 below. □

The next two lemmas are well known.

Lemma 2.5. DNR ≤_{w} MLR.

Proof. Consider the recursive functional X ↦ f^{X} given by f^{X}(n) = ∑_{i=0}^{n−1} X(i)2^{i} for all X ∈ 2^{ω}. Let U_{n} = {X ∈ 2^{ω} | f^{X}(n) ≃ φ_{n}^{(1)}(n)}. Note that U_{n} is uniformly Σ_{1}^{0} and μ(U_{n}) ≤ 1/2^{n}. If X is random, it follows by Solovay’s Lemma (see for instance [33, Lemma 3.7]) that X ∈ U_{n} for only finitely many n. Therefore, with finitely many exceptions, f^{X} is diagonally nonrecursive. This proves the lemma. For refinements, see Jockusch [14, Proposition 3] and Ambos-Spies/Kjos-Hanssen/Lempp/Slaman [1] and Simpson [31]. □

Lemma 2.6. MLR ≤_{w} PA.

Proof. Since MLR is Σ_{2}^{0} and nonempty, we can find a nonempty Π_{1}^{0} set P ⊆ MLR. Since P is a nonempty Π_{1}^{0} subset of 2^{ω}, we have P ≤_{w} PA in view of Scott/Tennenbaum [30] and Scott [29]. The lemma follows. □

By Lemmas 2.4 and 2.5 and 2.6 we have MLR ∪ PA ≰_{w} AED. From this it follows trivially that AED ∪ PA <_{w} (MLR × AED) ∪ PA. In other words, inf(b_{1}, 1) < inf(b_{2}, 1).

Next we prove inf(b_{2}, 1) < inf(b_{3}, 1). We use the forcing construction of Cholak/Greenberg/Miller [5] referring to CGM-genericity.

Lemma 2.7 (Cholak/Greenberg/Miller).

1. If B is sufficiently CGM-generic, then B is almost everywhere dominating.

2. If B is sufficiently CGM-generic, then DNR ≰_{w} {B}.

3. For each nonrecursive A, if B is sufficiently CGM-generic then A ≰_{T} B.

Proof. See Cholak/Greenberg/Miller [5, Section 4]. □

We also use the following result due to Hirschfeldt and Miller, 2006.

Lemma 2.8 (Hirschfeldt/Miller). There is a nonrecursive, recursively enumerable set A such that {A} ≤_{w} MLR ∩ AED.

Proof. See Nies [25, Theorem 5.6]. Alternatively, see Section 4 below. □

The next lemma is well known.

Lemma 2.9.

1. If A ≰_{T} B, then μ({X ∈ 2^{ω} | A ≰_{T} X ⊕ B}) = 1.

2. If PA ≰_{w} {B}, then μ({X ∈ 2^{ω} | PA ≰_{w} {X ⊕ B}}) = 1.

Proof. The first statement is a relativized form of Sacks [28, Theorem 1, page 154]. The second statement is a relativized form of Jockusch/Soare [16, Theorem 5.3]. Both statements follow from the general “non-helping” result in [31, Lemma 7.3]. □

By Lemma 2.8 let A be nonrecursive such that {A} ≤_{w} MLR∩AED. Since A is nonrecursive, {A} ∪ DNR ≰_{w} AED by Lemma 2.7. Hence {A} ∪ PA ≰_{w} AED by Lemmas 2.5 and 2.6. But then, by Lemma 2.9, {A} ∪ PA ≰_{w} MLR × AED, since μ(MLR) = 1. It now follows by our choice of A that (MLR ∩ AED) ∪ PA ≰_{w} MLR × AED. From this it follows trivially that (MLR × AED) ∪ PA <_{w} (MLR ∩ AED) ∪ PA. In other words, inf(b_{2}, 1) < inf(b_{3}, 1).

It remains to prove inf(b_{3}, 1) < 1. We use the following results of Nies 2006 and Stephan 2002.

Lemma 2.10 (Nies). There exists B ∈ MLR ∩ AED such that 0′ ≰_{T} B.

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

Lemma 2.11 (Stephan). If B ∈ MLR and 0′ ≰_{T} B, then PA ≰_{w} {B}.

Proof. See Stephan [35]. Alternatively, see Section 6 below. □

By Lemma 2.10 let B ∈ MLR ∩ AED be such that 0′ ≰_{T} B. By Lemma 2.11 we have PA ≰_{w} {B}. Thus PA ≰_{w} MLR ∩ AED. It follows trivially that (MLR ∩ AED) ∪ PA <_{w} PA. In other words, inf(b_{3}, 1) < 1.

This completes the proof of Theorem 2.3. □

3 Comparison with r.e. Turing degrees

In this section we discuss the relationship between the weak degrees b_{1}, b_{2}, b_{3} and the recursively enumerable Turing degrees. Recall from [34, Theorem 5.5] that there is a natural one-to-one embedding of the recursively enumerable Turing degrees into P_{w} given by a ↦ inf(a, 1).

Theorem 3.1. There is no recursively enumerable Turing degree 0 < a < 0′ such that inf(a, 1) is comparable with inf(b_{2}, 1).

Proof. Let a = deg_{T} (A) where A is recursively enumerable and 0 <_{T} A <_{T} 0′. Since A is nonrecursive, we have {A} ∪ DNR ≰_{w} AED by Lemma 2.7, hence {A}∪PA ≰_{w} AED by Lemmas 2.5 and 2.6, hence {A}∪PA ≰_{w} MLR×AED by Lemma 2.9. From this it follows trivially that {A}∪PA ≰_{w} (MLR×AED)∪PA. In other words, inf(a, 1) ≰ inf(b_{2}, 1). On the other hand, since A is recursively enumerable and not Turing complete, we have DNR ≰_{w} {A} by the Arslanov Completeness Criterion [14], hence MLR ∪ PA ≰_{w} {A} by Lemmas 2.5 and 2.6. From this it follows trivially that (MLR × AED) ∪ PA ≰_{w} {A} ∪ PA. In other words, inf(b_{2}, 1) ≰ inf(a, 1). This completes the proof. □

Theorem 3.2. There are recursively enumerable Turing degrees 0 < a < 0′ and 0 < c < 0′ such that 0 < inf(a, 1) < inf(b_{3}, 1) < 1 and 0 < inf(b_{1}, 1) < inf(c, 1) < 1.

Proof. By Lemma 2.8 due to Hirschfeldt and Miller, let A >_{T} 0 be recursively enumerable such that {A} ≤_{w} MLR ∩ AED. By Simpson [33, Example 6.8] or Cholak/Greenberg/Miller [5, Theorem 2.1], let C <_{T} 0′ be recursively enumerable and almost everywhere dominating. Let a = deg_{T} (A) and c = deg_{T} (C). Clearly 0 < inf(a, 1) ≤ inf(b_{3}, 1) < 1 and 0 < a < 0′ and 0 < inf(b_{1}, 1) ≤ inf(c, 1) < 1 and 0 < c < 0′. By Theorems 2.3 and 3.1 it follows that inf(a, 1) < inf(b_{3}, 1) and inf(b_{1}, 1) < inf(c, 1). □

4 A theorem of Hirschfeldt and Miller

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

Theorem 4.1 (Hirschfeldt/Miller). Let S ⊆ 2^{ω} be Σ_{3}^{0} of measure 0. Then we can find a nonrecursive, recursively enumerable set A such that A ≤_{T} X for all random X ∈ S.

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

We first prove the theorem for Π_{2}^{0} sets. Let P ⊆ 2^{ω} be Π_{2}^{0} of measure 0. Write P = ⋂_{n} V_{n} where V_{n} is uniformly Σ_{1}^{0} and lim_{n} μ(V_{n}) = 0.

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

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

We claim that if W_{e} is infinite then W_{e} ∩ A ≠ ∅. To see this, fix n ∈ W_{e} so large that n > 2e and μ(V_{n}) < 1/2^{e}. Let s be such that n ∈ W_{e,s}. We have μ(V_{n,s}) < 1/2^{e}, so by construction W_{e,s} ∩ A_{s+1} ≠ ∅, Q.E.D.

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

We claim that A ≤_{T} X for all random X ∈ P. To see this, note that by construction

∑_{n∈A_{s+1}\A_{s}} μ(V_{n,s}) < ∑_{e} 1/2^{e} = 2 < ∞ .

Since X is random, it follows by Solovay’s Lemma (see [33, Lemma 3.7]) that X ∉ V_{n,s} for all but finitely many pairs n, s such that n ∈ A_{s+1} \ A_{s}. Let s_{0} be so large that (∀s > s_{0}) (∀n ∈ A_{s+1} \ A_{s}) (X ∉ V_{n,s}). Given n, since X ∈ V_{n} we can effectively find s > s_{0} such that X ∈ V_{n,s}. We then have n ∈ A ⟺ n ∈ A_{s}. Thus A ≤_{T} X, Q.E.D. This proves the theorem for Π_{2}^{0} sets.

Suppose now that S is Σ_{3}^{0} of measure 0. Write S = ⋃_{i} P_{i} where P_{i} is uniformly Π_{2}^{0}. Write P_{i} = ⋂_{n} V_{i,n} where V_{i,n} is uniformly Σ_{1}^{0} and lim_{n} μ(V_{i,n}) = 0 for each i. This implies that lim_{n} ∑_{i} μ(V_{i,n})/2^{i} = 0, so we can build A as before replacing μ(V_{n,s}) by ∑_{i} μ(V_{i,n,s})/2^{i}. The construction insures that

∑_{n∈A_{s+1}\A_{s}} ∑_{i} μ(V_{i,n,s})/2^{i} < ∑_{e} 1/2^{e} = 2 ,

hence for each i

∑_{n∈A_{s+1}\A_{s}} μ(V_{i,n,s}) < 2^{i+1} < ∞ ,

hence for any random X we have by Solovay’s Lemma X ∉ V_{i,n,s} for all but finitely many n, s such that n ∈ A_{s+1} \ A_{s}. It follows as before that A ≤_{T} X for all random X ∈ P_{i}. This proves the theorem. □

Remark 4.2. Hirschfeldt, Miller and Nies describe the proof of Theorem 4.1 as a “cost function” construction. In the case of a Π_{2}^{0} set, the cost of putting n into A at stage s is μ(V_{n,s}). In the case of a Σ_{3}^{0} set, the cost of putting n into A at stage s is ∑_{i} μ(V_{i,n,s})/2^{i}. The construction insures that the total cost of building A is finite, so that Solovay’s Lemma can be applied.

The following corollary is originally due to Kučera [21].

Corollary 4.3 (Kučera). Let X_{1}, …, X_{n} be random and ≤_{T} 0′. Then we can find a nonrecursive, recursively enumerable set A such that A ≤_{T} X_{i} for all i = 1, …, n.

Proof. Let S = {X_{1}, …, X_{n}} and apply Theorem 4.1. □

The following lemma is well known.

Lemma 4.4. μ({X ∈ 2^{ω} | X′ ≡_{T} X ⊕ 0′}) = 1.

Proof. It suffices to show that X′ ≡_{T} X ⊕ 0′ whenever X is random relative to 0′. (Generalizations of this result are in Kautz’s thesis [17, Theorem III.2.1].) Consider the sets U_{n} = {X ∈ 2^{ω} | n ∈ X′}. Obviously these sets are uniformly Σ_{1}^{0}. Let f(n) = least s such that μ(U_{n} \ U_{n,s}) ≤ 1/2^{n}. Note that f ≤_{T} 0′. Thus U_{n} \ U_{n,f(n)} is uniformly Σ_{1}^{0,0′} and these sets form a Solovay test relative to 0′. Now assume that X is random relative to 0′. By Solovay’s Lemma relative to 0′, we have X ∉ U_{n} \ U_{n,f(n)} for all but finitely many n. In other words, for all but finitely many n, n ∈ X′ if and only if X ∈ U_{n,f(n)}. Since f ≤_{T} 0′, it follows that X′ ≤_{T} X ⊕ 0′. This completes the proof. □

Theorem 4.5 (Hirschfeldt/Miller). We can find a nonrecursive, recursively enumerable set A such that A ≤_{T} X for all X such that X is random and almost everywhere dominating.

Proof. By Theorem 4.1 with S = AED, it suffices to show that AED is Σ_{3}^{0} and of measure 0. We have seen in the proof of Theorem 2.2 that AED is Σ_{3}^{0}. To show that μ(AED) = 0, recall from [19] and [33, Section 8] that AED ⊆ {X | X′ ≥_{T} 0′′}. Thus AED is disjoint from the intersection of two sets: {X | X′ ≡_{T} X ⊕0′} and {X | X ⊕ 0′ ≱_{T} 0′′}. The first set is of measure 1 by Lemma 4.4, and the second set is of measure 1 by Lemma 2.9. This completes the proof. □

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

5 A theorem of Nies

In this section we present a new proof of a theorem of Nies [26, Theorem VI.18] refining the Jockusch/Shore Pseudojump Inversion Theorem [15, Theorem 2.1]. By a pseudojump operator we mean an operator J_{e} : 2^{ω} → 2^{ω} given by J_{e}(X) = X ⊕ W_{e}^{X} for all X ∈ 2^{ω}.

Theorem 5.1 (Nies). Let P ⊆ 2^{ω} be Π_{1}^{0} of positive measure. For any pseudojump operator J_{e} and any Turing oracle A ≥_{T} 0′, we can find B ∈ P such that J_{e}(B) ≡_{T} B ⊕ 0′ ≡_{T} A.

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

Let us write Q_{e} = {X ∈ 2^{ω} | φ_{e}^{(1),X}(e) ↑}. Note that Q_{e}, e = 0, 1, 2, … is a standard, recursive enumeration of all Π_{1}^{0} subsets of 2^{ω}. Given a Π_{1}^{0} set Q ⊆ 2^{ω}, an index of Q is any integer e such that Q = Q_{e}. Let us say that a Π_{1}^{0} set P ⊆ 2^{ω} is rich if μ(P) > 0 and there exists a recursive function h such that for all e, if ∅ ≠ Q_{e} ⊆ P then μ(Q_{e}) ≥ 1/2^{h(e)}.

We claim that every Π_{1}^{0} set P ⊆ 2^{ω} of positive measure includes a Π_{1}^{0} set which is rich. To see this, let n be such that μ(P) > 1/2^{n}. Write Q_{e,s} = {X ∈ 2^{ω} | φ_{e,s}^{(1),X}(e) ↑} and note that Q_{e,s}, s = 0, 1, 2, … is a uniformly recursive descending sequence of clopen sets such that Q_{e} = ⋂_{s} Q_{e,s}. Define a recursive ascending sequence of clopen sets V_{s}, s = 0, 1, 2, … as follows. Begin with V_{0} = ∅. Given V_{s} define V_{s+1} = V_{s} ∪ ⋃_{e<s}(Q_{e,s} \ V_{s}) where the union is taken over all e < s such that μ(Q_{e,s} \ V_{s}) ≤ 1/2^{n+e+1}. Finally let P̃ = P \ V where V = ⋃_{s} V_{s}. Clearly P̃ is Π_{1}^{0}. Moreover μ(V) ≤ ∑_{e} 1/2^{n+e+1} = 1/2^{n}, hence μ(P̃) ≥ μ(P)−1/2^{n} > 0. If ∅ ≠ Q_{e} ⊆ P̃ then for all s > e we have μ(Q_{e,s}\V_{s}) > 1/2^{n+e+1}, hence μ(Q_{e}) ≥ 1/2^{n+e+1}. Thus P̃ is rich via h(e) = n + e + 1. This proves our claim.

To prove the theorem, let P ⊆ 2^{ω} be Π_{1}^{0} of positive measure. By our claim, we may safely assume that P is rich. Under this assumption we shall carry out the proof of the Pseudojump Inversion Theorem “within P ” to produce B ∈ P with the desired properties.

For strings σ ∈ 2^{<ω} let us write N_{σ} = {X ∈ 2^{ω} | σ ⊂ X}. For each string ρ ∈ 2^{<ω} we define a string f(ρ) ∈ 2^{<ω} and a nonempty Π_{1}^{0} set Q_{ρ} ⊆ P ∩ N_{f(ρ)}. Begin with f(⟨⟩) = ⟨⟩ and Q_{⟨⟩} = P. Assume inductively that f(ρ) and Q_{ρ} have already been defined.

In order to control the pseudojump J_{e}(B), define a string f^{∗}(ρ) ⊇ f(ρ) and a nonempty Π_{1}^{0} set Q_{ρ}^{∗} ⊆ Q_{ρ} ∩ N_{f^{∗}(ρ)} as follows. Let m = |ρ|. If ∃X (X ∈ Q_{ρ} and m ∉ W_{e}^{X}), let Q_{ρ}^{∗} = {X ∈ Q_{ρ} | m ∉ W_{e}^{X}} and let f^{∗}(ρ) = f(ρ). Otherwise, consider the least σ ⊇ f(ρ) such that Q_{ρ} ∩ N_{σ} ≠ ∅ and m ∈ W_{e}^{σ}, and let Q_{ρ}^{∗} = Q_{ρ} ∩ N_{σ} and f^{∗}(ρ) = σ. Thus f^{∗}(ρ) “decides” whether m ∈ W_{e}^{B} or not.

Because P is rich, given an index of Q_{ρ}^{∗} we can effectively find k such that μ(Q_{ρ}^{∗}) ≥ 1/2^{k}. But then there are at least two strings τ ⊃ f^{∗}(ρ) of length k + 1 such that Q_{ρ}^{∗} ∩ N_{τ} ≠ ∅. Let f(ρ^{⌢}⟨0⟩) and f(ρ^{⌢}⟨1⟩) be the lexicographically leftmost and rightmost such τ. Let Q_{ρ^{⌢}⟨0⟩} = Q_{ρ}^{∗} ∩ N_{f(ρ^{⌢}⟨0⟩)} and Q_{ρ^{⌢}⟨1⟩} = Q_{ρ}^{∗} ∩ N_{f(ρ^{⌢}⟨1⟩)}.

We have now defined f(ρ), f^{∗}(ρ), Q_{ρ}, Q_{ρ}^{∗} for all ρ. It is straightforward to check that f(ρ) and f^{∗}(ρ) and the indices of Q_{ρ} and Q_{ρ}^{∗} are uniformly computable from 0′.

Given A ∈ 2^{ω} let B = f(A) = ⋃_{m} f(A ↾ m). Then m ∈ W_{e}^{B} if and only if m ∈ W_{e}^{f^{∗}(A↾m)}. Moreover, it is straightforward to show that f(A ↾ m) and f^{∗}(A ↾ m) and the indices of Q_{A↾m} and Q_{A↾m}^{∗} are uniformly computable from 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. □

Theorem 5.2 (Nies). For any pseudojump operator J_{e} and any Turing oracle A ≥_{T} 0′, we can find a random B such that J_{e}(B) ≡_{T} B ⊕ 0′ ≡_{T} A.

Proof. In Theorem 5.1 let P be a nonempty Π_{1}^{0} set such that ∀X (X ∈ P ⇒ X is random). □

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

Corollary 5.4 (Nies). For any A ≥_{T} 0′ we can find a random B <_{T} A such that B ⊕ 0′ ≡_{T} A and A is low-for-random relative to B.

Proof. By Theorem 5.2, it suffices to produce a psuedojump operator J_{e} such that for all B, J_{e}(B) >_{T} B and J_{e}(B) is low-for-random relative to B. Such an operator is obtained by uniformly relativizing the Kučera/Terwijn [22] construction of a nonrecursive, recursively enumerable set which is low-for-random. See also the exposition in Simpson [33, Section 6]. □

Corollary 5.5 (Nies). We can find a random B <_{T} 0′ such that 0′ is low-for-random relative to B.

Proof. This is the special case of Corollary 5.4 in which we let A = 0′. □

Corollary 5.6 (Nies). There are uncountably many random B ≱_{T} 0′ such that 0′ is low-for-random relative to B.

Proof. This follows from Corollary 5.4 by considering uncountably many A >_{T} 0′. □

Corollary 5.7 (Nies). We can find a random B <_{T} 0′ which is almost everywhere dominating.

Corollary 5.8 (Nies). There are uncountably many random B ≱_{T} 0′ such that B is almost everywhere dominating.

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

6 A theorem of Stephan

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

Theorem 6.1 (Stephan). If B is random and 0′ ≰_{T} B, then PA ≰_{w} {B}.

Proof. We shall define a recursively bounded, partial recursive function ψ with the following property: For all random B, if B ≥_{T} some total function extending ψ then B ≥_{T} 0′. This suffices to prove the theorem, because clearly every {B} ≥_{w} PA computes a total extension of every recursively bounded, partial recursive function (see for instance [31, Theorem 4.10]).

Recall that 0′ is a recursively enumerable set. If n ∉ 0′ let ψ(⟨e, n⟩) be undefined for all e. If n ∈ 0′, say n ∈ 0′_{s+1} \ 0′_{s}, then for each i < 2^{n} compute the rational numbers

r_{e,n,i} = μ({X | φ_{e,s}^{(1),X}(⟨e, n⟩) ≃ i})

and define ψ(⟨e, n⟩) ≃ i chosen so as to minimize r_{e,n,i}. Note that ψ is partial recursive, and ψ(⟨e, n⟩) ↓ if and only if n ∈ 0′. Moreover, if ψ(⟨e, n⟩) ↓ then ψ(⟨e, n⟩) < 2^{n}, so ψ is recursively bounded. In addition μ(V_{e,n}) ≤ 1/2^{n} where

V_{e,n} = {X ∈ 2^{ω} | ∃s (n ∈ 0′_{s+1} \ 0′_{s} and φ_{e,s}^{(1),X}(⟨e, n⟩) ≃ ψ(⟨e, n⟩))}.

Assume now that B is random and computes a total extension of ψ. Let e be such that φ_{e}^{(1),B} is total and extends ψ. Define f(n) = least s such that φ_{e,s}^{(1),B}(⟨e, n⟩) ↓. Since φ_{e}^{(1),B} is total, f is total and ≤_{T} B. Since B is random, it follows by Solovay’s Lemma that B ∉ V_{e,n} for all but finitely many n. In other words, for all but finitely many n, if n ∈ 0′_{s+1} \0′_{s} then φ_{e,s}^{(1),B}(⟨e, n⟩) ≄ ψ(⟨e, n⟩). But then, since ψ(⟨e, n⟩) ↓ and φ_{e}^{(1),B} extends ψ, it follows that φ_{e,s}^{(1),B}(⟨e, n⟩) ↑, i.e., f(n) > s. We now see that, for all but finitely many n, if n ∈ 0′ then n ∈ 0′_{f(n)}. Thus 0′ ≤_{T} f ≤_{T} B. This completes the proof. □

Remark 6.2. A similar proof yields the following more detailed result. Given a recursively enumerable set A, we can find recursively enumerable sets A_{1} and A_{2} such that A_{1} ≡_{T} A_{2} ≡_{T} A and A_{1} ∩ A_{2} = ∅ and, for all random B, if (∃Z ≤_{T} B) (Z ⊇ A_{1} and Z ∩ A_{2} = ∅) then A ≤_{T} B.

References

[1] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman. Comparing DNR and WWKL. Journal of Symbolic Logic, 69:1089– 1104, 2004.

[2] Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, and David Reed Solomon. On a question of Dobrinen and Simpson concerning almost everywhere domination. Journal of Symbolic Logic, 71:119–136, 2006.

[3] Stephen Binns and Stephen G. Simpson. Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes. Archive for Mathematical Logic, 43:399– 414, 2004.

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

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

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

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

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

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

[10] H.-D. Ebbinghaus, G. H. Müller, and G. E. Sacks, editors. Recursion Theory Week. Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985. IX + 418 pages.

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

[12] J. Gruska, B. Rovan, and J. Wiedermann, editors. Mathematical Foundations of Computer Science. Number 233 in Lecture Notes in Computer Science. Springer-Verlag, 1986. IX + 650 pages.

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

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

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

[16] Carl G. Jockusch, Jr. and Robert I. Soare. Π_{1}^{0} classes and degrees of theories. Transactions of the American Mathematical Society, 173:35–56, 1972.

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

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

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

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

[21] Antonín Kučera. An alternative, priority-free, solution to Post’s problem. In [12], pages 493–500, 1986.

[22] Antonín Kučera and Sebastiaan A. Terwijn. Lowness for the class of random sets. Journal of Symbolic Logic, 64:1396–1402, 1999.

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

[24] André Nies. Lowness properties and randomness. Advances in Mathematics, 197:274–305, 2005.

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

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

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

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

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

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

[31] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005.

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

[33] Stephen G. Simpson. Almost everywhere domination and superhighness. Mathematical Logic Quarterly, 53:462–482, 2007.

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

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