Computable categoricity versus relative computable categoricity
Volume 221 / 2013
Fundamenta Mathematicae 221 (2013), 129-159
MSC: Primary 03C57.
DOI: 10.4064/fm221-2-2
Abstract
We study the notion of computable categoricity of computable structures, comparing it especially to the notion of relative computable categoricity and its relativizations. We show that every 1 decidable computably categorical structure is relatively $\Delta ^0_2$ categorical. We study the complexity of various index sets associated with computable categoricity and relative computable categoricity. We also introduce and study a variation of relative computable categoricity, comparing it to both computable categoricity and relative computable categoricity and its relativizations.
