pith. sign in

arxiv: 1708.04267 · v2 · pith:E5EM7ESSnew · submitted 2017-08-14 · 🧮 math.LO

The computational content of intrinsic density

classification 🧮 math.LO
keywords densityintrinsicnon-computabledegreediagonallyeveryexistencefunction
0
0 comments X
read the original abstract

In a previous paper, the author introduced the idea of intrinsic density --- a restriction of asymptotic density to sets whose density is invariant under computable permutation. We prove that sets with well-defined intrinsic density (and particularly intrinsic density 0) exist only in Turing degrees that are either high ($\mathbf{a}'\ge_{\rm T}\emptyset"$) or compute a diagonally non-computable function. By contrast, a classic construction of an immune set in every non-computable degree actually yields a set with intrinsic lower density 0 in every non-computable degree. We also show that the former result holds in the sense of reverse mathematics, in that (over $\mathsf{RCA}_0$) the existence of a dominating or diagonally non-computable function is equivalent to the existence of a set with intrinsic density 0.

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.