Asymptotic density and the Ershov hierarchy

Preprint English OPEN
Downey, Rod; Jockusch, Carl; McNicholl, Timothy H.; Schupp, Paul;
(2013)
  • Subject: Mathematics - Logic | 03D25, 03D78

We classify the asymptotic densities of the $\Delta^0_2$ sets according to their level in the Ershov hierarchy. In particular, it is shown that for $n \geq 2$, a real $r \in [0,1]$ is the density of an $n$-c.e.\ set if and only if it is a difference of left-$\Pi_2^0$ re... View more
  • References (11)
    11 references, page 1 of 2

    1. K. Ambos-Spies, K. Weihrauch, and X. Zheng, Weakly computable real numbers, Journal of Complexity 16 (2000), no. 4, 679 - 690.

    2. Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010.

    3. Rodney G. Downey, Carl G. Jockusch, Jr., and Paul E. Schupp, Asymptotic density and computably enumerable sets, Journal of Mathematical Logic, to appear.

    4. Richard L. Epstein, Richard Haas, and Richard L. Kramer, Hierarchies of sets and degrees below 0′, Logic Year 1979-80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) (Berlin), Lecture Notes in Math., vol. 859, Springer, 1981, pp. 32-48.

    5. Y.L. Ershov, A hierarchy of sets, part I, Algebra and Logic 7 (1968), 24-43, (English translation).

    6. , A hierarchy of sets, part II, Algebra and Logic 7 (1968), 212-232, (English translation).

    7. , A hierarchy of sets, part III, Algebra and Logic 9 (1970), 20-31, (English translation).

    8. Carl G. Jockusch, Jr. and Paul E. Schupp, Generic computability, Turing degrees, and asymptotic density, J. Lond. Math. Soc. (2) 85 (2012), no. 2, 472-490.

    9. R. Soare, Cohesive sets and recursively enumerable Dedekind cuts, Pacific J. Math. 31 (1969), 215-231. School of Mathematics, Statistics, and Operations Research, Victoria University of Wellington, New Zealand E-mail address: Rod.Downey@msor.vuw.ac.nz Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W.

    Green St., Urbana, Illinois 61801 USA E-mail address: jockusch@math.uiuc.edu Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W.

  • Metrics
Share - Bookmark