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

Authors
Luca San Mauro
Università degli Studi di Roma La Sapienza
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.
Keywords No keywords specified (fix it)
Categories No categories specified
(categorize this paper)
ISBN(s)
DOI 10.1007/s00153-018-0650-3
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,295
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.

View all 10 references / Add more references

Citations of this work BETA

Add more citations

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 index
2018-11-01

Total views
21 ( #514,000 of 2,448,749 )

Recent downloads (6 months)
1 ( #447,034 of 2,448,749 )

How can I increase my downloads?

Downloads

My notes