On the degree structure of equivalence relations under computable reducibility

DOI10.1215/00294527-2019-0028zbMath1472.03039OpenAlexW2972719540MaRDI QIDQ2295742

Hongyuan Yu, Keng Meng Ng

Publication date: 14 February 2020

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.ndjfl/1568253623

zbMATH Keywords

equivalence relationsdensityuniversalitydegreeseffective enumerations

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45) Other Turing degree structures (03D28)

Related Items (6)

Primitive recursive equivalence relations and their primitive recursive complexity ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Classifying equivalence relations in the Ershov hierarchy ⋮ Minimal equivalence relations in hyperarithmetical and analytical hierarchies ⋮ Weakly precomplete equivalence relations in the Ershov hierarchy ⋮ Computable embeddability for algebraic structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Initial segments of one-one degrees
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY
• FINITARY REDUCIBILITY ON EQUIVALENCE RELATIONS
• A Borel reductibility theory for classes of countable structures
• Classifying positive equivalence relations
• Classification from a Computable Viewpoint
• Equivalence Relations on Classes of Computable Structures
• The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
• Comparing Classes of Finite Structures
• Computably enumerable equivalence relations

This page was built for publication: On the degree structure of equivalence relations under computable reducibility