On functors enumerating structures

DOI10.17377/SEMI.2017.14.059MaRDI QIDQ2403649zbMATH OpenFDO

Authors Dino Rossegger

Publication date 11 September 2017

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

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

zbMATH Keywords

computable structurescomputable structure theoryenumeration reducibilityenumerable functor

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Abstract: We study a new notion of reduction between structures called enumerable functors related to the recently investigated notion of computable functors. Our main result shows that enumerable functors and effective interpretability with the equivalence relation computable are equivalent. We also obtain results on the relation between enumerable and computable functors.

Recommendations

• Computable functors and effective interpretability
• scientific article; zbMATH DE number 218551
• Enumeration reducibility and computable structure theory
• A Friedberg enumeration of equivalence structures
• Comparing Classes of Finite Structures

Cites work

• scientific article; zbMATH DE number 6536312 (Why is no real title available?)
• scientific article; zbMATH DE number 695580 (Why is no real title available?)
• scientific article; zbMATH DE number 890268 (Why is no real title available?)
• A certain reducibility on admissible sets
• A computable functor from graphs to fields
• BOREL FUNCTORS AND INFINITARY INTERPRETATIONS
• Comparing Classes of Finite Structures
• Computability theoretic classifications for classes of structures
• Computable functors and effective interpretability
• 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
• Enumeration reducibility and computable structure theory
• Generic copies of countable structures
• On functors enumerating structures
• Relations between algorithmic reducibilities of algebraic systems
• Rice sequences of relations
• Turing computability. Theory and applications
• Turing computable embeddings
• Σ-Definability of countable structures over real numbers, complex numbers, and quaternions

Cited in

(7)

• A computable functor from graphs to fields
• Functorial approach structures
• Computable functors and effective interpretability
• Computable embeddings for pairs of linear orders
• On functors enumerating structures
• Positive enumerable functors
• scientific article; zbMATH DE number 218551 (Why is no real title available?)

This page was built for publication: On functors enumerating structures

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