DEGREES OF CATEGORICITY ON A CONE VIA eta-SYSTEMS

作者：Csima Barbara F^*; Harrison Trainor Matthew

来源：Journal of Symbolic Logic, 2017, 82(1): 325-346.

DOI：10.1017/jsl.2016.43

• computability theory
• computable structure theory
• degrees of categoricity
• natural structure
• on a cone

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 Delta(0)(alpha)-complete for some alpha. To prove this, we extend Montalban's eta-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 alpha and a cone in the Turing degrees such that the exact complexity of computing an isomorphism between the given structure and another copy B in the cone is a.c.e. degree in Delta(0)(alpha) (B). 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.

• 出版日期2017-3