Abstract

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