The hierarchy of equivalence relations on the natural numbers under computable reducibility

Details The hierarchy of equivalence relations on the natural numbers under computable reducibility The hierarchy of equivalence relations on the natural numbers under computable reducibility

2011-09-15

arxiv.org/abs/1109.3375v3

Mathematics

Logic

To appear in Computability

Scientific paper

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 equivalence relations on the c.e.\ sets, and more specifically, on various classes of c.e.\ structures. This is a rich context with many natural examples, such as the isomorphism relation on c.e.\ graphs or on computably presented groups. Here, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remains.

Affiliated with

Also associated with

No associations

Rating

The hierarchy of equivalence relations on the natural numbers under computable reducibility does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The hierarchy of equivalence relations on the natural numbers under computable reducibility, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The hierarchy of equivalence relations on the natural numbers under computable reducibility will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-673542