Logic Seminar

Russell MillerCUNY
Computable reducibility on equivalence relations on Cantor space

Wednesday, May 10, 2017 - 4:00pm
Malott 206

We examine various versions of Borel reducibility on equivalence relations on the Cantor space $2^\omega$, using reductions given by Turing functionals on the inputs $A\in 2^\omega$. In some versions, we vary the number of jumps of $A$ which the functional is allowed to use. In others, we do not require the reduction to succeed for all elements of the Cantor space at once, but only when applied to arbitrary finite or countable subsets of $2^\omega$. These versions, inspired largely by work on computable reducibility on equivalence relations on $\omega$, yield a more informed understanding of the levels of difficulty of Borel reductions, or the reasons why a Borel reduction may fail to exist.

To apply this work, we consider equivalence relations on subsets of Cantor space defined using techniques from computable structure theory. One can consider, for example, those elements of $2^\omega$ which code atomic diagrams of countable fields, for example, or finite-branching trees. The isomorphism relation provides a natural equivalence relation on such subspaces, and we use the techniques above to analyze isomorphism on these classes of structures.