Article contents
THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY
Published online by Cambridge University Press: 01 August 2018
Abstract
In a previous article, 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 (${\bf{a}}\prime { \ge _{\rm{T}}}\emptyset \prime \prime$) or compute a diagonally noncomputable function. By contrast, a classic construction of an immune set in every noncomputable degree actually yields a set with intrinsic lower density 0 in every noncomputable degree.
We also show that the former result holds in the sense of reverse mathematics, in that (over RCA0) the existence of a dominating or diagonally noncomputable function is equivalent to the existence of a set with intrinsic density 0.
- Type
- Articles
- Information
- Copyright
- Copyright © The Association for Symbolic Logic 2018
References
REFERENCES
- 1
- Cited by