Premium
Mass problems and almost everywhere domination
Author(s) -
Simpson Stephen G.
Publication year - 2007
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200710013
Subject(s) - recursively enumerable language , mathematics , combinatorics , embedding , recursively enumerable set , turing , discrete mathematics , computer science , artificial intelligence , programming language
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 b 1 , b 2 , and b 3 be the degrees of unsolvability of the mass problems associated with AED, MLR × AED, and MLR ∩ AED, respectively. Let w be the lattice of degrees of unsolvability of mass problems associated with nonempty Π 0 1 subsets of 2 ω . Let 1 and 0 be the top and bottom elements of w . We show that inf( b 1 , 1 ), inf( b 2 , 1 ), and inf( b 3 , 1 ) belong to w and 0 < inf( b 1 , 1 ) < inf( b 2 , 1 ) < inf( b 3 , 1 ) < 1 . Under the natural embedding of the recursively enumerable Turing degrees into w , we show that inf( b 1 , 1 ) and inf( b 3 , 1 ) but not inf( b 2 , 1 ) 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. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)