Computable functors and effective interpretability
From MaRDI portal
Abstract: Our main result is the equivalence of two notions of reducibility between structures. One is a syntactical notion which is an effective version of interpretability as in model theory, and the other one is a computational notion which is a strengthening of the well-known Medvedev reducibility. We extend our result to effective bi-interpretability and also to effective reductions between classes of structures.
Recommendations
Cites work
- A certain reducibility on admissible sets
- A computable functor from graphs to fields
- A fixed point for the jump operator on structures
- A Jump Inversion Theorem for the Degree Spectra
- Computability theoretic classifications for classes of structures
- Computable ordered abelian groups and fields
- Degree spectra and computable dimensions in algebraic structures
- Degrees of presentability of structures. I
- Degrees of presentability of structures. II
- Effective model theory vs. recursive model theory
- Generic copies of countable structures
- scientific article; zbMATH DE number 6536312 (Why is no real title available?)
- scientific article; zbMATH DE number 53151 (Why is no real title available?)
- scientific article; zbMATH DE number 890268 (Why is no real title available?)
- Model Theory
- Notes on the Jump of a Structure
- On Σ‐definability without equality over the real numbers
- Relations between algorithmic reducibilities of algebraic systems
- Rice sequences of relations
Cited in
(40)- Computable valued fields
- Degree spectra of real closed fields
- Computability of distributive lattices
- Finitely generated groups are universal among finitely generated structures
- Computable transformations of structures
- Turing computable embeddings, computable infinitary equivalence, and linear orders
- 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
- Positive enumerable functors
- Graphs are not universal for online computability
- Spectral universality of linear orders with one binary relation
- HKSS-completeness of modal algebras
- Categorical linearly ordered structures
- On functors enumerating structures
- Some Questions in Computable Mathematics
- scientific article; zbMATH DE number 3916232 (Why is no real title available?)
- scientific article; zbMATH DE number 4068864 (Why is no real title available?)
- Torsion-free abelian groups with optimal Scott families
- Some new computable structures of high rank
- A computable functor from graphs to fields
- BOREL FUNCTORS AND INFINITARY INTERPRETATIONS
- DEGREE SPECTRA OF ANALYTIC COMPLETE EQUIVALENCE RELATIONS
- The tree of tuples of a structure
- INTERPRETING A FIELD IN ITS HEISENBERG GROUP
- Jump inversions of algebraic structures and Σ‐definability
- A structure of punctual dimension two
- CODING IN GRAPHS AND LINEAR ORDERINGS
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- A computable structure with non-standard computability
- PUNCTUAL CATEGORICITY AND UNIVERSALITY
- On the effective universality of mereological theories
- Rigid differentially closed fields
- Failure modes for structural highness notions
- Relations enumerable from positive information
- Algorithmic transformations of partial orders into linearly ordered structures
- Étale structures and the Joyal-Tierney representation theorem in countable model theory
- On a computability-theoretic approach to Boolean-valued models
- On computability-theoretic universality of Boolean-valued models
This page was built for publication: Computable functors and effective interpretability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5738191)
