Graphings of arithmetical equivalence relations
Tyler Arant · arXiv (Cornell University) · 2025
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 $Σ^0_3$ relation of computable isomorphism of structures on $\N$ in a computable first-order language is $Π^0_2$-graphable, i.e., is the connectedness relation of a $Π^0_2$ 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$.