Geodesic
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/}
}
TY  - JOUR
AU  - B. S. Kalmurzaev
AU  - N. A. Bazhenov
AU  - M. A. Torebekova
TI  - Index sets for classes of positive preorders
JO  - Algebra i logika
PY  - 2022
SP  - 42
EP  - 76
VL  - 61
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2022_61_1_a2/
LA  - ru
ID  - AL_2022_61_1_a2
ER  - 
%0 Journal Article
%A B. S. Kalmurzaev
%A N. A. Bazhenov
%A M. A. Torebekova
%T Index sets for classes of positive preorders
%J Algebra i logika
%D 2022
%P 42-76
%V 61
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2022_61_1_a2/
%G ru
%F 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/