UC Berkeley

We investigate the problem of what equivalence relations from recursion theory are universal countable Borel equivalence relations. While this question is interesting in its own right, it has also been a particularly rich source of connections between recursion theory, countable Borel equivalence relations, and Borel combinatorics. Tools developed by this investigation have proved very applicable to other problems in these fields.

In Chapter 2, we prove a model universality theorem, and introduce several themes of the thesis. A corollary of this first theorem is that polynomial time Turing equivalence is a universal countable Borel equivalence relation.

Slaman and Steel have shown that arithmetic equivalence is a universal countable Borel equivalence relation. In Chapter 3, we combine this fact with the existence of a cone measure for arithmetic equivalence to prove several structural results about universal countable Borel equivalence relations in general. We show that universality for Borel reductions coincides with universality for Borel embeddings, and a universal countable Borel equivalence relation is always universal on some nullset with respect to any Borel probability measure. We also settle questions of Thomas, and Jackson, Kechris, and Louveau by showing that a smooth disjoint union of non-universal countable Borel equivalence relations is non-universal. This result can be significantly strengthened by assuming a conjecture of Martin which states that every Turing invariant function is equivalent to a uniformly Turing invariant function on a Turing cone.

In Chapter 4, we investigate uniformity of homomorphisms among equivalence relations from recursion theory. We pose several open questions in this context, and investigate the implications of the uniformity that they imply. We introduce the concept of a Borel metric on a countable Borel equivalence relation, and show that this concept is closely connected to a weakening of the notion of a uniform homomorphism. Using this language of metrics and the machinery of Slaman and Steel for proving the universality of arithmetic equivalence, we construct an example of a homomorphism between equivalence relations coarser than Turing equivalence which is not uniform on any pointed perfect set. This is the first example of a nonuniform homomorphism in this sort of recursion-theoretic context, and it places some limits on how abstract a proof of Martin's conjecture could be.

In Chapter 5, we turn to the question of whether recursive isomorphism is a universal countable Borel equivalence relation. Improving prior results of Dougherty and Kechris and Andretta, Camerlo, and Hjorth, we show that recursive isomorphism on $3^\omega$ is a universal countable Borel equivalence relation. We isolate a question of Borel combinatorics for which a positive answer would imply that recursive isomorphism on $2^\omega$ is universal. We show that this question is equivalent to the problem of whether $\omega$ many 2-regular Borel graphs on the same space can be simultaneously Borel 3-colored so that there are no monochromatic points. We then show that this question has an affirmative answer if and only if many-one equivalence on $2^\omega$ is a uniformly universal countable Borel equivalence relation. Thus, we have an exact combinatorial calibration of the difficulty of this universality problem.

In Chapter 6, we consider the question of whether there exist disjoint Borel complete sections for every pair of aperiodic countable Borel equivalence relations. We show that this question is very robust, and has many equivalent formulations. A positive answer to this question would positively answer the combinatorial question of the previous paragraph, while a negative answer would settle several open questions of Borel combinatorics. We also show that this question is true in both the measure and category context, in all its equivalent forms. One application of this fact is that every Borel bipartite 3-regular graph has measurable and Baire measurable edge colorings with 4 colors. This is a descriptive analogue of a special case of Vizing's theorem on edge colorings from classical combinatorics. Finally, we see that recursive isomorphism on $2^\omega$ is measure universal. Thus, purely measure-theoretic tools cannot be used to prove that it is not universal.