ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
The Journal of Symbolic Logic · 2023-09 · 88 (3) · 1038-1063
DOI: 10.1017/jsl.2022.28 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Journal of Symbolic Logic, online erschienen am 12.04.2022. Verfasst von URI ANDREWS und 2 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 24 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
ANDREWS, U., BELIN, D. F., & MAURO, L. S. (2023). ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS. The Journal of Symbolic Logic, 88(3), 1038-1063. https://doi.org/10.1017/jsl.2022.28
Vancouver
ANDREWS U, BELIN DF, MAURO LS. ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS. The Journal of Symbolic Logic. 2023;88(3):1038-1063. doi:10.1017/jsl.2022.28
BibTeX
@article{ANDREWS2023,
author = {ANDREWS, URI and BELIN, DANIEL F. and MAURO, LUCA SAN},
title = {ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS},
journal = {The Journal of Symbolic Logic},
year = {2023},
volume = {88},
number = {3},
pages = {1038--1063},
doi = {10.1017/jsl.2022.28}
}
EUVIMED