Affiliations: [a] Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., Novosibirsk, 630090, Russia | [b] Novosibirsk State University, 2 Pirogova St., Novosibirsk, 630090, Russia. [email protected] | [c] Institute of Discrete Mathematics, Vienna University of Technology, Wiedner Hauptstrasse 8-10/104, 1040 Vienna, Austria. [email protected] | [d] Department of Pure Mathematics, University of Waterloo, 200 University Ave West, Waterloo, Ontario, Canada. [email protected] | [e] Institute of Discrete Mathematics, Vienna University of Technology, Wiedner Hauptstrasse 8-10/104, 1040 Vienna, Austria. [email protected]
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 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.
