A NOTE ON THE STRUCTURE OF MINIMAL DARK CEERS

О СТРУКТУРЕ МИНИМАЛЬНЫХ ТЕМНЫХ ВЫЧИСЛИМО ПЕРЕЧИСЛИМЫХ ОТНОШЕНИЙ ЭКВИВАЛЕНТНОСТИ
Badaev S.A. Iskakov A.M. Kalmurzayev B.S. Askarbekkyzy A.
2025 Kazakh-British Technical University

Herald of the Kazakh British Technical UNiversity
2025 #22 Issue 3 199 - 209 pp.

The structure of computably enumerable equivalence relations under computable reducibility (commonly referred to as ceers) has been actively developed over the past 25 years. A comprehensive survey by Andrews and Sorbi presented numerous structural properties of ceers, most notably investigating the existence of joins and meets in the degree structure of ceers. They divided the structure into two definable parts: dark ceers (ceers without an effective transversal) and light ceers (ceers with an effective transversal). They also showed the existence of an infinite number of minimal dark ceers (modulo equivalence relations with finitely many classes). Minimal dark ceers exhibit the distinctive property that every pair of classes is computably inseparable. Furthermore, the classes of weakly precomplete equivalence relations (i.e. those that lack a computable diagonal functions) are also computably inseparable. In this context, a natural question arises: do minimal dark equivalence relations exist that are not weakly precomplete? This paper provides an affirmative answer to this question. Moreover, we establish the existence of an infinite family of non-weakly precomplete minimal dark ceers that avoids lower cone of a given non-universal ceer. We denote by the set of ceers consisting of only finite classes. Andrews, Schweber, Sorbi showed the existence of dark equivalences. In this paper, we prove that over any dark ceer, there exists an infinite antichain of dark ceers.

computable reducibility , computably enumerable equivalence relation , Equivalence relation , weakly precomplete equivalence relation

Text of the article Перейти на текст статьи

Kazakh-British Technical University, Almaty, Kazakhstan

Kazakh-British Technical University

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026