|
This article is cited in 1 scientific paper (total in 1 paper)
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
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
Linking options:
https://www.mathnet.ru/eng/al2696 https://www.mathnet.ru/eng/al/v61/i1/p42
|
Statistics & downloads: |
Abstract page: | 126 | Full-text PDF : | 42 | References: | 22 | First page: | 6 |
|