Publication:4638989

DOI10.1017/JSL.2017.50zbMATH Open1447.03005arXiv1510.07322OpenAlexW2964092600MaRDI QIDQ4638989FDOQ4638989

Hans Schoutens, Bjorn Poonen, Alexandra Shlapentokh, Russell Miller

Publication date: 2 May 2018

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: We construct a fully faithful functor from the category of graphs to the category of fields. Using this functor, we resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure S, there exists a countable field F 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.

Full work available at URL: https://arxiv.org/abs/1510.07322

zbMATH Keywords

fieldsgraphscompletenessfunctorcomputabilitycomputable model theory

Mathematics Subject Classification ID

Automorphisms and endomorphisms of algebraic structures (08A35) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Model theory of fields (12L12) Special properties of functors (faithful, full, etc.) (18A22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Autostability of models
• Computable structures and the hyperarithmetical hierarchy
• Computably categorical fields via Fermat's last theorem
• Computable categoricity of trees of finite height
• d-computable categoricity for algebraic fields
• Recursively Categorical Linear Orderings
• Turing computable embeddings
• Problem of the number of non-self-equivalent constructivizations
• Degrees of categoricity of computable structures
• Simple structures with complex symmetry
• Complements à un article de Hans Grauert sur la conjecture de Mordell
• Integral points on curves
• Every Low Boolean Algebra is Isomorphic to a Recursive One
• The complexity of computable categoricity
• Degree spectra and computable dimensions in algebraic structures
• Non Σ_n axiomatizable almost strongly minimal theories
• Degrees coded in jumps of orderings
• Degrees of Structures
• Degrees of orderings not isomorphic to recursive linear orderings
• The quantity of nonautoequivalent constructivizations
• Does the Frobenius endomorphism always generate a direct summand in the endomorphism monoids of fields of prime characteristic?
• Computable categoricity for algebraic fields with splitting algorithms
• Varieties without extra automorphisms. III: Hypersurfaces
• COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY
• Spectra of structures and relations
• Bounds on the number of automorphisms of curves over algebraically closed fields

Cited In (38)

• On the effective universality of mereological theories
• INTERPRETING A FIELD IN ITS HEISENBERG GROUP
• PUNCTUAL CATEGORICITY AND UNIVERSALITY
• Some Questions in Computable Mathematics
• COPYING ONE OF A PAIR OF STRUCTURES
• Classes of algebraic structures
• HKSS-completeness of modal algebras
• Degree spectra of real closed fields
• Computable Heyting algebras with distinguished atoms and coatoms
• Categoricity spectra of computable structures
• Effective categoricity for distributive lattices and Heyting algebras
• COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY
• Primitive recursive fields and categoricity
• Categoricity properties for computable algebraic fields
• Constructing decidable graphs from decidable structures
• \(\prod_1^1\)-completeness of the computable categoricity problem for projective planes
• Graphs are not universal for online computability
• TURING DEGREE SPECTRA OF DIFFERENTIALLY CLOSED FIELDS
• Computable procedures for fields
• Preserving categoricity and complexity of relations
• Model completeness and relative decidability
• Freely generated projective planes with finite computable dimension
• Computable embeddings for pairs of linear orders
• There is no classification of the decidably presentable structures
• DEGREE SPECTRA OF ANALYTIC COMPLETE EQUIVALENCE RELATIONS
• On functors enumerating structures
• CODING IN GRAPHS AND LINEAR ORDERINGS
• A note on computable embeddings for ordinals and their reverses
• Torsion-free abelian groups with optimal Scott families
• Degree spectra of structures
• Finitely generated groups are universal among finitely generated structures
• Positive enumerable functors
• Computable transformations of structures
• Categoricity spectra for polymodal algebras
• Spectral universality of linear orders with one binary relation
• THE TREE OF TUPLES OF A STRUCTURE
• A structure of punctual dimension two
• The theory of projective planes is complete with respect to degree spectra and effective dimensions

This page was built for publication: A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638989)