ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS

DOI10.1017/JSL.2022.28arXiv2105.12534MaRDI QIDQ6095972FDOQ6095972

Authors: Uri Andrews, Luca San Mauro 

Publication date: 11 September 2023

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: We examine the degree structure $mathbfER$ of equivalence relations on $omega$ 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 $mathbfER$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $mathbfdoplusmathbfI{d}_1$ needn't be a strong minimal cover of a self-full degree $mathbfd$. Finally, we show that the theory of the degree structure $mathbfER$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second order arithmetic.

Full work available at URL: https://arxiv.org/abs/2105.12534

Recommendations

• On the degree structure of equivalence relations under computable reducibility
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)
• Finitary reducibility on equivalence relations
• Weakly precomplete equivalence relations in the Ershov hierarchy

zbMATH Keywords

second-order arithmeticcomputable reducibilitycomputably enumerable equivalence relationscountable equivalence relations

Mathematics Subject Classification ID

Quantum computation (81P68) Weak interaction in quantum theory (81V15) Hierarchies of computability and definability (03D55) Other degrees and reducibilities in computability and recursion theory (03D30) Recursive equivalence types of sets and structures, isols (03D50) Dark matter and dark energy (83C56)

Cites Work

• Invariant descriptive set theory
• Isomorphism relations on computable structures
• Borel equivalence relations
• Turing computability. Theory and applications
• First-order theory of the degrees of recursive unsolvability
• Definability in the enumeration degrees
• Title not available (Why is that?)
• Classifying positive equivalence relations
• Computably enumerable equivalence relations
• On the degree structure of equivalence relations under computable reducibility
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Title not available (Why is that?)
• Classifying equivalence relations in the Ershov hierarchy
• Universal computably enumerable equivalence relations
• A survey on universal computably enumerable equivalence relations
• The theory of ceers computes true arithmetic
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• Joins and meets in the structure of ceers
• Complexity of equivalence relations and preorders from computability theory
• Self-full ceers and the uniform join operator
• Measuring the complexity of reductions between equivalence relations
• Uniform Martin's conjecture, locally

Cited In (10)

• Title not available (Why is that?)
• Representations versus numberings: On the relationship of two computability notions
• On notions of computability-theoretic reduction between Π21 principles
• ON RELATIVE COMPLETE REDUCIBILITY
• Logical specifications of effectively separable data models
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• Computational completeness of equations over sets of natural numbers
• On Σ¹ ₁ equivalence relations over the natural numbers
• On the degree structure of equivalence relations under computable reducibility
• On \(p\)-reducibility of computable numerations

This page was built for publication: ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095972)