# Almost everywhere domination and superhighness

Stephen G. Simpson

Pennsylvania State University

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

http://www.personal.psu.edu/t20/

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 , we say that is dominated by if for all but finitely many . We consider the standard fair coin'' probability measure on the space of infinite sequences of 0's and 1's. A Turing oracle is said to be almost everywhere dominating if, for measure one many , each function which is Turing computable from is dominated by some function which is Turing computable from . 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 -reducibility and almost everywhere domination. We also prove the following new result: If is almost everywhere dominating, then is superhigh, i.e., is truth-table computable from , the Turing jump of .

# 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 -triviality and low-for-randomness which are due to Downey, Hirschfeldt, Kucera, Nies, Stephan, and Terwijn [16,9,21,11]. The purpose of this paper is to update the Dobrinen/Simpson account of almost everywhere domination by expositing this subsequent research. We provide introductory accounts of Martin-Löf randomness, -reducibility, and prefix-free Kolmogorov complexity as they relate to almost everywhere domination. We also prove a new result: If is almost everywhere dominating, then is superhigh.

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

# Notation

We use standard recursion-theoretic notation and terminology from Rogers [25]. We write r.e. as an abbreviation for recursively enumerable''. If is a Turing oracle, we write -recursive for recursive relative to '', -r.e. for recursively enumerable relative to '', etc. We write to denote the set of natural numbers. We often identify Turing oracles with subsets of . If is an expression denoting a natural number which may or may not be defined, we write to mean that is defined, and to mean that is undefined. If and are two such expressions, we write to mean that and are both undefined or both defined with the same value. If is a Turing oracle, we write

the Turing jump of .
In particular a Turing oracle for the Halting Problem. For we write
,
the Turing join of and . We write to denote Turing reducibility. Thus means that is Turing computable from . For we write , the complement of . We sometimes identify with its characteristic function given by if , if .

We write to denote the Cantor space, i.e., the set of total functions . We write to denote the set of strings, i.e., finite sequences of 's and 's. For we write where the length of . The empty string, denoted , is the unique string of length . Given and , we have a string of length . For and , we write to mean that is a prefix of , i.e., . For , 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 and we write the concatenation, followed by . Thus if and only if for some .

Given , we write . Thus is a basic open neighborhood in the Cantor space. The fair-coin probability measure on is defined by . In particular . A set is said to be prefix-free if there are no such that . Note that if is prefix-free then .

We make extensive use of the relativized arithmetical hierarchy of subsets of . See Rogers [25, Section 15.1]. If is a Turing oracle, then by definition is if and only if for some -r.e. set . A well known fact is that for any such we can find such an which is prefix-free. By definition, is if and only if its complement is . Note that . Because is compact, a set is if and only if for some finite . This is the same as saying that is clopen, i.e., closed and open, in . Again, we may take to be prefix-free.

# Randomness

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

Definition 3.1 (Martin-Löf 1966)   Let be a Turing oracle. We say that is -random if for all uniformly sequences of sets , such that for all . Such a sequence is called a Martin-Löf test for -randomness.

Theorem 3.2 (Martin-Löf 1966, Kucera 1985)   We can construct a universal Martin-Löf test. In other words, we can find uniformly sets , such that and, for all and all Turing oracles , is -random if and only if .

Proof.Let , be a standard, uniform enumeration of all subsets of . For let be the set of which get into by means of a computation in steps using only oracle information from . Thus , is a uniformly -recursive sequence of clopen sets, and . For rational numbers let

Intuitively, is just enumerated so long as its measure is . Note that is uniformly , and , and if and only if . Now for all let if , and if . Again is uniformly . Moreover, for each , the sequence , is a Martin-Löf test, and all Martin-Löf tests occur in this way. Finally let . Then is uniformly , and for all , so , is a Martin-Löf test. Moreover, for an arbitrary Martin-Löf test , , we have . Thus , is a universal Martin-Löf test.

Corollary 3.3 (Kucera 1985)   For any Turing oracle , the set
is -random
is uniformly and of measure .

Proof.By Theorem 3.2 let , be a universal Martin-Löf test for -randomness. Then . Moreover is uniformly , hence is uniformly , hence is uniformly . Also for all , hence , hence .

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

Lemma 3.4   Assume that is random. Then is -random, and is -random. In particular, and are random.

