Graphings of arithmetical equivalence relations

Abstract

This paper studies when an arithmetical equivalence relation $E$ can be realized as the connectedness relation of a graph $G$ which is simpler to define than $E$. Several examples of such equivalence relations are established. In particular, it is proved that the $\hat{I}{\pounds }_3^0$ relation of computable isomorphism of structures on $\mathbb{N}$ in a computable first-order language is ${\hat{I}}_2^0$-graphable, i.e., is the connectedness relation of a ${\hat{I}}_2^0$ graph. Graphings of Friedman-Stanley jumps are studied, including an arithmetical construction of a graphing of the Friedman-Stanley jump of $E$ from a graphing of $E$.

25 pages