Back to Search
Start Over
Degrees of bi-embeddable categoricity.
- Source :
-
Computability . 2021, Vol. 10 Issue 1, p1-16. 16p. - Publication Year :
- 2021
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ANALOGY
Subjects
Details
- Language :
- English
- ISSN :
- 22113568
- Volume :
- 10
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Computability
- Publication Type :
- Academic Journal
- Accession number :
- 148247331
- Full Text :
- https://doi.org/10.3233/COM-190289