RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2022 Volume 61, Number 1, Pages 42–76 (Mi al2696)

This article is cited 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.

UDC: 510.5

Received: 28.07.2021
Revised: 07.06.2022

DOI: 10.33048/alglog.2022.61.103



© Steklov Math. Inst. of RAS, 2024