Premium
Asymptotic density and the Ershov hierarchy
Author(s) -
Downey Rod,
Jockusch Carl,
McNicholl Timothy H.,
Schupp Paul
Publication year - 2015
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.201300081
Subject(s) - natural density , mathematics , hierarchy , set (abstract data type) , discrete mathematics , computer science , economics , market economy , programming language
We classify the asymptotic densities of the Δ 2 0 sets according to their level in the Ershov hierarchy. In particular, it is shown that for n ≥ 2 , a real r ∈ [ 0 , 1 ] is the density of an n ‐c.e. set if and only if it is a difference of left‐ Π 2 0 reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the Δ 2 0 sets, and there are ω‐c.e. sets whose density is not the density of an n ‐c.e. set for any n ∈ ω .