Blog Archives

Topic Archive: asymptotic density

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20161:15 pmLocklin Hall, Room 232, Springfield College

Eric Astor

Density and computability

University of Connecticut

We develop and discuss some of the theory relating asymptotic density and computability, with attention to the inherent complexity of sets with density invariant under computable permutation. We will make a brief excursion into reverse mathematics on the way, pointing out that a key equivalence of Kjos-Hanssen, Merkle, and Stephan holds over RCA0.

CUNY Logic WorkshopFriday, November 6, 20152:00 pmGC 6417

Eric Astor

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.