Stephen G. Simpson
Pennsylvania State University
First draft: September 15, 2006
This draft: April 28, 2008
http://www.personal.psu.edu/t20/
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.
In our previous papers [3,31,34,32,7] we studied the lattice of degrees of unsolvability of mass problems associated with nonempty subsets of . We showed that contains many specific, natural degrees in addition to and , the top and bottom elements of . We showed that many specific, natural degrees in 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 . The new examples arise from almost everywhere domination, a concept which was originally introduced by Dobrinen/Simpson [9]. Let be a Turing oracle. We say that is almost everywhere dominating if, for all except a set of measure , each function computable from is dominated by some function computable from . 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 is Martin-Löf random and is almost everywhere dominating. For we write and and the intersection of and . With these conventions, let , , be the respective degrees of unsolvability of the mass problems associated with , , . Trivially . Our main results may be summarized by saying that the degrees , , belong to and
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 . In order to state our results, let us temporarily identify each recursively enumerable Turing degree with its image in under the natural one-to-one embedding given in [34, Theorem 5.5]. In particular, we identify and , the top and bottom recursively enumerable Turing degrees, with and , the top and bottom degrees in . In our papers [31,34] written in 2004, we remarked that all of the specific, natural degrees in which were known at that time are incomparable with all recursively enumerable Turing degrees except and . In this respect it turns out that our new examples of specific, natural degrees in behave somewhat differently from the old ones. Namely, although is again incomparable with all recursively enumerable Turing degrees except and , this turns out not to be the case for and . See Theorems 3.1 and 3.2 below.
Our work in this paper owes much to conversations with Bjørn Kjos-Hanssen, Antonín Kucera, and Joseph S. Miller. In particular, the fact that belongs to was already implicit in Kjos-Hanssen [18], and Miller corrected an error in one of our early proofs of the inequality .
The reader who is familiar with the basics of recursion theory will find that this paper is largely self-contained. If is an expression which may or may not denote a natural number, we write to mean that is defined (i.e., denotes a natural number), otherwise . If and are two such expressions, we write to mean that and 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.
The purpose of this section is to prove our mass problem inequalities in . 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 , we say that is Turing reducible to , abbreviated , if is computable using as an oracle. A Turing degree is an equivalence class of elements of under mutual Turing reducibility. The Turing degree of is denoted .
Our notion of reducibility for mass problems is as follows. Given , we say that is weakly reducible to , abbreviated , if for all there exists such that is Turing reducible to . A weak degree is an equivalence class of subsets of under mutual weak reducibility. The weak degree of is denoted . Weak degrees have sometimes been known as Muchnik degrees [23].
Note that for and we have and . Note also that for we have if and only if . Here denotes the singleton set whose only element is . Therefore, the Turing degree is sometimes identified with the weak degree .
Proof.An important tool in the study of is the Embedding Lemma [34, Lemma 3.3], [32, Lemma 4]. The Embedding Lemma says: For any where is , we have . Therefore, in order to prove Theorem 2.2, it suffices to show that and are .
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 is almost everywhere dominating if and only if . Here denotes the Halting Problem, and denotes -reducibility: if and only if if is random relative to , then is random relative to . Moreover, as shown in [19], -reducibility is equivalent to -reducibility: if and only if for all . Here denotes the prefix-free Kolmogorov complexity of relative to a Turing oracle . The concepts of -reducibility and -reducibility were originally introduced by Nies [24, Section 8]. A convenient reference for these results is Simpson [33].
One way to see that is is to use the characterization in terms of -reducibility. We know that if and only if , i.e., , i.e., . But if and only if and . Here is a universal prefix-free oracle machine. The last satement is , so is . The fact that is 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 is . In fact, is 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.
Proof.Trivially , hence . Recall from [31,34] that where
Next we prove . We use the forcing construction of Cholak/Greenberg/Miller [5] referring to -genericity.
It remains to prove . We use the following results of Nies 2006 and Stephan 2002.
This completes the proof of Theorem 2.3.
In this section we discuss the relationship between the weak degrees , , 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 given by .
Proof.Let where is recursively enumerable and . Since is nonrecursive, we have by Lemma 2.7, hence by Lemmas 2.5 and 2.6, hence by Lemma 2.9. From this it follows trivially that . In other words, . On the other hand, since is recursively enumerable and not Turing complete, we have by the Arslanov Completeness Criterion [14], hence by Lemmas 2.5 and 2.6. From this it follows trivially that . In other words, . This completes the proof.
Proof.By Lemma 2.8 due to Hirschfeldt and Miller, let be recursively enumerable such that . By Simpson [33, Example 6.8] or Cholak/Greenberg/Miller [5, Theorem 2.1], let be recursively enumerable and almost everywhere dominating. Let and . Clearly and and and . By Theorems 2.3 and 3.1 it follows that and .
In this section we exposit the proof of the following theorem of Hirschfeldt and Miller 2006, generalizing a much earlier theorem of Kucera [21].
Proof.We follow the writeup of Nies [25, Theorem 5.6].
We first prove the theorem for sets. Let be of measure . Write where is uniformly and .
The construction of is as follows. At stage , for each such that , look for such that and and put the least such into .
Clearly is recursively enumerable. Moreover, for each , at most one gets into for the sake of , and for this we have . Hence has at most members . Thus is infinite.
We claim that if is infinite then . To see this, fix so large that and . Let be such that . We have , so by construction , Q.E.D.
It follows from the previous claim that is nonrecursive. Indeed, is simple in the sense of Post (compare Rogers [27, Section 8.1]).
We claim that for all random . To see this, note
that by construction
Suppose now that is of measure . Write
where is uniformly . Write
where is uniformly and
for each . This implies that
, so we can build as before
replacing by
. The
construction insures that
The following corollary is originally due to Kucera [21].
Proof.Let and apply Theorem 4.1.
The following lemma is well known.
Proof.It suffices to show that whenever is random relative to . (Generalizations of this result are in Kautz's thesis [17, Theorem III.2.1].) Consider the sets . Obviously these sets are uniformly . Let least such that . Note that . Thus is uniformly and these sets form a Solovay test relative to . Now assume that is random relative to . By Solovay's Lemma relative to , we have for all but finitely many . In other words, for all but finitely many , if and only if . Since , it follows that . This completes the proof.
Proof.By Theorem 4.1 with , it suffices to show that is and of measure . We have seen in the proof of Theorem 2.2 that is . To show that , recall from [19] and [33, Section 8] that . Thus is disjoint from the intersection of two sets: and . The first set is of measure by Lemma 4.4, and the second set is of measure by Lemma 2.9. This completes the proof.
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 given by for all .
Proof.Our proof is based on a sketch given by Kucera 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 Kucera/Gács Theorem.
Let us write . Note that , is a standard, recursive enumeration of all subsets of . Given a set , an index of is any integer such that . Let us say that a set is rich if and there exists a recursive function such that for all , if then .
We claim that every set of positive measure includes a set which is rich. To see this, let be such that . Write and note that , is a uniformly recursive descending sequence of clopen sets such that . Define a recursive ascending sequence of clopen sets , as follows. Begin with . Given define where the union is taken over all such that . Finally let where . Clearly is . Moreover , hence . If then for all we have , hence . Thus is rich via . This proves our claim.
To prove the theorem, let be of positive measure. By our claim, we may safely assume that is rich. Under this assumption we shall carry out the proof of the Pseudojump Inversion Theorem ``within '' to produce with the desired properties.
For strings let us write . For each string we define a string and a nonempty set . Begin with and . Assume inductively that and have already been defined.
In order to control the pseudojump , define a string and a nonempty set as follows. Let . If and , let and let . Otherwise, consider the least such that and , and let and . Thus ``decides'' whether or not.
Because is rich, given an index of we can effectively find such that . But then there are at least two strings of length such that . Let and be the lexicographically leftmost and rightmost such . Let and .
We have now defined , , , for all . It is straightforward to check that and and the indices of and are uniformly computable from .
Given let . Then if and only if . Moreover, it is straightforward to show that and and the indices of and are uniformly computable from each of the Turing oracles and and . From this, the desired conclusions follow easily.
Proof.In Theorem 5.1 let be a nonempty set such that is random.
Proof.By Theorem 5.2, it suffices to produce a psuedojump operator such that for all , and is low-for-random relative to . Such an operator is obtained by uniformly relativizing the Kucera/Terwijn [22] construction of a nonrecursive, recursively enumerable set which is low-for-random. See also the exposition in Simpson [33, Section 6].
Proof.This is the special case of Corollary 5.4 in which we let .
Proof.This follows from Corollary 5.4 by considering uncountably many .
Proof.Corollaries 5.7 and 5.8 are immediate from Corollaries 5.5 and 5.6 plus the following fact: If is low-for-random relative to then is almost everywhere dominating. This fact is due to Kjos-Hanssen/Miller/Solomon [19]. See also the exposition in Simpson [33, Section 5].
In this section we exposit the proof of the following theorem of Stephan [35].
Proof.We shall define a recursively bounded, partial recursive function with the following property: For all random , if some total function extending then . This suffices to prove the theorem, because clearly every computes a total extension of every recursively bounded, partial recursive function (see for instance [31, Theorem 4.10]).
Recall that is a recursively enumerable set. If let be undefined for all . If , say , then for each compute the rational numbers
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 massaed
The translation was initiated by Stephen G Simpson on 2008-04-28