Degrees of bi-embeddable categoricity of equivalence structures

Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger, Luca San Mauro

Результат исследования: Научные публикации в периодических изданияхстатья

2 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)543-563
Число страниц21
ЖурналArchive for Mathematical Logic
Том58
Номер выпуска5-6
DOI
СостояниеОпубликовано - 1 авг 2019

Fingerprint Подробные сведения о темах исследования «Degrees of bi-embeddable categoricity of equivalence structures». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать