Computably enumerable equivalence relations via primitive recursive reductions
Kalmurzayev B.S. Bazhenov N.A. Iskakov A.M.
1 March 2025Oxford University Press
Journal of Logic and Computation
2025#35Issue 2
The complexity classification of computably enumerable equivalence relations (or ceers, for short) has received much attention in the recent literature. A measure of complexity is typically provided by an appropriate notion of a reduction. Given binary relations and on natural numbers, a total function is a reduction from to if for arbitrary and, the conditions and are always equivalent. If the function can be chosen primitive recursive, then we say that is primitively recursively reducible to, denoted by. We investigate the degree structure of-degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of. In particular, we prove that the set of equivalences that have only finitely many classes is definable in. Finally, we show that the structure of-degrees of computably enumerable preorders has a hereditarily undecidable theory.
computable reducibility , Computably enumerable equivalence relation , computably enumerable preorder , primitive recursive function , primitive recursive reducibility
Text of the article Перейти на текст статьи
Kazakh-British Technical University, 59 Tole Bi Street, Almaty, 050000, Kazakhstan
Al-Farabi Kazakh National University, 71 al Farabi Avenue, Almaty, 050040, Kazakhstan
Kazakh-British Technical University
Al-Farabi Kazakh National University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026