Degrees of categoricity above limit ordinals

DOI10.3233/COM-190254MaRDI QIDQ5131645zbMATH OpenOpenAlexFDO

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

Publication date 9 November 2020

Published in Computability (Search for Journal in Brave)

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

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)

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.

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

Cited in

(10)

• On categoricity spectra for locally finite graphs
• The property ``arithmetic-is-recursive on a cone
• 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

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)