Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Degrees of bi-embeddable categoricity of equivalence structures. / Bazhenov, Nikolay; Fokina, Ekaterina; Rossegger, Dino и др.
в: Archive for Mathematical Logic, Том 58, № 5-6, 01.08.2019, стр. 543-563.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Degrees of bi-embeddable categoricity of equivalence structures
AU - Bazhenov, Nikolay
AU - Fokina, Ekaterina
AU - Rossegger, Dino
AU - San Mauro, Luca
PY - 2019/8/1
Y1 - 2019/8/1
N2 - We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δα0 bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of Δα0 bi-embeddable categoricity and relative Δα0 bi-embeddable categoricity coincide for equivalence structures for α= 1 , 2 , 3. We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0, 0′, or 0′ ′. We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.
AB - We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δα0 bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of Δα0 bi-embeddable categoricity and relative Δα0 bi-embeddable categoricity coincide for equivalence structures for α= 1 , 2 , 3. We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0, 0′, or 0′ ′. We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.
KW - Bi-embeddability
KW - Computable categoricity
KW - Degrees of bi-embeddable categoricity
KW - Degrees of categoricity
KW - EQUIMORPHISM
UR - http://www.scopus.com/inward/record.url?scp=85055991720&partnerID=8YFLogxK
U2 - 10.1007/s00153-018-0650-3
DO - 10.1007/s00153-018-0650-3
M3 - Article
AN - SCOPUS:85055991720
VL - 58
SP - 543
EP - 563
JO - Archive for Mathematical Logic
JF - Archive for Mathematical Logic
SN - 0933-5846
IS - 5-6
ER -
ID: 17487761