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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Cambridge University Press (CUP)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116051 https://orcid.org/0000-0002-8593-2792 |
| 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. 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. |
|---|