A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS

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 S, there ex...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 2018-03, Vol.83 (1), p.326-348
Main Authors: MILLER, RUSSELL, POONEN, BJORN, SCHOUTENS, HANS, SHLAPENTOKH, ALEXANDRA
Format: Article
Language:English
Subjects:
Logic
Mathematics
Philosophy
Structuralism
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 S, there exists a countable field F of arbitrary characteristic 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.
ISSN:0022-4812
1943-5886
DOI:10.1017/jsl.2017.50