Index sets for classes of positive preorders
Algebra i logika, Tome 61 (2022) no. 1, pp. 42-76
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{AL_2022_61_1_a2,
author = {B. S. Kalmurzaev and N. A. Bazhenov and M. A. Torebekova},
title = {Index sets for classes of positive preorders},
journal = {Algebra i logika},
pages = {42--76},
publisher = {mathdoc},
volume = {61},
number = {1},
year = {2022},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/AL_2022_61_1_a2/}
}
B. S. Kalmurzaev; N. A. Bazhenov; M. A. Torebekova. Index sets for classes of positive preorders. Algebra i logika, Tome 61 (2022) no. 1, pp. 42-76. http://geodesic.mathdoc.fr/item/AL_2022_61_1_a2/