On diagonal functions for equivalence relations
Badaev S.A. Bazhenov N.A. Kalmurzayev B.S. Mustafa M.
May 2024Springer Science and Business Media Deutschland GmbH
Archive for Mathematical Logic
2024#63Issue 3-4259 - 278 pp.
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.
03D25 , 03D45 , 03D55 , Computably enumerable equivalence relation , Diagonal function , DNC degree , Ershov hierarchy , Weakly precomplete equivalence
Text of the article Перейти на текст статьи
Kazakh-British Technical University, 59 Tole Bi Street, Almaty, 050000, Kazakhstan
Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, Novosibirsk, 630090, Russian Federation
Al-Farabi Kazakh National University, 71 al Farabi Avenue, Almaty, 050040, Kazakhstan
Department of Mathematics, SSH, Nazarbayev University, 53 Qabanbay Batyr Avenue, Astana, 010000, Kazakhstan
Kazakh-British Technical University
Sobolev Institute of Mathematics
Al-Farabi Kazakh National University
Department of Mathematics
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026