Degrees of categoricity on a Cone via η-systems

Journal of Symbolic Logic 82 (1):325-346 (2017)
  Copy   BIBTEX

Abstract

We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity of computing an isomorphism between the given structure and another copy${\cal B}$in the cone is a c.e. degree in${\rm{\Delta }}_\alpha ^0\left$. In each of our theorems the cone in question is clearly described in the beginning of the proof, so it is easy to see how the theorems can be viewed as general theorems with certain effectiveness conditions.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,227

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
Internal Categoricity in Arithmetic and Set Theory.Jouko Väänänen & Tong Wang - 2015 - Notre Dame Journal of Formal Logic 56 (1):121-134.
On an application of categoricity.Alexander Paseau - 2005 - Proceedings of the Aristotelian Society 105 (3):411–415.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.
Speech Acts, Categoricity, and the Meanings of Logical Connectives.Ole Thomassen Hjortland - 2014 - Notre Dame Journal of Formal Logic 55 (4):445-467.
Categoricity in hyperarithmetical degrees.C. J. Ash - 1987 - Annals of Pure and Applied Logic 34 (1):1-14.
Categoricity and indefinite extensibility.James Walmsley - 2002 - Proceedings of the Aristotelian Society 102 (3):217–235.

Analytics

Added to PP
2017-03-26

Downloads
23 (#685,787)

6 months
5 (#648,432)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Generic copies of countable structures.Chris Ash, Julia Knight, Mark Manasse & Theodore Slaman - 1989 - Annals of Pure and Applied Logic 42 (3):195-205.
Stability of recursive structures in arithmetical degrees.C. J. Ash - 1986 - Annals of Pure and Applied Logic 32:113-135.
Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.

View all 11 references / Add more references