Standard

Degrees of bi-embeddable categoricity. / Bazhenov, Nikolay; Fokina, Ekaterina; Rossegger, Dino et al.

In: Computability, Vol. 10, No. 1, 2021, p. 1-16.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, N, Fokina, E, Rossegger, D & San Mauro, L 2021, 'Degrees of bi-embeddable categoricity', Computability, vol. 10, no. 1, pp. 1-16. https://doi.org/10.3233/COM-190289

APA

Bazhenov, N., Fokina, E., Rossegger, D., & San Mauro, L. (2021). Degrees of bi-embeddable categoricity. Computability, 10(1), 1-16. https://doi.org/10.3233/COM-190289

Vancouver

Bazhenov N, Fokina E, Rossegger D, San Mauro L. Degrees of bi-embeddable categoricity. Computability. 2021;10(1):1-16. doi: 10.3233/COM-190289

Author

Bazhenov, Nikolay ; Fokina, Ekaterina ; Rossegger, Dino et al. / Degrees of bi-embeddable categoricity. In: Computability. 2021 ; Vol. 10, No. 1. pp. 1-16.

BibTeX

@article{f5aa10a4344a4efa927186321468eb72,
title = "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 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. ",
keywords = "Bi-embeddability, categoricity, computable categoricity, computable structures",
author = "Nikolay Bazhenov and Ekaterina Fokina and Dino Rossegger and {San Mauro}, Luca",
note = "Funding Information: N. Bazhenov was supported by Russian Science Foundation, project No. 18-11-00028. D. Rossegger was supported by RFBR, project no. 17-31-50026 mol_nr. E. Fokina was supported by the Austrian science fund FWF, project P 27527. L. San Mauro was supported by the Austrian science fund FWF, projects P 27527 and M 2461. Publisher Copyright: {\textcopyright} 2021-IOS Press. All rights reserved. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",
year = "2021",
doi = "10.3233/COM-190289",
language = "English",
volume = "10",
pages = "1--16",
journal = "Computability",
issn = "2211-3568",
publisher = "IOS Press BV",
number = "1",

}

RIS

TY - JOUR

T1 - Degrees of bi-embeddable categoricity

AU - Bazhenov, Nikolay

AU - Fokina, Ekaterina

AU - Rossegger, Dino

AU - San Mauro, Luca

N1 - Funding Information: N. Bazhenov was supported by Russian Science Foundation, project No. 18-11-00028. D. Rossegger was supported by RFBR, project no. 17-31-50026 mol_nr. E. Fokina was supported by the Austrian science fund FWF, project P 27527. L. San Mauro was supported by the Austrian science fund FWF, projects P 27527 and M 2461. Publisher Copyright: © 2021-IOS Press. All rights reserved. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Bi-embeddability

KW - categoricity

KW - computable categoricity

KW - computable structures

UR - http://www.scopus.com/inward/record.url?scp=85099947227&partnerID=8YFLogxK

U2 - 10.3233/COM-190289

DO - 10.3233/COM-190289

M3 - Article

AN - SCOPUS:85099947227

VL - 10

SP - 1

EP - 16

JO - Computability

JF - Computability

SN - 2211-3568

IS - 1

ER -

ID: 27640302