The complexity of computable categoricity

DOI10.1016/J.AIM.2014.09.022zbMATH Open1345.03063OpenAlexW2009042084MaRDI QIDQ471691FDOQ471691

Steffen Lempp, Andrew E. M. Lewis, Antonio Montalbán, Daniel Turetsky, Asher M. Kach, Rodney G. Downey

Publication date: 17 November 2014

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2014.09.022

Recommendations

• Computable categoricity versus relative computable categoricity
• Categoricity properties for computable algebraic fields
• Index sets for \(n\)-decidable structures categorical relative to \(m\)-decidable presentations
• Computability-theoretic categoricity and Scott families
• Degrees of categoricity of computable structures

zbMATH Keywords

computable categoricity

Mathematics Subject Classification ID

Categoricity and completeness of theories (03C35) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Cites Work

• Title not available (Why is that?)
• Autostability of models and Abelian groups
• Autostability of models
• Computable structures and the hyperarithmetical hierarchy
• The computable dimension of ordered abelian groups
• Subspaces of computable vector spaces
• Computably categorical fields via Fermat's last theorem
• Computable categoricity of trees of finite height
• Computable Categoricity of Graphs with Finite Components
• Title not available (Why is that?)
• CONSTRUCTIVE ALGEBRAS I
• Effective procedures in field theory
• Title not available (Why is that?)
• Computable Algebra, General Theory and Theory of Computable Fields
• Enumerations in computable structure theory
• Intrinsic bounds on complexity and definability at limit levels
• Incompleteness along paths in progressions of theories
• The isomorphism problem for torsion-free abelian groups is analytic complete
• Categoricity in hyperarithmetical degrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of categoricity in computable structures
• Title not available (Why is that?)
• Computable categoricity versus relative computable categoricity
• Intrinsically Hyperarithmetical Sets

Cited In (42)

• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Category and Measure in Complexity Classes
• PUNCTUAL CATEGORICITY AND UNIVERSALITY
• Relativizing computable categoricity
• Finite computable dimension and degrees of categoricity
• Computable bi-embeddable categoricity
• The index set of the groups autostable relative to strong constructivizations
• HKSS-completeness of modal algebras
• Complexity of categorical theories with computable models
• Computable Heyting algebras with distinguished atoms and coatoms
• Categoricity spectra of computable structures
• The complexity of countable categoricity in finite languages
• A note on decidable categoricity and index sets
• Complexity of hyperconcepts
• Decidable categoricity spectra for almost prime models
• Computable torsion abelian groups
• Индексное множество автоустойчивых упорядоченных абелевых групп
• Punctual categoricity relative to a computable oracle
• \(\prod_1^1\)-completeness of the computable categoricity problem for projective planes
• Solving the Caesar problem without categorical sortals
• Punctual definability on structures
• Categorical linearly ordered structures
• AN INTRODUCTION TO THE SCOTT COMPLEXITY OF COUNTABLE STRUCTURES AND A SURVEY OF RECENT RESULTS
• A Note on Effective Categoricity for Linear Orderings
• On a question of Kalimullin
• Intrinsic bounds on complexity and definability at limit levels
• Index sets for \(n\)-decidable structures categorical relative to \(m\)-decidable presentations
• Title not available (Why is that?)
• There is no classification of the decidably presentable structures
• Computable categoricity and the Ershov hierarchy
• A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS
• Torsion-free abelian groups with optimal Scott families
• Degrees of bi-embeddable categoricity
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Index sets of autostable relative to strong constructivizations constructive models for familiar classes
• Decomposing the complexity quotient category
• Categoricity spectra for polymodal algebras
• DEGREES OF CATEGORICITY ON A CONE VIAη-SYSTEMS
• Fundamentals of Computation Theory
• On the virtue of categoricity
• Coding in the automorphism group of a computably categorical structure
• THE TREE OF TUPLES OF A STRUCTURE

This page was built for publication: The complexity of computable categoricity

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