Friday, February 28, 20142:00 pmCUNY Logic WorkshopGC 6417

The theory of fields is complete for isomorphisms

Russell Miller

City University of New York

Russell Miller

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 properly joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh. The slides for the talk are available here.

Russell Miller is professor of mathematics at Queens College of CUNY and also at the CUNY Graduate Center.  He conducts research in mathematical logic, especially computability theory and its interaction with other areas of mathematics, as in computable model theory. He received his doctorate from the University of Chicago in 2000, as a student of Robert Soare, and subsequently held a postdoctoral position at Cornell University until 2003, when he came to CUNY.