Asymptotic density and the Ershov hierarchy

Abstract

We classify the asymptotic densities of the ${\Delta }_2^0$ sets according to their level in the Ershov hierarchy. In particular, it is shown that for $n\ge 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 }_2^0$ 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$.

To appear in Mathematical Logic Quarterly