Proof.Suppose for instance that is not -random. Then where is uniformly of measure . Let and note that is uniformly of measure . We have , contradicting the assumption that is random.

Lemma 3.5 (Solovay's Lemma)   Assume is random. Let , be uniformly such that . Then , i.e., is finite.

Proof.For each let . Let be such that . We claim that . To see this, let and note that . For all we have

so for all . It follows that , and our claim is proved. Since is random and is uniformly , we have , hence for some , hence . This proves the lemma.

Theorem 3.6 (van Lambalgen's Theorem)   is random if and only if is random and is -random.

Proof.The only if'' direction follows from Lemma 3.4. For the if'' direction, assume that is not random. We have where is uniformly with . By passing to a subsequence, we may assume that . Let and note that is uniformly . Moreover for all , because otherwise we would have

a contradiction. Since is random, it follows by Lemma 3.5 that is finite. Thus for all but finitely many we have , i.e., . Let . Then for all but finitely many , and is uniformly . Moreover , contradicting the assumption that is -random.

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

Lemma 3.7   Let be of positive measure. Then for all there exists such that and .

Proof.Claim: If where , then there are at least two strings such that and .

To prove the claim, note first that , hence since . If the conclusion of the claim were false, we would have

contradicting the hypothesis of the claim.

To prove Lemma 3.7, assume that is with , say where . Note that , hence . Applying our claim repeatedly, define as follows. Let . Suppose inductively that has already been defined. Let where . Let (respectively ) be the lexicographically leftmost (respectively rightmost) such that and . Our claim implies that and exist and are incompatible. It is straightforward to check that .

Given , let . Clearly and . We claim that . To prove this, we describe how to compute using an oracle for . Let where is a recursive sequence of clopen sets. Suppose we have already computed . We also have if , or if . Our construction implies that is either the leftmost or the rightmost of length such that . Therefore, for all sufficiently large stages , we will have for all of length lying to the left (respectively right) of . When such a stage is reached, then at that point we see that (respectively ). This completes the proof.

Theorem 3.8 (Kucera/Gács Theorem)   For any we can find a random such that .

Proof.By Corollary 3.3 let be of positive measure such that is random. Applying Lemma 3.7 to any , we obtain such that .

Corollary 3.9   Assume that is random and and is -random and . Then is -random.

Proof.Since , we may assume by the Kucera/Gács Theorem that is random. Since is -random and is random, it follows by van Lambalgen's Theorem that is random, hence is -random. Since , it follows that is -random. Now, since is random, it follows that is random, hence is -random.

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

Theorem 3.10 (Miller/Yu 2004)   If is random and where is -random, then is -random.

# -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 and be Turing oracles. We say that is -reducible to , abbreviated , if
is -random is -random.

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

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

However, caution is required, because in general is not equivalent to being low-for-random relative to . In Section 6 we shall construct a Turing oracle such that yet is not low-for-random relative to . We shall also see that the binary relation  is low-for-random relative to '' is not transitive. Indeed, we shall construct Turing oracles and such that , hence is low-for-random relative to and is low-for-random relative to , yet is not low-for-random relative to . See Theorem 6.10.

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

Remark 4.5   On the other hand, consider the equivalence relation defined by letting if and only if and . It can be shown (see Remark 10.12) that if then is low-for-random relative to and is low-for-random relative to . It follows that each -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. .
2. Each set of positive measure includes a set of positive measure.
3. There exists a set such that is -random and includes a set of positive measure.
4. There exists a set of positive measure such that is -random.

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

Lemma 4.7   Fix a Turing oracle , and let be . The following statements are pairwise equivalent.
(a)
is of positive measure.
(b)
and is nonempty and is -random.
(c)
and is -random.

Proof.By Corollary 3.3, is -random is and of measure 1. From this it follows easily that (a) (b). Trivially (b) (c). In order to prove (c) (a), assume . We have where is a -recursive sequence of clopen sets. Hence . Let where least such that . Then , is a Martin-Löf test for -randomness, and . Hence no is -random, Q.E.D.

Lemma 4.8   Assume that is such that is -random. Then 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 Kucera [15].

Definition 4.9 (Kucera 1985)   Let be . We define a product operation. Let and where are -r.e. and prefix-free. We define the product

Note that is again -r.e. and prefix-free. Note also that:
(a)
is .
(b)
Given indices of and qua sets, we can compute an index of qua set.
(c)
.
(d)
.
(e)
The product is associative, i.e., .

Definition 4.10 (Kucera 1985)   Dually, let be . We define the product , where . Note that:
(a)
is .
(b)
Given indices of and qua sets, we can compute an index of qua set.
(c)
.
(d)
.
(e)
The product is associative, i.e., .

We now begin the proof of Theorem 4.6. Let us say that is fat if it includes a set of positive measure. The implication of Theorem 4.6 may be rephrased as follows:

If , then every set of positive measure is fat.
Our proof of this statement will use the following lemma.

Lemma 4.11 (Kjos-Hanssen 2005)   Let be . If is fat, then at least one of and is fat.

Proof.Let . Then is , say where is -r.e. and prefix-free. We have where . Suppose now that is fat, say where is and . By Lemmas 4.7 and 4.8 we may safely assume that is -random, hence . If then is fat and we are done. Otherwise there exists such that , hence . But , hence is fat, hence is fat, Q.E.D.

We now prove the implication of Theorem 4.6. Assume and suppose that is of positive measure. We must show that is fat.

Let , so . Let be such that . Let ( times) and ( times). Note that . We have , hence , is a Martin-Löf test for -randomness. It follows that is not -random.

By Lemma 4.7 let be nonempty such that is -random. By Lemma 4.8 we have .

We claim that and . Otherwise we would have . Therefore, since is , we would be able to find such that and for all . Setting we would have and . Thus would be -random but not -random, contradicting our assumption . This proves our claim.

Let and be as in our claim. We then have , hence is fat. It follows by Lemma 4.11 that is fat. This completes the proof of .

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

Lemma 4.12 (Kucera 1985)   Let be of positive measure. Then for all -random there exist and such that and .

Proof.Suppose is of positive measure. As before let where is -r.e. and prefix-free. Define and as before. Suppose is -random. Since , is a Martin-Löf test for -randomness, we have for some . Choosing the least such , we have , i.e., for some and . Letting we have , Q.E.D.

We now prove . Assuming 4, let be of positive measure such that is -random. To prove 1, suppose is -random. Applying Lemma 4.12 with and in place of and , we have for some . It follows that is -random. Hence is -random. Thus , Q.E.D.

This completes the proof of Theorem 4.6.

Corollary 4.13 (Kjos-Hanssen 2005)   The binary relation is .

Proof.Let , be a standard, uniform enumeration of all subsets of , where is a Turing oracle. Fix such that for all , is of positive measure1 and is -random. By Theorem 4.6, is equivalent to and . A Tarski/Kuratowski computation (see Rogers [25, Section 14.3]) shows that this is .

Similarly one can prove:

Corollary 4.14 (Kjos-Hanssen 2005)   The ternary relation is . More generally, for each the -ary relation is .

Remark 4.15   Earlier Nies had proved that is . Another interesting result due to Nies and Hirschfeldt (see Remark 10.12 below) is that if and then . Thus is a Turing ideal. See Nies [21, Theorems 6.2 and 7.9].

# Almost everywhere domination

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

Definition 5.1 (Dobrinen/Simpson 2003)
1. Let be total functions. We say that is dominated by if for all but finitely many .
2. We say that is almost everywhere dominating if, for measure 1 many , each -recursive function is dominated by some -recursive function.
3. We say that is uniformly almost everywhere dominating if there is a fixed -recursive function which dominates all -recursive functions for measure 1 many .

Theorem 5.2 (Dobrinen/Simpson 2003)   The following statements are pairwise equivalent.
1. is uniformly almost everywhere dominating.
2. Every subset of includes a set of the same measure.
3. Every subset of includes a 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. is almost everywhere dominating.
2. Given a set , and given , we can find a set such that .
3. Given a set , and given , we can find a set such that .

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 is positive-measure dominating if every subset of of positive measure includes a set of positive measure. Equivalently, every subset of of positive measure includes a set of positive measure.

We then have:

Theorem 5.5 (Kjos-Hanssen 2005)   is positive-measure dominating if and only if .

Proof.This is immediate from the special case of Theorem 4.6.

Corollary 5.6 (Kjos-Hanssen 2005)   The set
is positive-measure dominating
is .

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 are pairwise equivalent.
1. is uniformly almost everywhere dominating.
2. is almost everywhere dominating.
3. is positive-measure dominating.
4. .

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
is almost everywhere dominating
and
is uniformly almost everywhere dominating
are . In fact, .

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 subsets of . 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 . Let be recursive. For all -r.e. sets such that , there exists a -r.e. set such that .

Proof.We use the following fact from analysis. Given , , we have

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

To prove our lemma, let be as in the hypotheses of the lemma. We may safely assume that for all . Let

and
where . Note that the 's are mutually independent and clopen and . Consider the set . By hypothesis , hence
.
Let be such that . Let . Clearly and is -r.e. Moreover , hence
,
hence , Q.E.D.

Remark 5.12   Under the same hypothesis, , we can obtain the following stronger conclusion. Given a recursive sequence of recursive real numbers , , and given an -r.e. set such that , we can effectively find a -r.e. set such that .

Theorem 5.13 (Kjos-Hanssen/Miller/Solomon 2006)
Assume and . Then every subset of includes a set of the same measure.

Proof.Assume and . We must show that every set includes a set of the same measure. Equivalently, we shall show that every set is included a set of the same measure.

Let be . Write

where is -r.e. and prefix-free. Let
with use .
Thus . Clearly is -r.e. and
.
By Lemma 5.11 let be -r.e. such that .

We may safely assume that . Since , let be a -recursive approximation of . Let

where
with use .
Clearly is . Moreover , hence .

Claim 1: .

To see this, suppose . Then either (1) , or (2) but is not in with use . In case (1) we have for all sufficiently large , hence . In case (2) we have for all sufficiently large , hence is not in with use , hence again , proving our claim.

Claim 2: .

To see this, fix . Let be a finite subset of such that . Let be so large that, for all , if then . Then

proving our claim.

This completes the proof of Theorem 5.13.

Remark 5.14   Theorem 5.7 is just the special case of Theorem 5.13 in light of Theorems 5.2, 5.3, 5.5.

# Some examples

We have seen in Theorem 5.3 that every Turing oracle is almost everywhere dominating. In this section we construct a which is almost everywhere dominating. Such examples were first given by Cholak/Greenberg/Miller [5]. We also construct a such that yet is not low-for-random relative to .

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

Theorem 6.1 (Kucera/Terwijn 1997)   We can find a nonrecursive r.e. set such that , i.e., is low-for-random.

Proof.By Corollary 3.3 we know that is random is and of measure 1. Therefore, we can find a set such that and is random. By uniformly relativizing the construction of to an arbitrary Turing oracle , we obtain2 a set such that and is -random. For let . Note that is uniformly and .

To prove the theorem, we shall build a nonrecursive r.e. set and a set such that . Letting , it will follow that is a subset of of positive measure. Hence by Theorem 4.6 , Q.E.D.

It remains to build and as specified.

We first establish some notation. Let , be a recursive enumeration of the r.e. subsets of . Let be the set of which get into by means of a computation in steps. Thus . Let be the set of which get into by means of a computation in steps using only oracle information from . Thus , is a uniformly -recursive sequence of clopen sets in , and .

Our r.e. set will be constructed as where is a recursive sequence of finite sets. Let . Clearly and is . Our construction of will insure that . Since , we shall have as desired.

Note that , is a recursive sequence of clopen sets in . Let . Then , is a recursive, pairwise disjoint sequence of clopen sets in , and .

Our construction of is as follows. At stage 0 let . At stage , for each such that , look for such that and and put the least such into .

Finally let . Clearly is r.e. By construction, for each at most one is put into for the sake of . Therefore, our condition insures that is infinite.

Lemma 6.2   For each , if is infinite then .

Proof.Since the 's are pairwise disjoint, we have . Assume that is infinite. Let be so large that and . Let be so large that . Then by construction .

Since is infinite, it follows that is nonrecursive. (Actually, 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 .

Proof.Given , let be such that . Then , hence . In other words, at some stage , some is put into for the sake of for some . For this particular , the set of such 's is , hence of measure . Hence the set of all such 's is of measure .

This completes the proof of Theorem 6.1.

We now present the Pseudojump Inversion Theorem.

Definition 6.4   For an arbitrary Turing oracle , let , be a standard, uniform enumeration of all -r.e. subsets of . For each fixed , the operator given by is called a pseudojump operator or an -operator. (The acronym REA stands for r.e. and above''.)

Remark 6.5   Note that the Turing jump operator 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 and any , we can find a such that .

Proof.For and , we write to denote the set of which get into by means of a computation in steps using only oracle information from . Note that . We also write where .

Given , our construction of is as follows. We define a sequence of strings , . Let . For each , given , if there exists such that , let be the least such . Otherwise let . For each let . Finally let . By construction, the sequence is easily seen to be recursive in each of the Turing oracles and and . From this, the desired conclusions follow easily.

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

Theorem 6.7   There exists such that is almost everywhere dominating.

Proof.By uniformly relativizing Theorem 6.1 to an arbitrary Turing oracle , we obtain a pseudojump operator such that for all , is and . Applying the Pseudojump Inversion Theorem 6.6 to this operator, we see that for all there exists such that and . (Then by Theorem 8.9 we necessarily have .) In particular, letting , we obtain such that . (Then by Theorem 8.9 we necessarily have .) By Theorem 5.7 is almost everywhere dominating.

Remark 6.8   In the example of Theorem 6.7, we have , hence is low-for-random relative to . We now use the Join Theorem of Posner/Robinson [24] to obtain a different kind of example, namely a such that , hence is almost everywhere dominating, yet is not low-for-random relative to .

Theorem 6.9 (Join Theorem)   Given such that , we can find a such that .

Proof.See Posner/Robinson [24].

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

Proof.Let be as in Theorem 6.7, i.e., and . Relativizing the Join Theorem 6.9 to and letting , we obtain such that and . We then have , hence . (It follows that and .) By Theorem 5.7 is almost everywhere dominating. We claim that , i.e., is not low-for-random relative to . To see this, note that would imply (see Theorem 8.8) which would imply , a contradiction.

# 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 set includes a set of the same measure, then and .

To see this, assume the conclusion of Theorem 5.13, i.e., every set includes a set of the same measure. Then in view of Theorem 4.6. It remains to prove . Consider the set where

Note that . Our assumption implies that for some set such that . Write where is uniformly . Then if and only if , if and only if , if and only if . Thus is . Similarly we can show that is . Thus is , i.e., , Q.E.D.

Remark 7.2   The hypothesis cannot be dropped from Theorem 5.13. To see this, recall from Remark 4.4 that there exists a such that for uncountably many . In particular, there are uncountably many such that yet . For such and , 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 , i.e., is low-for-random relative to . Then every subset of includes a 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 then .

Proof.Assume . By Theorem 10.10 we have , i.e., . From this it follows easily that . In other words, using the terminology of Nies [21], is -trivial relative to . By Chaitin's Theorem (see Downey/Hirschfeldt/Nies/Stephan [9, Corollary 6.7(ii)]) relative to , it follows that is , i.e., , hence .

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 and , does it follow that ? The answer to this question is negative. Indeed, letting be as in Theorem 6.10, we have and yet .

Question 7.6   If and , does it follow that ? (Compare Theorem 8.9 below.)

# Superhighness

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

Remark 8.1   Recall from Rogers [25, Chapters 8 and 9] the notion of truth-table reducibility, denoted . A result of Nerode (see Rogers [25, Chapter 9, Theorem XIX]) says that for all , if and only if for some total recursive functional . Thus truth-table reducibility is a special case of Turing reducibility.

Definition 8.2   Let be a Turing oracle. We say that is high if , i.e., is Turing reducible to . We say that superhigh if , i.e., is truth-table reducible to .

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

Definition 8.3   Let and be Turing oracles.
1. We say that is jump-traceable by if for each partial -recursive function there exist recursive functions and such that and .
2. We say that is weakly jump-traceable by if for each partial -recursive function there exists a recursive function such that and is finite.

Lemma 8.4   If then is jump-traceable by .

Proof.Consider the -r.e. set . We have

.
By Lemma 5.11 let be -r.e. such that , say
.
Let be a recursive function such that for all ,
.
Setting we obtain the desired conclusions. Note that the bounding function is not only recursive but primitive recursive.

Lemma 8.5   If is weakly jump-traceable by , then .

Proof.Consider the partial -recursive function least such that . Note that . By weak jump-traceability, let be recursive such that and is finite. Consider the total function . Note that is recursive relative to , and if and only if . Thus .

Lemma 8.6   If is jump-traceable by and -r.e., then .

Proof.Since is -r.e., let where , is a -recursive sequence of finite sets with . We identify the sets and with their characteristic functions. Consider the partial -recursive function the least such that . Clearly . By jump-traceability let and be recursive functions such that and . We may safely assume that each satisfies . For all and all let the th member of in order of -recursive enumeration. We may now compute from as follows. Given , for each ask the oracle whether and whether and and . Upon receiving the answers to these -many questions, we know the finite set . Then if and only if is nonempty. Thus , Q.E.D.

Remark 8.7   In the proof of Lemma 8.6 we have for any . Thus we see that, under the hypotheses of Lemma 8.6, the function

is -recursive with recursively bounded use of and unbounded use of . This conclusion is in general strictly stronger than either of the conditions and jump-traceable by . However, it is equivalent to their conjunction if , and it is equivalent to each of them individually if and is -r.e.

Theorem 8.8   If then .

Proof.This is immediate from Lemmas 8.4 and 8.5.

Theorem 8.9   If and is -r.e., then .

Proof.This is immediate from Lemmas 8.4 and 8.6.

Theorem 8.10   If then .

Proof.This is the special case of Theorem 8.9.

Theorem 8.11   If is almost everywhere dominating, then 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 then is superlow, i.e., (see Nies [21, Corollary 7.6]). Relativizing the arguments of Nies to a Turing oracle , one can show that if then . (See also Remark 10.12 below.) In particular, if then . Our Theorem 8.10 improves this by weakening the hypothesis to . In addition, Nies [21, paragraph preceding Proposition 8.3] announced that if and are r.e. and then . Our Theorem 8.9 improves this by eliminating the hypothesis that is r.e.

Question 8.13   If and , does it follow that ?

# Counterexamples via duality

In the previous section we have seen that if is almost everywhere dominating then is superhigh, which implies that 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 , we can find an r.e. set such that .

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 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 with corresponding properties on the right side of the table.

Table 1: Duality

 low high superlow superhigh low-for-random a. e. dominating

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

Theorem 9.2 (Cholak/Greenberg/Miller 2004)   There exists an r.e. set which is and almost everywhere dominating.

Proof.In Theorem 6.1 we have constructed an r.e. set which is and . By uniformly relativizing this construction to an arbitrary Turing oracle , we obtain a pseudojump operator such that for all , is and . Applying the Duality Theorem 9.1 to this operator, we obtain an r.e. set which is and . It follows by Theorems 5.7 and 8.11 that 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 which is superhigh and not almost everywhere dominating.

Proof.By uniformly relativizing the proof of Lemma 9.3, we obtain a pseudojump operator such that for all , is superlow relative to and not low-for-random relative to . In other words, and . Applying the Duality Theorem 9.1, we obtain an r.e. set such that and . It follows by Theorem 5.7 that 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 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 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 such that for all , is low and not superlow relative to . In other words, is and . Applying the Duality Theorem 9.1, we obtain an r.e. set such that is and . In other words, is high and not superhigh.

# Prefix-free Kolmogorov complexity

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

Lemma 10.1   Given a recursive sequence of natural numbers , such that , we can effectively find a recursive, one-to-one, prefix-free sequence of strings , such that for all .

Proof.Assume inductively that we have chosen , . Assume also that we have chosen another finite set of strings, . Define a partition to be a finite, maximal, prefix-free set of strings. We start with and assume inductively that has the following properties:

(a)
.
(b)
is a partition.
(c)
The strings in are all of different lengths. I.e., for all , if then .
In fact we shall have a stronger property: , where denotes the lexicographical order.

We claim that .

Otherwise , hence by (c) we have

hence by (b) we have

By the above claim, let be such that and is as large as possible. Let

Then and , for . Let

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

Definition 10.2   We define a machine to be a partial recursive function from into . A machine is said to be prefix-free if its domain

is prefix-free.

If is a prefix-free machine, then clearly , 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 be an r.e. subset of such that . Then we can effectively find a prefix-free machine such that for all there exists such that and .

Proof.Let , be a one-to-one recursive enumeration of . By Lemma 10.1 let , be a recursive, prefix-free sequence of strings such that for all . Define for all .

Remark 10.4   In the Kraft/Chaitin Theorem 10.3, the pairs are sometimes called axioms for the prefix-free machine . 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 is said to be universal if for all prefix-free machines there exists a string such that for all strings , . The prefix-free Kolmogorov complexity of a string is defined to be

where is a universal prefix-free machine. Note that is well defined up to within . In other words, if we let

where is another universal prefix-free machine, then , i.e., .

Corollary 10.6   Let be an r.e. subset of such that . Then for all we have .

Proof.Let be such that . Then , so by the Kraft/Chaitin Theorem 10.3 let be a prefix-free machine such that for all there exists such that and . Let be such that for all . Then for all we have . 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 , we have that is random if and only if , i.e., .

Proof.For let . Note that is uniformly . We claim that . To see this, for each such that choose such that and . Here is a universal prefix-free machine. By the Kraft Inequality we have

hence

thus proving the claim. We now see that , is a Martin-Löf test. Therefore, if is random, we have , i.e., , i.e., . This is one direction of the theorem.

For the converse, assume is not random, say where is uniformly and , . Let be uniformly r.e. and prefix-free such that . We have

Hence by Corollary 10.6, for all and all . Since for all , it follows that .

Remark 10.8   The above definitions and results can be uniformly relativized to an arbitrary Turing oracle . Thus, a prefix-free -machine is a partial -recursive function from to such that is prefix-free. We define where is a universal prefix-free -machine. The relativization of Schnorr's Theorem says that is -random if and only if .

Definition 10.9 (Nies 2002)   Let and be Turing oracles. We say that is -reducible to , abbreviated , if . In other words, for some constant we have for all strings .

Theorem 10.10 (Kjos-Hanssen/Miller/Solomon 2006)
The following statements are pairwise equivalent.
1. .
2. .
3. For any -r.e. set such that , there exists a -r.e. set such that .

Proof.The implication follows from Schnorr's Theorem relativized to and . The implication follows from Lemma 5.11. Now assume and let . Clearly is -r.e. and , so let be -r.e. such that . By Corollary 10.6 relative to we have for all . Since it follows that for all . This proves .

Remark 10.11   The reducibilities and were originally defined by Nies [21, Section 8]. In the direction of Theorem 10.10, Nies proved the equivalence (see [21, Corollary 5.3]) and noted that implies . The full equivalence 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 for which no other proofs are presently known. Among these results are:
1. If and then . (See Nies [21, Theorem 6.2] and Downey/Hirschfeldt/Nies/Stephan [9, Theorem 7.2].) More generally, if and then .

Caution: It is not in general true that if and then . Indeed, in Theorem 6.10 above we have constructed a such that yet .

2. If then , in fact (see Nies [21, Corollary 7.6]). More generally, if then (see Lemma 7.4 above), in fact .

3. If then we can find an r.e. set such that and , in fact . (See Nies [21, Theorems 7.4 and 6.2].) More generally, if then we can find a -r.e. set such that and , in fact . See also Theorem 8.9 above.

4. If then and (see Nies [21, Proposition 8.3(iii)]), hence and , in fact .

In particular, for each there are only countably many such that .

Caution: By Miller/Yu [19,18], there exists a such that is uncountable. In fact, Barmpalias/Lewis/Soskova [1] have shown that this holds for any which is generalized superhigh.

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

## Bibliography

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

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

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

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

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

6
C.-T. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang, editors.
Computational Prospects of Infinity: Proceedings of the Logic Workshop at the Institute for Mathematical Sciences, June 20 - August 15, 2005, Part II: Presented Talks.
Number 15 in Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific, 2008.
432 pages.

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

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

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

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

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

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

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

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

15
Antonín Kucera.
Measure, classes and complete extensions of PA.
In [10], pages 245-259, 1985.

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

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

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

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

20
Jeanleah Mohrherr.
A refinement of low and high 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.

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

23
Real Variables.
Appleton-Century-Crofts, 1959.
VIII + 621 pages.

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

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

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

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

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

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

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

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

Almost everywhere domination and superhighness

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 aedsh

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

#### Footnotes

... measure1
For example, we may take where , is a universal Martin-Löf test for -randomness as in Theorem 3.2.
... obtain2
For example, we may take where , is a universal Martin-Löf test for -randomness as in Theorem 3.2.

Stephen G Simpson 2009-10-29