Stephen G. Simpson
Pennsylvania State University
First draft: July 5, 2006
This draft: October 29, 2009
http://www.personal.psu.edu/t20/
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.
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
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.
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.
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
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].
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.
Proof.For each let
. Let
be such that
. We claim that
. To see this, let
and note that
. For
all we have
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
Next we present the Kucera/Gács Theorem, from Kucera [15].
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
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.
Proof.By Corollary 3.3 let be of positive measure such that is random. Applying Lemma 3.7 to any , we obtain such that .
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].
In this section we study the following reducibility notion, which was originally introduced by Nies [21, Section 8].
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.
We now prove the following theorem due to Kjos-Hanssen [13].
Proof.In order to prove Theorem 4.6, we first prove several lemmas.
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.
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].
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:
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].
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.
Proof.Let , be a standard, uniform enumeration of all subsets of , where is a Turing oracle. Fix such that for all , is of positive measure^{1} 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:
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].
Proof.See Dobrinen/Simpson [7, Theorem 3.2].
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].
We then have:
Proof.This is immediate from the special case of Theorem 4.6.
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.
Proof.This is immediate from Corollary 5.6 and Theorem 5.7.
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.
Proof.We use the following fact from analysis. Given , , we have
To prove our lemma, let be as in the hypotheses of the lemma. We may safely assume that for all . Let
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
We may safely assume that . Since , let be a -recursive approximation of . Let
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
This completes the proof of Theorem 5.13.
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].
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 obtain^{2} 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.
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].)
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.
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.
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.
Proof.See Posner/Robinson [24].
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.
This section consists of some technical remarks showing that Theorem 5.13 is, in various senses, best possible.
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
The following special case of Theorem 5.13 seems interesting in view of Remarks 4.3 and 4.4.
Proof.We first prove a lemma which is well known. See also Remark 10.12 below.
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.
In this section we present some new results concerning the relationship between -reducibility and truth-table reducibility.
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.
Proof.Consider the -r.e. set . We have
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 .
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.
Proof.This is immediate from Lemmas 8.4 and 8.5.
Proof.This is immediate from Lemmas 8.4 and 8.6.
Proof.This is the special case of Theorem 8.9.
Proof.This is a restatement of Theorem 8.10 in light of Theorem 5.7.
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.
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.
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.
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.
Proof.We omit the proof, which is fairly straightforward.
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].
Proof.See Mohrherr [20, Theorem 3] and Bickford/Mills (reference in Mohrherr [20]).
The following counterexample is due to Mohrherr [20].
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.
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].
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:
We claim that .
Otherwise
, hence by (c) we have
By the above claim, let be such that
and is as large as possible. Let
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].
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 .
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.
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
For the converse, assume is not random, say
where
is uniformly and
, . Let be uniformly r.e. and prefix-free such that
. We
have
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 .
Caution: It is not in general true that if and then . Indeed, in Theorem 6.10 above we have constructed a such that yet .
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.
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