A Turing degree a is said to be almost everywhere dominating if, for almost all $X \in 2^{\omega}$ with respect to the "fair coin" probability measure on $2^{\omega}$ , and for all g: $\omega \rightarrow \omega$ Turing reducible to X, there exists f: $\omega \rightarrow \omega$ of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in (...) the reverse mathematics of measure theory. (shrink)

We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.

We examine the concept of almost everywhere domination from the viewpoint of mass problems. Let AED and MLR be the sets of reals which are almost everywhere dominating and Martin-Löf random, respectively. Let b1, b2, and b3 be the degrees of unsolvability of the mass problems associated with AED, MLR × AED, and MLR ∩ AED, respectively. Let [MATHEMATICAL SCRIPT CAPITAL P]w be the lattice of degrees of unsolvability of mass problems associated with nonempty Π01 subsets of 2ω. Let 1 (...) and 0 be the top and bottom elements of [MATHEMATICAL SCRIPT CAPITAL P]w. We show that inf, inf, and inf belong to [MATHEMATICAL SCRIPT CAPITAL P]w and 0 < inf < inf < inf < 1. Under the natural embedding of the recursively enumerable Turing degrees into [MATHEMATICAL SCRIPT CAPITAL P]w, we show that inf and inf but not inf 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. (shrink)

It is shown that if A and C are sets of degrees uniformly recursive in 0' with $\mathbf{0} \nonin \mathscr{C}$ then there is a degree b with b' = 0', b ∪ c = 0' for every c ∈ C, and $\mathbf{a} \nleq \mathbf{b}$ for every a ∈ A ∼ {0}. The proof is given as an oracle construction recursive in 0'. It follows that any nonrecursive degree below 0' can be joined to 0' by a degree strictly below 0'. (...) Also, if $\mathbf{a ' and a" = 0" then there is a degree b such that a ∪ b = 0' and a ∩ b = 0. (shrink)

We say that A ≤LR B if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ. In other words. B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumberable degrees) and their relationship with the Turing degrees. Among other results we show that whenever α in not GL₂ the LR degree of (...) α bounds $2^{\aleph _{0}}$ degrees (so that, in particular, there exist LR degrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. LR degrees. (shrink)

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RAND A.

Robert I. Soare, Automorphisms of the Lattice of Recursively Enumerable Sets. Part I: Maximal Sets.Manuel Lerman, Robert I. Soare, $d$-Simple Sets, Small Sets, and Degree Classes.Peter Cholak, Automorphisms of the Lattice of Recursively Enumerable Sets.Leo Harrington, Robert I. Soare, The $\Delta^0_3$-Automorphism Method and Noninvariant Classes of Degrees.