On diagonal functions for equivalence relations.

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers ω , having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for Δ 2 0 equivalence relations, starting with the Π 2 - 1 level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree d , there exists a weakly precomplete c.e. equivalence E admitting a d -computable diagonal function. We observe that a Turing degree d can compute a diagonal function for every Δ 2 0 equivalence relation E if and only if d computes 0 ′ . On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if d computes diagonal functions for all c.e. E, then d must be a DNC degree. [ABSTRACT FROM AUTHOR]