Asymptotic density and the Ershov hierarchy
classification
🧮 math.LO
keywords
densitysetsdensitiesomegaasymptoticdeltaershovhierarchy
read the original 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.