Classifying equivalence relations in the Ershov hierarchy (Q2204368)

This article examines the behavior of \(\Delta^0_2\) equivalence relations with respect to computable reducibility \(\le_c\), considering the \(c\)-degrees at the various levels of the Ershov hierarchy. The authors discuss dark equivalence relations and introduce the stronger notion of a pair of ``mutually dark'' relations. They show that every level of the hierarchy, except for that of the co-ceers, contains mutually dark (and hence dark) relations. The paper also establishes several results on the existence and especially the non-existence of sups and infs of \(c\)-degrees. Mutually dark relations play an important role here as well.