On the Computational Content of the Theory of Borel Equivalence Relations

Abstract

This preprint offers computational insights into the theory of Borel equivalence relations. Specifically, we classify equivalence relations on the Cantor space up to computable reductions, i.e., reductions induced by Turing functionals. The presented results correspond to three main research focuses: (i) the poset of degrees of equivalence relations on reals under computable reducibility; (ii) the complexity of the equivalence relations generated by computability-theoretic reducibilities (⩽T,⩽tt,⩽m,⩽1), (iii) the effectivization of the notion of hyperfiniteness.