Journal of Symbolic Logic 83 (1):326-348 (2018)

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 are computable functors.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2017.50
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,577
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

Computable Heyting Algebras with Distinguished Atoms and Coatoms.Nikolay Bazhenov - forthcoming - Journal of Logic, Language and Information:1-16.

View all 7 citations / Add more citations

Similar books and articles

Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
Domatic Partitions of Computable Graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2014 - Archive for Mathematical Logic 53 (1-2):137-155.
D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
Classifications of Computable Structures.Karen Lange, Russell Miller & Rebecca M. Steiner - 2018 - Notre Dame Journal of Formal Logic 59 (1):35-59.
Computable Categoricity and the Ershov Hierarchy.Bakhadyr Khoussainov, Frank Stephan & Yue Yang - 2008 - Annals of Pure and Applied Logic 156 (1):86-95.
Index Sets for Some Classes of Structures.Ekaterina B. Fokina - 2009 - Annals of Pure and Applied Logic 157 (2-3):139-147.
Torsion-Free Abelian Groups with Optimal Scott Families.Alexander G. Melnikov - 2018 - Journal of Mathematical Logic 18 (1):1850002.
Prime Models of Finite Computable Dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
Feasible Graphs with Standard Universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.
Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.


Added to PP index

Total views
13 ( #775,298 of 2,533,597 )

Recent downloads (6 months)
1 ( #389,998 of 2,533,597 )

How can I increase my downloads?


My notes