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

DOI10.1017/JSL.2022.28MaRDI QIDQ6095972zbMATH OpenFDO

Authors Uri Andrews, Luca San Mauro

Publication date 11 September 2023

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

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

zbMATH Keywords

computable reducibilitycomputably enumerable equivalence relationscountable equivalence relationssecond-order arithmetic

Mathematics Subject Classification ID

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

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.

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 ^0_3 complete for computable reducibility (extended abstract)
• Finitary reducibility on equivalence relations
• Weakly precomplete equivalence relations in the Ershov hierarchy

Cites work

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

Cited in

(17)

• Computational completeness of equations over sets of natural numbers
• On the degree structure of equivalence relations under computable reducibility
• On Σ¹ ₁ equivalence relations over the natural numbers
• On notions of computability-theoretic reduction between Π21 principles
• scientific article; zbMATH DE number 4160710 (Why is no real title available?)
• Primitive recursive equivalence relations and their primitive recursive complexity
• ON RELATIVE COMPLETE REDUCIBILITY
• On \(p\)-reducibility of computable numerations
• Representations versus numberings: On the relationship of two computability notions
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• Logical specifications of effectively separable data models
• Finite logical specifications of effectively separable data models
• Computably enumerable equivalence relations via primitive recursive reductions
• Unoids with finiteness conditions over computably separable equivalences
• Analogues of the countable Borel equivalence relations in the setting of computable reducibility
• One question of the theory of numbered groups
• Computable structure theory of partial combinatory algebras

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)