Asymptotic density and the Ershov hierarchy

2013/08/31 by Rod Downey, Downey, Rod, Carl Jockusch +5
Mathematics · #03D25 #03D78 #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03D25 #msc:03D78

paper · pdf · doi:10.48550/arxiv.1309.0137

To appear in Mathematical Logic Quarterly

arxiv created 2014/08/17 · arxiv updated 2014/08/19

Abstract

We classify the asymptotic densities of the Δ⁰₂ 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-Π₂⁰ reals. Further, we show that the densities of the ω-c.e. sets coincide with the densities of the Δ⁰₂ sets, and there are ω-c.e. sets whose density is not the density of an n-c.e. set for any n ∈ ω.

Related

• Asymptotic ψ-densities of subsets of natural numbers
• Abstract densities and ideals of sets
• A note on asymptotic density
• On the limits of real-valued functions in sets involving ψ-density, and applications
• On the density or measure of sets and their sumsets in the integers or\n the circle