Degrees of categoricity and spectral dimension

Standard

Degrees of categoricity and spectral dimension. / Bazhenov, Nikolay A.; Kalimullin, Iskander S.H.; Yamaleev, Mars M.

In: Journal of Symbolic Logic, Vol. 83, No. 1, 01.03.2018, p. 103-116.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, NA, Kalimullin, ISH & Yamaleev, MM 2018, 'Degrees of categoricity and spectral dimension', Journal of Symbolic Logic, vol. 83, no. 1, pp. 103-116. https://doi.org/10.1017/jsl.2017.70

APA

Bazhenov, N. A., Kalimullin, I. S. H., & Yamaleev, M. M. (2018). Degrees of categoricity and spectral dimension. Journal of Symbolic Logic, 83(1), 103-116. https://doi.org/10.1017/jsl.2017.70

Vancouver

Bazhenov NA, Kalimullin ISH, Yamaleev MM. Degrees of categoricity and spectral dimension. Journal of Symbolic Logic. 2018 Mar 1;83(1):103-116. doi: 10.1017/jsl.2017.70

Author

Bazhenov, Nikolay A. ; Kalimullin, Iskander S.H. ; Yamaleev, Mars M. / Degrees of categoricity and spectral dimension. In: Journal of Symbolic Logic. 2018 ; Vol. 83, No. 1. pp. 103-116.

BibTeX

@article{cd88c5d0c295412888e1b5479ff677a2,

title = "Degrees of categoricity and spectral dimension",

abstract = "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.",

keywords = "categoricity spectrum, computable categoricity, degree of categoricity, rigid structure",

author = "Bazhenov, {Nikolay A.} and Kalimullin, {Iskander S.H.} and Yamaleev, {Mars M.}",

year = "2018",

month = mar,

day = "1",

doi = "10.1017/jsl.2017.70",

language = "English",

volume = "83",

pages = "103--116",

journal = "Journal of Symbolic Logic",

issn = "0022-4812",

publisher = "Cambridge University Press",

number = "1",

}

RIS

TY - JOUR

T1 - Degrees of categoricity and spectral dimension

AU - Bazhenov, Nikolay A.

AU - Kalimullin, Iskander S.H.

AU - Yamaleev, Mars M.

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 -

ID: 13072386