The complexity of computable categoricity
Downey, R. G., Kach, A. M., Lempp, S., Lewis-Pye, A., Montalbán, A. & Turetsky, D. D.
(2015).
The complexity of computable categoricity.
Advances in Mathematics,
268, 423-466.
https://doi.org/10.1016/j.aim.2014.09.022
We show that the index set complexity of the computably categorical structures is View the MathML source-complete, demonstrating that computable categoricity has no simple syntactic characterization. As a consequence of our proof, we exhibit, for every computable ordinal α , a computable structure that is computably categorical but not relatively View the MathML source-categorical.
| Item Type | Article |
|---|---|
| Copyright holders | © 2014 Elsevier Inc. |
| Departments | LSE |
| DOI | 10.1016/j.aim.2014.09.022 |
| Date Deposited | 27 Feb 2017 |
| URI | https://researchonline.lse.ac.uk/id/eprint/69570 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Andrew-Lewis-Pye.aspx (Author)
- https://www.scopus.com/pages/publications/84908191144 (Scopus publication)
- https://www.journals.elsevier.com/advances-in-math... (Official URL)