Degrees of bi-embeddable categoricity of equivalence structures

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

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)543-563
Number of pages21
JournalArchive for Mathematical Logic
Volume58
Issue number5-6
DOIs
Publication statusPublished - 1 Aug 2019

Keywords

  • Bi-embeddability
  • Computable categoricity
  • Degrees of bi-embeddable categoricity
  • Degrees of categoricity
  • EQUIMORPHISM

OECD FOS+WOS

  • 6.03.UA PHILOSOPHY
  • 1.01.QL LOGIC

Fingerprint

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

Cite this