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 |
| _version_ | 1811085550157824000 |
|---|---|
| author | SHLAPENTOKH, ALEXANDRA Miller, Russell Schoutens, Hans Schoustens, Hans Shlapentokh, Alexandra Poonen, Bjorn |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics SHLAPENTOKH, ALEXANDRA Miller, Russell Schoutens, Hans Schoustens, Hans Shlapentokh, Alexandra Poonen, Bjorn |
| author_sort | SHLAPENTOKH, ALEXANDRA |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:11:22Z |
| format | Article |
| id | mit-1721.1/116051 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:11:22Z |
| publishDate | 2018 |
| publisher | Cambridge University Press (CUP) |
| record_format | dspace |
| spelling | mit-1721.1/1160512022-10-01T13:38:49Z A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS SHLAPENTOKH, ALEXANDRA Miller, Russell Schoutens, Hans Schoustens, Hans Shlapentokh, Alexandra Poonen, Bjorn Massachusetts Institute of Technology. Department of Mathematics Poonen, Bjorn 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. National Science Foundation (U.S.) (Grant DMS-1069236) 2018-06-04T15:04:36Z 2018-06-04T15:04:36Z 2018-05 2015-10 2018-05-29T17:23:47Z Article http://purl.org/eprint/type/JournalArticle 0022-4812 1943-5886 http://hdl.handle.net/1721.1/116051 MILLER, RUSSELL et al. “A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS.” The Journal of Symbolic Logic 83, 1 (March 2018): 326–348 © 2018 The Association for Symbolic Logic https://orcid.org/0000-0002-8593-2792 http://dx.doi.org/10.1017/jsl.2017.50 The Journal of Symbolic Logic Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Cambridge University Press (CUP) arXiv |
| spellingShingle | SHLAPENTOKH, ALEXANDRA Miller, Russell Schoutens, Hans Schoustens, Hans Shlapentokh, Alexandra Poonen, Bjorn A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS |
| title | A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS |
| title_full | A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS |
| title_fullStr | A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS |
| title_full_unstemmed | A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS |
| title_short | A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS |
| title_sort | computable functor from graphs to fields |
| url | http://hdl.handle.net/1721.1/116051 https://orcid.org/0000-0002-8593-2792 |
| work_keys_str_mv | AT shlapentokhalexandra acomputablefunctorfromgraphstofields AT millerrussell acomputablefunctorfromgraphstofields AT schoutenshans acomputablefunctorfromgraphstofields AT schoustenshans acomputablefunctorfromgraphstofields AT shlapentokhalexandra acomputablefunctorfromgraphstofields AT poonenbjorn acomputablefunctorfromgraphstofields AT shlapentokhalexandra computablefunctorfromgraphstofields AT millerrussell computablefunctorfromgraphstofields AT schoutenshans computablefunctorfromgraphstofields AT schoustenshans computablefunctorfromgraphstofields AT shlapentokhalexandra computablefunctorfromgraphstofields AT poonenbjorn computablefunctorfromgraphstofields |