Equivalence relations and infinite-time computable reductions

Effective Mathematics of the Uncountable, New York, August 2008

Abstract: Many classification problems can be thought of as an equivalence relations on $2^{\omega }$. For instance, any countable linear ordering on $\omega$ can be coded as an element of $2^{\omega }$, and the classification problem for countable linear orders can be identified with the isomorphism equivalence relation on these codes. If $E,F$ are equivalence relations on $2^{\omega }$, then a reduction from $E$ to $F$ is a function $f:2^{\omega }\to 2^{\omega }$ such that $xE{x}^{\prime }⟺f(x)Ff(x^{\prime })$.

If the reduction function is reasonably explicit, then we say that the classification problem up to $E$ is no more complicated than that up to $F$.

In the study of Borel equivalence relations one defines that $E{\le }_{B}F$ iff there exists a Borel reduction from $E$ to $F$. In this talk, we instead consider infinite-time Turing computable reductions. Such reductions are more powerful than Borel reductions; indeed any Borel function is infinite-time computable from a real parameter. It is then possible to use infinite-time computable reductions to analyze very natural equivalence relations which are beyond Borel in complexity.