Degrees of bi-embeddable categoricity of equivalence structures

Archive for Mathematical Logic 58 (5-6):543-563 (2019)
  Copy   BIBTEX

Abstract

We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ 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 \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, or \. We furthermore obtain results on the index set complexity of computable equivalence structure with respect to bi-embeddability.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,271

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
On the complexity of categoricity in computable structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
Categoricity Spectra for Polymodal Algebras.Nikolay Bazhenov - 2016 - Studia Logica 104 (6):1083-1097.
Effective algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.
On MODkP Counting Degrees.Masamitsu Ozaki & Juichi Shinoda - 1999 - Mathematical Logic Quarterly 45 (3):327-342.
Categoricity and Mathematical Knowledge.Fernando Ferreira - 2017 - Revista Portuguesa de Filosofia 73 (3-4):1423-1436.
A Real Number Structure that is Effectively Categorical.Peter Hertling - 1999 - Mathematical Logic Quarterly 45 (2):147-182.

Analytics

Added to PP
2018-11-01

Downloads
32 (#483,225)

6 months
8 (#341,144)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Luca San Mauro
Università degli Studi di Roma La Sapienza