TY - JOUR

T1 - Degrees of categoricity and spectral dimension

AU - Bazhenov, Nikolay A.

AU - Kalimullin, Iskander S.H.

AU - Yamaleev, Mars M.

N1 - Publisher Copyright: © 2018 The Association for Symbolic Logic. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2018/3/1

Y1 - 2018/3/1

N2 - A Turing degree d is the degree of categoricity of a computable structure S if d is the least degree capable of computing isomorphisms among arbitrary computable copies of S. A degree d is the strong degree of categoricity of S if d is the degree of categoricity of S, and there are computable copies A and B of S such that every isomorphism from A onto B computes d. In this paper, we build a c.e. degree d and a computable rigid structure Msuch that d is the degree of categoricity of M, but d is not the strong degree of categoricity of M. This solves the open problem of Fokina, Kalimullin, andMiller [13]. For a computable structure S, we introduce the notion of the spectral dimension of S, which gives a quantitative characteristic of the degree of categoricity of S. We prove that for a nonzero natural number N, there is a computable rigid structureMsuch that 0 is the degree of categoricity ofM, and the spectral dimension ofMis equal to N.

AB - A Turing degree d is the degree of categoricity of a computable structure S if d is the least degree capable of computing isomorphisms among arbitrary computable copies of S. A degree d is the strong degree of categoricity of S if d is the degree of categoricity of S, and there are computable copies A and B of S such that every isomorphism from A onto B computes d. In this paper, we build a c.e. degree d and a computable rigid structure Msuch that d is the degree of categoricity of M, but d is not the strong degree of categoricity of M. This solves the open problem of Fokina, Kalimullin, andMiller [13]. For a computable structure S, we introduce the notion of the spectral dimension of S, which gives a quantitative characteristic of the degree of categoricity of S. We prove that for a nonzero natural number N, there is a computable rigid structureMsuch that 0 is the degree of categoricity ofM, and the spectral dimension ofMis equal to N.

KW - categoricity spectrum

KW - computable categoricity

KW - degree of categoricity

KW - rigid structure

UR - http://www.scopus.com/inward/record.url?scp=85046365456&partnerID=8YFLogxK

U2 - 10.1017/jsl.2017.70

DO - 10.1017/jsl.2017.70

M3 - Article

AN - SCOPUS:85046365456

VL - 83

SP - 103

EP - 116

JO - Journal of Symbolic Logic

JF - Journal of Symbolic Logic

SN - 0022-4812

IS - 1

ER -