Degrees of bi-embeddable categoricity

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

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

Аннотация

We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure A as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of A; the degree of bi-embeddable categoricity of A is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and we show that every degree d.c.e above 0 ( α ) for α a computable successor ordinal and 0 ( λ ) for λ a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra.

Язык оригиналаанглийский
Страницы (с-по)1-16
Число страниц16
ЖурналComputability
Том10
Номер выпуска1
DOI
СостояниеОпубликовано - 2021

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

Цитировать