Categoricity spectra for rigid structures. (English) Zbl 1359.03030
Let \(\mathbf d\) be a Turing degree. We say that a computable structure is \(\mathbf d\)-categorical if each its computable isomorphic copy is isomorphic to it via a \(\mathbf d\)-computable isomorphism. The least such degree, if existing, is called the degree of categoricity of this structure. The authors prove that there exists a computable rigid structure with no degree of categoricity and that for every c.e. nonzero degree \(\mathbf x\), there exists an \(\mathbf x\)-computably categorical structure with no degree of categoricity.
Reviewer: Andrei S. Morozov (Novosibirsk)
MSC:
03C57 | Computable structure theory, computable model theory |
03D45 | Theory of numerations, effectively presented structures |
03C35 | Categoricity and completeness of theories |
03D28 | Other Turing degree structures |