Computably enumerable equivalence relations via primitive recursive reductions.
Saved in:
| Title: | Computably enumerable equivalence relations via primitive recursive reductions. |
|---|---|
| Authors: | Kalmurzayev, Birzhan S1 (AUTHOR), Bazhenov, Nikolay A2 (AUTHOR), Iskakov, Alibek M1 (AUTHOR) |
| Source: | Journal of Logic & Computation. Mar2025, Vol. 35 Issue 2, p1-31. 31p. |
| Subjects: | Recursive functions, Natural numbers, Classification, Literature |
| Abstract: | 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 |$R$| and |$S$| on natural numbers, a total function |$f$| is a reduction from |$R$| to |$S$| if for arbitrary |$x$| and |$y$| , the conditions |$x~R~y$| and |$f(x)~S~f(y)$| are always equivalent. If the function |$f$| can be chosen primitive recursive, then we say that |$R$| is primitively recursively reducible to |$S$| , denoted by |$R \leq _{pr} S$|. We investigate the degree structure |$(\textbf {Ceers},\leq _{pr})$| of |$\leq _{pr}$| -degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that |$(\textbf {Ceers},\leq _{pr})$| is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of |$(\textbf {Ceers},\leq _{pr})$|. In particular, we prove that the set of equivalences that have only finitely many classes is definable in |$(\textbf {Ceers},\leq _{pr})$|. Finally, we show that the structure of |$\leq _{pr}$| -degrees of computably enumerable preorders has a hereditarily undecidable theory. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | 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 |$R$| and |$S$| on natural numbers, a total function |$f$| is a reduction from |$R$| to |$S$| if for arbitrary |$x$| and |$y$| , the conditions |$x~R~y$| and |$f(x)~S~f(y)$| are always equivalent. If the function |$f$| can be chosen primitive recursive, then we say that |$R$| is primitively recursively reducible to |$S$| , denoted by |$R \leq _{pr} S$|. We investigate the degree structure |$(\textbf {Ceers},\leq _{pr})$| of |$\leq _{pr}$| -degrees of ceers. We examine when pairs of incomparable degrees have an infimum and a supremum. In particular, we show that |$(\textbf {Ceers},\leq _{pr})$| is neither an upper semilattice nor a lower semilattice. We also study first-order definable subclasses of |$(\textbf {Ceers},\leq _{pr})$|. In particular, we prove that the set of equivalences that have only finitely many classes is definable in |$(\textbf {Ceers},\leq _{pr})$|. Finally, we show that the structure of |$\leq _{pr}$| -degrees of computably enumerable preorders has a hereditarily undecidable theory. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 0955792X |
| DOI: | 10.1093/logcom/exad082 |
