The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
The notion of computable reducibility between equivalence relations on the natural numbers provides a natural computable analogue of Borel reducibility.We investigate the computable reducibility hierarchy, comparing and contrasting it with the Borel reducibility hierarchy from descriptive set theory.Meanwhile, the notion of computable reducibility appears well suited for an analysis of …