Coarse Computability, the Density Metric,
Hausdorff Distances between Turing Degrees, Perfect Trees, and
Reverse Mathematics
Status: submitted
Availability: preprint
Abstract. For A ⊆ ω, the coarse similarity
class of A, denoted by [A], is the set of all B
⊆ ω such that the symmetric difference of A and B
has asymptotic density 0. There is a natural metric δ on the space
S of coarse similarity classes defined by letting
δ([A],[B]) be the upper density of the symmetric
difference of A and B. We study the metric space of coarse
similarity classes under this metric, and show in particular that between
any two distinct points in this space there are continuum many geodesic
paths. We also study subspaces of the form {[A] : A ∈
U} where U is closed under Turing equivalence, and show that
there is a tight connection between topological properties of such a space
and computability-theoretic properties of U.
We then define a distance between Turing degrees based on Hausdorff
distance in the metric space (S,δ). We adapt a proof of Monin
to show that the Hausdorff distances between Turing degrees that occur are
exactly 0, 1/2, and 1, and study which of these values occur most
frequently in the senses of Lebesgue measure and Baire category. We define
a degree a to be attractive if the class of all
degrees at distance 1/2 from a has measure 1, and
dispersive otherwise. In particular, we study the distribution of
attractive and dispersive degrees. We also study some properties of the
metric space of Turing degrees under this Hausdorff distance, in
particular the question of which countable metric spaces are isometrically
embeddable in it, giving a graph-theoretic sufficient condition for
embeddability.
Motivated by a couple of issues arising in the above work, we also study
the computability-theoretic and reverse-mathematical aspects of a
Ramsey-theoretic theorem due to Mycielski, which in particular implies
that there is a perfect set whose elements are mutually 1-random, as well
as a perfect set whose elements are mutually 1-generic.
Finally, we study the completeness of (S,δ) from the
perspectives of computability theory and reverse mathematics.
drh@math.uchicago.edu