Back to Search
Start Over
ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS.
- Source :
- Journal of Symbolic Logic; Sep2023, Vol. 88 Issue 3, p1038-1063, 26p
- Publication Year :
- 2023
-
Abstract
- We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn't be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00224812
- Volume :
- 88
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Journal of Symbolic Logic
- Publication Type :
- Academic Journal
- Accession number :
- 171373720
- Full Text :
- https://doi.org/10.1017/jsl.2022.28