TY - JOUR

T1 - On diagonal functions for equivalence relations

AU - Badaev, Serikzhan A.

AU - Bazhenov, Nikolay A.

AU - Kalmurzayev, Birzhan S.

AU - Mustafa, Manat

N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2023/10/18

Y1 - 2023/10/18

N2 - 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 Δ20 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 Δ20 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.

AB - 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 Δ20 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 Δ20 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.

KW - Computably enumerable equivalence relation

KW - Diagonal function

KW - DNC degree

KW - Ershov hierarchy

KW - Weakly precomplete equivalence

UR - http://www.scopus.com/inward/record.url?scp=85174419625&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85174419625&partnerID=8YFLogxK

U2 - 10.1007/s00153-023-00896-0

DO - 10.1007/s00153-023-00896-0

M3 - Article

AN - SCOPUS:85174419625

SN - 0933-5846

JO - Archive for Mathematical Logic

JF - Archive for Mathematical Logic

ER -