|
Algebra i logika, 2022, Volume 61, Number 1, Pages 42–76 DOI: https://doi.org/10.33048/alglog.2022.61.103
(Mi al2696)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Index sets for classes of positive preorders
B. S. Kalmurzaevab, N. A. Bazhenovc, M. A. Torebekovab a Al-Farabi Kazakh National University
b Kazakh-British Technical University
c Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
DOI:
https://doi.org/10.33048/alglog.2022.61.103
Abstract:
We study the complexity of index sets with respect to a universal computable numbering of the family of all positive preorders. Let $\leq_c$ be computable reducibility on positive preorders. For an arbitrary positive preorder $R$ such that the $R$-induced equivalence $\sim_R$ has infinitely many classes, the following results are obtained. The index set for preorders $P$ with $R\leq_c P$ is $\Sigma^0_3$-complete. A preorder $R$ is said to be self-full if the range of any computable function realizing the reduction $R\leq_c R$ intersects all $\sim_R$-classes. If $L$ is a non-self-full positive linear preorder, then the index set of preorders $P$ with $P\equiv_c L$ is $\Sigma^0_3$-complete. It is proved that the index set of self-full linear preorders is $\Pi^0_3$-complete.
Keywords:
positive preorder, positive equivalence, positive linear preorder, computable reducibility, index set.
Received: 28.07.2021 Revised: 07.06.2022
Citation:
B. S. Kalmurzaev, N. A. Bazhenov, M. A. Torebekova, “Index sets for classes of positive preorders”, Algebra Logika, 61:1 (2022), 42–76; Algebra and Logic, 61:1 (2022), 30–53
Linking options:
https://www.mathnet.ru/eng/al2696 https://www.mathnet.ru/eng/al/v61/i1/p42
|
|