Computable categoricity and the Ershov hierarchy

DOI10.1016/j.apal.2008.06.010zbMath1165.03012OpenAlexW1976898576MaRDI QIDQ958489

Bakhadyr Khoussainov, Yue Yang, Frank Stephan

Publication date: 5 December 2008

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2008.06.010

zbMATH Keywords

linear ordersgraphscategoricityErshov hierarchyrecursive ordinal

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Categoricity and completeness of theories (03C35)

Related Items (6)

The branching theorem and computable categoricity in the Ershov hierarchy ⋮ \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures ⋮ Isomorphism relations on computable structures ⋮ $\Sigma^0_1$ and $\Pi^0_1$ Equivalence Structures ⋮ Rogers semilattices for families of equivalence relations in the Ershov hierarchy ⋮ On Σ¹ ₁ equivalence relations over the natural numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Autostability of models
• On the role of procrastination in machine learning
• \(\Delta_{2}^{0}\)-categoricity in Boolean algebras and linear orderings
• Supersimple sets and the problem of extending a retracing function
• Equivalence structures and isomorphisms in the difference hierarchy
• Recursively Categorical Linear Orderings
• A proof of Beigel's cardinality conjecture
• Trial and error predicates and the solution to a problem of Mostowski
• Limiting recursion

This page was built for publication: Computable categoricity and the Ershov hierarchy