publication . Preprint . Article . 2015

Asymptotic density and the Ershov hierarchy

Rod Downey; Carl Jockusch; Timothy H. McNicholl; Paul Schupp;
Open Access English
  • Published: 14 Apr 2015
Abstract
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$ reals. Further, we show that the densities of the $\omega$-c.e.\ sets coincide with the densities of the $\Delta^0_2$ sets, and there are $\omega$-c.e.\ sets whose density is not the density of an $n$-c.e. set for any $n \in \omega$.
Subjects
free text keywords: Mathematics - Logic, 03D25, 03D78, Natural density, If and only if, Combinatorics, Mathematics, Hierarchy, Discrete mathematics, Computability theory

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. [OpenAIRE]

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). [OpenAIRE]

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. [OpenAIRE]

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

Green St., Urbana, Illinois 61801 USA E-mail address: schupp@math.uiuc.edu

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Article . 2015

Asymptotic density and the Ershov hierarchy

Rod Downey; Carl Jockusch; Timothy H. McNicholl; Paul Schupp;