For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] 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 [Formula: see text] where [Formula: see text] 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 [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], 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 [Formula: see text] 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 [Formula: see text] from the perspectives of computability theory and reverse mathematics. (shrink)

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if for all Y ∈ Q there exists X ∈ P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. Let [Formula: see text] be the lattice of weak degrees of mass problems associated with nonempty [Formula: see text] subsets of the Cantor (...) space. The lattice [Formula: see text] has been studied in previous publications. The purpose of this paper is to show that [Formula: see text] partakes of hyperarithmeticity. We exhibit a family of specific, natural degrees in [Formula: see text] which are indexed by the ordinal numbers less than [Formula: see text] and which correspond to the hyperarithmetical hierarchy. Namely, for each [Formula: see text], let hα be the weak degree of 0, the αth Turing jump of 0. If p is the weak degree of any mass problem P, let p* be the weak degree of the mass problem P* = {Y | ∃X ⊆ BLR )} where BLR is the set of functions which are boundedly limit recursive in X. Let 1 be the top degree in [Formula: see text]. We prove that all of the weak degrees [Formula: see text], [Formula: see text], are distinct and belong to [Formula: see text]. In addition, we prove that certain index sets associated with [Formula: see text] are [Formula: see text] complete. (shrink)