The theory of fields is complete for isomorphisms

Abstract: We give a highly effective coding of countable graphs into countable fields.  For each countable graph G, we build a countable field F(G), uniformly effectively from an arbitrary presentation of G.  There is a uniform effective method of recovering the graph G from the field F(G).  Moreover, each isomorphism g from G onto any G' may be turned into an isomorphism F(g) from F(G) onto F(G'), again by a uniform effective method so that F(g) is computable from g. Likewise, an isomorphism f from F(G) onto any F(G') may be turned back into an isomorphism g with F(g)=f.  Not every field F isomorphic to F(G) is actually of the form F(G'), but for every such F,  there is a graph G' isomorphic to G and an isomorphism f from F onto F(G'), both computable in F.

It follows that many computable-model-theoretic properties which hold of some graph G will carry over to the field F(G), including spectra, categoricity spectra, automorphism spectra, computable dimension, and spectra of relations on the graph.  By previous work of Hirschfeldt, Khoussainov, Shore, and Slinko, all of these properties can be transferred from any other countable, automorphically nontrivial structure to a graph (and then to various other standard classes of structures), so our result may be viewed as saying that, like these other classes, fields are complete for such properties.

This work is joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh.