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.