×

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.

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