On the structure of computable reducibility on equivalence relations of natural numbers

preprint2022arXivOpen access

Abstract

We examine the degree structure ER\mathbf{ER} of equivalence relations on ωω under computable reducibility. We examine when pairs of degrees have a join. In particular, we show that sufficiently incomparable pairs of degrees do not have a join but that some incomparable degrees do, and we characterize the degrees which have a join with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in ER\mathbf{ER}. We show that every equivalence relation has continuum many self-full strong minimal covers, and that d⊕Id1\mathbf{d}\oplus \mathbf{Id_1} needn't be a strong minimal cover of a self-full degree d\mathbf{d}. Finally, we show that the theory of the degree structure ER\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.