On diagonal functions for equivalence relations

Serikzhan A. Badaev, Nikolay A. Bazhenov, Birzhan S. Kalmurzayev, Manat Mustafa

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
JournalArchive for Mathematical Logic
Publication statusAccepted/In press - Oct 18 2023


  • Computably enumerable equivalence relation
  • Diagonal function
  • DNC degree
  • Ershov hierarchy
  • Weakly precomplete equivalence

ASJC Scopus subject areas

  • Philosophy
  • Logic


Dive into the research topics of 'On diagonal functions for equivalence relations'. Together they form a unique fingerprint.

Cite this