Degrees of categoricity above limit ordinals

DOI10.3233/COM-190254zbMATH Open1485.03110arXiv1805.10249OpenAlexW2989591992MaRDI QIDQ5131645FDOQ5131645

Authors: Michael Deveau, Matthew Harrison-Trainor, Mohammad Assem Mahmoud, Barbara Csima 

Publication date: 9 November 2020

Published in: Computability (Search for Journal in Brave)

Abstract: A computable structure $mathcalA$ has degree of categoricity $mathbfd$ if $mathbfd$ is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of $mathcalA$. Fokina, Kalimullin, and Miller showed that every degree d.c.e. in and above $mathbf{0}^{(n)}$, for any $n<omega$, and also the degree $mathbf{0}^{(omega)}$, are degrees of categoricity. Later, Csima, Franklin, and Shore showed that every degree $mathbf{0}^{(alpha)}$ for any computable ordinal $alpha$, and every degree d.c.e. in and above $mathbf{0}^{(alpha)}$ for any successor ordinal $alpha$, is a degree of categoricity. We show that every degree c.e. in and above $mathbf{0}^{(alpha)}$, for $alpha$ a limit ordinal, is a degree of categoricity. We also show that every degree c.e. in and above $mathbf{0}^{(omega)}$ is the degree of categoricity of a prime model, making progress towards a question of Bazhenov and Marchuk.

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

Recommendations

• Degrees of categoricity and the hyperarithmetic hierarchy
• Categoricity in hyperarithmetical degrees
• Degrees of relations on ordinals
• Ordinals and Knuth-Bendix orders
• Infinite ordinals and finite improvement
• Countable categoricity
• A hierarchy of computably enumerable degrees
• Degrees of categoricity and spectral dimension
• A classification of ordinals up to Borel isomorphism
• Ordinal exponentiations of sets

zbMATH Keywords

limit ordinalsdegrees of categoricity

Mathematics Subject Classification ID

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

Cited In (10)

• On categoricity spectra for locally finite graphs
• Degrees of categoricity on a cone via \(\eta\)-systems
• A note on effective categoricity for linear orderings
• Strong degrees of categoricity and weak density
• Degrees of categoricity for prime and homogeneous models
• Degrees of categoricity and treeable degrees
• Degrees of categoricity and the hyperarithmetic hierarchy
• Every Δ20 degree is a strong degree of categoricity
• Degrees of categoricity of computable structures
• The property ``arithmetic-is-recursive on a cone

This page was built for publication: Degrees of categoricity above limit ordinals

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