1 results
A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS
-
- Journal:
- The Journal of Symbolic Logic / Volume 83 / Issue 1 / March 2018
- Published online by Cambridge University Press:
- 01 May 2018, pp. 326-348
- Print publication:
- March 2018
-
- Article
- Export citation
-
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.
