On the Computational Content of the Theory of Borel Equivalence Relations

View/ Open
Date
2021-03-17MFO Scientific Program
Research in Pairs 2020Series
Oberwolfach Preprints;2021-06Author
Bazhenov, Nikolay
Monin, Benoit
San Mauro, Luca
Zamora, Rafael
Metadata
Show full item recordOWP-2021-06
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 $(\leqslant_T , \leqslant_{tt} , \leqslant_m , \leqslant_1 )$, (iii) the effectivization of the notion of hyperfiniteness.