Degrees of categoricity above limit ordinals
Autor: | Michael Deveau, Mohammad Assem Mahmoud, Barbara F. Csima, Matthew Harrison-Trainor |
---|---|
Rok vydání: | 2020 |
Předmět: |
Physics
Degree (graph theory) 010102 general mathematics Successor ordinal Structure (category theory) Limit ordinal Mathematics - Logic 0102 computer and information sciences 01 natural sciences Omega Computer Science Applications Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Artificial Intelligence Prime model FOS: Mathematics Limit (mathematics) 0101 mathematics Logic (math.LO) |
Zdroj: | Computability. 9:127-137 |
ISSN: | 2211-3576 2211-3568 |
DOI: | 10.3233/com-190254 |
Popis: | A computable structure $\mathcal{A}$ has degree of categoricity $\mathbf{d}$ if $\mathbf{d}$ is exactly the degree of difficulty of computing isomorphisms between isomorphic computable copies of $\mathcal{A}$. 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. Comment: 14 pages |
Databáze: | OpenAIRE |
Externí odkaz: |