TY - JOUR

T1 - Strong Degrees of Categoricity and Weak Density

AU - Bazhenov, N. A.

AU - Kalimullin, I. Sh

AU - Yamaleev, M. M.

N1 - Funding Information: The work was supported by the Russian Science Foundation, project no. 18-11-00028. Publisher Copyright: © 2020, Pleiades Publishing, Ltd. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/9

Y1 - 2020/9

N2 - It is well-known that every c.e. Turing degree is the degree of categoricity of a rigid structure. In this work we study the possibility of extension of this result to properly 2-c.e. degrees. We found a condition such that if a Δ02-degree is a degree of categoricity of a rigid structure and satisfies this condition then it must be c.e. Also we show that degrees of non-categoricity are dense in the c.e. degrees.

AB - It is well-known that every c.e. Turing degree is the degree of categoricity of a rigid structure. In this work we study the possibility of extension of this result to properly 2-c.e. degrees. We found a condition such that if a Δ02-degree is a degree of categoricity of a rigid structure and satisfies this condition then it must be c.e. Also we show that degrees of non-categoricity are dense in the c.e. degrees.

KW - computable isomorphism

KW - computably enumerable sets

KW - degree of categoricity

KW - rigid structure

KW - Turing degrees

KW - STABILITY

KW - COMPUTABLE CATEGORICITY

KW - SPECTRA

KW - RECURSIVE STRUCTURES

KW - AUTOSTABILITY

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

U2 - 10.1134/S1995080220090048

DO - 10.1134/S1995080220090048

M3 - Article

AN - SCOPUS:85095597282

VL - 41

SP - 1630

EP - 1639

JO - Lobachevskii Journal of Mathematics

JF - Lobachevskii Journal of Mathematics

SN - 1995-0802

IS - 9

ER -