A computable functor from graphs to fields
From MaRDI portal
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.
Recommendations
Cites work
- d-computable categoricity for algebraic fields
- Autostability of models
- Bounds on the number of automorphisms of curves over algebraically closed fields
- Complements à un article de Hans Grauert sur la conjecture de Mordell
- Computability theoretic classifications for classes of structures
- Computable categoricity for algebraic fields with splitting algorithms
- Computable categoricity of trees of finite height
- Computable functors and effective interpretability
- Computable structures and the hyperarithmetical hierarchy
- Computably categorical fields via Fermat's last theorem
- Degree spectra and computable dimensions in algebraic structures
- Degrees coded in jumps of orderings
- Degrees of categoricity of computable structures
- Degrees of orderings not isomorphic to recursive linear orderings
- Degrees of Structures
- Does the Frobenius endomorphism always generate a direct summand in the endomorphism monoids of fields of prime characteristic?
- Every Low Boolean Algebra is Isomorphic to a Recursive One
- scientific article; zbMATH DE number 3781440 (Why is no real title available?)
- scientific article; zbMATH DE number 3788909 (Why is no real title available?)
- scientific article; zbMATH DE number 42077 (Why is no real title available?)
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- Integral points on curves
- Non Σn axiomatizable almost strongly minimal theories
- Problem of the number of non-self-equivalent constructivizations
- Recursively Categorical Linear Orderings
- Simple structures with complex symmetry
- Spectra of structures and relations
- The complexity of computable categoricity
- The quantity of nonautoequivalent constructivizations
- Turing computable embeddings
- Varieties without extra automorphisms. III: Hypersurfaces
Cited in
(39)- Degree spectra of real closed fields
- Finitely generated groups are universal among finitely generated structures
- Primitive recursive fields and categoricity
- Computable transformations of structures
- Categoricity spectra of computable structures
- Degree spectra of structures
- Model completeness and relative decidability
- Computable embeddings for pairs of linear orders
- A note on computable embeddings for ordinals and their reverses
- Computable procedures for fields
- Positive enumerable functors
- Graphs are not universal for online computability
- Spectral universality of linear orders with one binary relation
- HKSS-completeness of modal algebras
- Constructing decidable graphs from decidable structures
- _1¹-completeness of the computable categoricity problem for projective planes
- Freely generated projective planes with finite computable dimension
- On functors enumerating structures
- Effective categoricity for distributive lattices and Heyting algebras
- Some Questions in Computable Mathematics
- There is no classification of the decidably presentable structures
- Torsion-free abelian groups with optimal Scott families
- DEGREE SPECTRA OF ANALYTIC COMPLETE EQUIVALENCE RELATIONS
- The tree of tuples of a structure
- COPYING ONE OF A PAIR OF STRUCTURES
- INTERPRETING A FIELD IN ITS HEISENBERG GROUP
- A structure of punctual dimension two
- Categoricity spectra for polymodal algebras
- CODING IN GRAPHS AND LINEAR ORDERINGS
- Categoricity properties for computable algebraic fields
- TURING DEGREE SPECTRA OF DIFFERENTIALLY CLOSED FIELDS
- Computable functors and effective interpretability
- PUNCTUAL CATEGORICITY AND UNIVERSALITY
- The theory of projective planes is complete with respect to degree spectra and effective dimensions
- On the effective universality of mereological theories
- Computable Heyting algebras with distinguished atoms and coatoms
- Classes of algebraic structures
- Universal-existential theories of fields
- Preserving categoricity and complexity of relations
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)
