Logic Seminar

A graphing of an equivalence relation E is a graph G whose connectivity equivalence relation is equal to E. In previous joint work with Alekos Kechris and Patrick Lutz, we studied analytic equivalence relations which have Borel graphings. In this talk, we will discuss new results about when arithmetical equivalence relations have definable graphings which are lower down in the arithmetical hierarchy. In particular, we will see that for any computable relational language L, computable isomorphism of L-structures presented on the natural numbers (a Σ^0_3 equivalence relation) has a Π^0_2 graphing. We will also prove a result on how to arithmetically construct a graphing of the Friedman-Stanley jump of E from a graphing of E.