# 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 https://doi.org/10.3233/COM-190289 Опубликовано - 2021