A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS
Russell Miller, Bjorn Poonen, Hans Schoutens, Alexandra Shlapentokh · Journal of Symbolic Logic · 2018
Abstract Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure ${\cal S}$ , there exists a countable field ${\cal F}$ of arbitrary characteristic with the same essential computable-model-theoretic properties as ${\cal S}$ . Along the way, we develop a new “computable category theory”, and prove that our functor and its partially defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.