Standard

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

In: Archive for Mathematical Logic, Vol. 58, No. 5-6, 01.08.2019, p. 543-563.

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

Harvard

Bazhenov, N, Fokina, E, Rossegger, D & San Mauro, L 2019, 'Degrees of bi-embeddable categoricity of equivalence structures', Archive for Mathematical Logic, vol. 58, no. 5-6, pp. 543-563. https://doi.org/10.1007/s00153-018-0650-3

APA

Bazhenov, N., Fokina, E., Rossegger, D., & San Mauro, L. (2019). Degrees of bi-embeddable categoricity of equivalence structures. Archive for Mathematical Logic, 58(5-6), 543-563. https://doi.org/10.1007/s00153-018-0650-3

Vancouver

Bazhenov N, Fokina E, Rossegger D, San Mauro L. Degrees of bi-embeddable categoricity of equivalence structures. Archive for Mathematical Logic. 2019 Aug 1;58(5-6):543-563. doi: 10.1007/s00153-018-0650-3

Author

Bazhenov, Nikolay ; Fokina, Ekaterina ; Rossegger, Dino et al. / Degrees of bi-embeddable categoricity of equivalence structures. In: Archive for Mathematical Logic. 2019 ; Vol. 58, No. 5-6. pp. 543-563.

BibTeX

@article{328e237932e74d6d985336821a3caddc,
title = "Degrees of bi-embeddable categoricity of equivalence structures",
abstract = "We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δα0 bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of Δα0 bi-embeddable categoricity and relative Δα0 bi-embeddable categoricity coincide for equivalence structures for α= 1 , 2 , 3. We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0, 0′, or 0′ ′. We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.",
keywords = "Bi-embeddability, Computable categoricity, Degrees of bi-embeddable categoricity, Degrees of categoricity, EQUIMORPHISM",
author = "Nikolay Bazhenov and Ekaterina Fokina and Dino Rossegger and {San Mauro}, Luca",
year = "2019",
month = aug,
day = "1",
doi = "10.1007/s00153-018-0650-3",
language = "English",
volume = "58",
pages = "543--563",
journal = "Archive for Mathematical Logic",
issn = "0933-5846",
publisher = "Springer Nature",
number = "5-6",

}

RIS

TY - JOUR

T1 - Degrees of bi-embeddable categoricity of equivalence structures

AU - Bazhenov, Nikolay

AU - Fokina, Ekaterina

AU - Rossegger, Dino

AU - San Mauro, Luca

PY - 2019/8/1

Y1 - 2019/8/1

N2 - We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δα0 bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of Δα0 bi-embeddable categoricity and relative Δα0 bi-embeddable categoricity coincide for equivalence structures for α= 1 , 2 , 3. We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0, 0′, or 0′ ′. We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.

AB - We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) Δα0 bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of Δα0 bi-embeddable categoricity and relative Δα0 bi-embeddable categoricity coincide for equivalence structures for α= 1 , 2 , 3. We also prove that computable equivalence structures have degree of bi-embeddable categoricity 0, 0′, or 0′ ′. We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.

KW - Bi-embeddability

KW - Computable categoricity

KW - Degrees of bi-embeddable categoricity

KW - Degrees of categoricity

KW - EQUIMORPHISM

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

U2 - 10.1007/s00153-018-0650-3

DO - 10.1007/s00153-018-0650-3

M3 - Article

AN - SCOPUS:85055991720

VL - 58

SP - 543

EP - 563

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

SN - 0933-5846

IS - 5-6

ER -

ID: 17487761