Intrinsic density and computability
University of Connecticut
The idea of a negligible subset of the natural numbers is highly appealing; bad behavior often seems restricted to a “small” set. Asymptotic density (the usual solution) has been used repeatedly in many fields, most prominently in number theory. Unfortunately, this is largely incompatible with the computability theorist’s perspective; even 1-equivalent sets can have wildly different densities. However, by restricting to cases where density is computably invariant, we develop a new notion with appealing properties. We will characterize exactly how hard it is to make a set with intrinsic density, and uncover connections to both computability and randomness. In particular, we suggest that Post missed a very natural immunity property when developing his notions of hyperimmunity.
Eric Astor received his doctorate from the University of Chicago in 2015, under the supervision of Denis Hirschfeldt and Robert Soare. He now holds a postdoctoral position at the University of Connecticut.