Degrees of bi-embeddable categoricity

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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)1-16
Number of pages16
JournalComputability
Volume10
Issue number1
DOIs
Publication statusPublished - 2021

Keywords

  • Bi-embeddability
  • categoricity
  • computable categoricity
  • computable structures

Fingerprint Dive into the research topics of 'Degrees of bi-embeddable categoricity'. Together they form a unique fingerprint.

Cite this