Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 949

Preprint Number 949

Previous Next Preprint server

949. Russell Miller, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh
A Computable Functor From Graphs to Fields

Submission date: 25 October 2015.


We construct a fully faithful functor from the category of graphs to the category of fields. Using this functor, we resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure S, there exists a countable field F with the same essential computable-model-theoretic properties as 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.

Mathematics Subject Classification: 03C57 (Primary) 03D45, 12L12, 18A15, 08A35 (Secondary)

Keywords and phrases:

Full text arXiv 1510.07322: pdf, ps.

Last updated: October 30 2015 15:06 Please send your corrections to: