Degrees of bi-embeddable categoricity

Abstract

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 $\mathcal{A}$ as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of $\mathcal{A}$; the degree of bi-embeddable categoricity of $\mathcal{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^{(\alpha )}$ for $\alpha$ a computable successor ordinal and $0^{(\lambda )}$ for $\lambda$ 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.

18 pages