{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T02:24:45Z","timestamp":1648607085566},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2933,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2006,3]]},"abstract":"Dobrinen and Simpson [4] introduced the notions of almost everywhere domination and uniform almost everywhere domination to study recursion theoretic analogues of results in set theory concerning domination in generic extensions of transitive models of ZFC and to study regularity properties of the Lebesgue measure on 2\u03c9<\/jats:italic><\/jats:sup> in reverse mathematics. In this article, we examine one of their conjectures concerning these notions.<\/jats:p>Throughout this article, \u2264T<\/jats:italic><\/jats:sub> denotes Turing reducibility and \u03bc<\/jats:italic> denotes the Lebesgue (or \u201cfair coin\u201d) probability measure on 2\u03c9<\/jats:italic><\/jats:sup> given by<\/jats:p><\/jats:disp-formula><\/jats:p>A property holds almost everywhere<\/jats:italic> or for almost all X<\/jats:italic> \u2208 2\u03c9<\/jats:italic><\/jats:sup> if it holds on a set of measure 1. For f, g<\/jats:italic> \u2208 \u03c9\u03c9<\/jats:sup><\/jats:italic>, f<\/jats:italic> dominatesg if \u2203m<\/jats:italic>\u2200n<\/jats:italic> < m<\/jats:italic>(f(n<\/jats:italic>) > g<\/jats:italic>(n<\/jats:italic>)).<\/jats:p>(Dobrinen, Simpson). A set A<\/jats:italic> \u2208 2\u03c9<\/jats:sup>is almost everywhere (a.e.) dominating if for almost all X<\/jats:italic> \u2208 2\u03c9<\/jats:sup> and all functions g<\/jats:italic> \u2264T<\/jats:sub>X<\/jats:italic>, there is a function f<\/jats:italic> \u2264T<\/jats:sub>A<\/jats:italic> such that f<\/jats:italic> dominates g<\/jats:italic>. A is uniformly almost everywhere (u.a.e.) dominating<\/jats:italic> if there is a function f<\/jats:italic> \u2264T<\/jats:italic><\/jats:sub>A<\/jats:italic> such that for almost all X<\/jats:italic> \u2208 2\u03c9<\/jats:italic><\/jats:sup> and all functions g<\/jats:italic> \u2264T<\/jats:italic><\/jats:sub>X, f<\/jats:italic> dominates g<\/jats:italic>.<\/jats:p>There are several trivial but useful observations to make about these definitions. First, although these properties are stated for sets, they are also properties of Turing degrees. That is, a set is (u.)a.e. dominating if and only if every other set of the same degree is (u.)a.e. dominating. Second, both properties are closed upwards in the Turing degrees. Third, u.a.e. domination implies a.e. domination. Finally, if A<\/jats:italic> is u.a.e. dominating, then there is a function f<\/jats:italic> \u2264T<\/jats:italic><\/jats:sub>A<\/jats:italic> which dominates every computable function.<\/jats:p>","DOI":"10.2178\/jsl\/1140641165","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T16:22:31Z","timestamp":1198081351000},"page":"119-136","source":"Crossref","is-referenced-by-count":13,"title":["On a conjecture of Dobrinen and Simpson concerning almost everywhere domination"],"prefix":"10.1017","volume":"71","author":[{"given":"Stephen","family":"Binns","sequence":"first","affiliation":[]},{"given":"Bj\u00f8rn","family":"Kjos-Hanssen","sequence":"additional","affiliation":[]},{"given":"Manuel","family":"Lerman","sequence":"additional","affiliation":[]},{"given":"Reed","family":"Solomon","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120000637X_ref007","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.40.605"},{"key":"S002248120000637X_ref006","unstructured":"Downey R. , Hirschfeldt D.R. , Miller J. , and Nies A. , Relativizing Chaitin's halting probability, submitted."},{"key":"S002248120000637X_ref020","first-page":"501","volume":"37","author":"Stillwell","year":"1972","journal-title":"Decidability of the \u201calmost all\u201d theory of degrees"},{"key":"S002248120000637X_ref004","first-page":"914","volume":"69","author":"Dobrinen","year":"2004","journal-title":"Almost everywhere domination"},{"key":"S002248120000637X_ref017","unstructured":"Schwarz S. , Index sets of recursively enumerable sets, quotient lattices, and recursive linear orderings, Ph.D. thesis, University of Chicago, 1982."},{"key":"S002248120000637X_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59971-2"},{"key":"S002248120000637X_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076224"},{"key":"S002248120000637X_ref005","unstructured":"Downey R. and Hirschfeldt D.R. , Algorithmic randomness and complexity, online manuscript available at www.mcs.vuw.ac.nz\/~downey."},{"key":"S002248120000637X_ref001","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608858"},{"key":"S002248120000637X_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S002248120000637X_ref002","unstructured":"Cholak P. , Greenberg N. , and Miller J.S. . Uniform almost everywhere domination, to appear."},{"key":"S002248120000637X_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.006"},{"key":"S002248120000637X_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S002248120000637X_ref013","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19660120125"},{"key":"S002248120000637X_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S002248120000637X_ref016","first-page":"515","volume":"70","author":"Nies","year":"2005","journal-title":"Randomness, relativization and Turing degrees"},{"key":"S002248120000637X_ref010","unstructured":"Kurtz S. , Randomness and genericity in the degrees of unsolvability, Ph.D. thesis. University of Illinois at Urbana-Champaign, 1981."},{"key":"S002248120000637X_ref011","unstructured":"van Lambalgen M. , Random sequences, Ph.D. thesis, University of Amsterdam, 1987."},{"key":"S002248120000637X_ref008","unstructured":"Kautz S. , Degrees of random sets, Ph.D. thesis, Cornell University, 1991."},{"key":"S002248120000637X_ref003","first-page":"1","volume":"66","author":"Cholak","year":"2001","journal-title":"On the strength of Ramsey's Theorem for pairs"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120000637X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T20:34:23Z","timestamp":1556829263000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120000637X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["S002248120000637X"],"URL":"http:\/\/dx.doi.org\/10.2178\/jsl\/1140641165","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":["Logic","Philosophy"],"published":{"date-parts":[[2006,3]]}}}