Degrees of bi-embeddable categoricity
Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger, Luca San Mauro · Computability · 2020
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 [Formula: see text] as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of [Formula: see text]; the degree of bi-embeddable categoricity of [Formula: see text] 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 [Formula: see text] for α a computable successor ordinal and [Formula: see text] 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.