Index Sets for Classes of Positive Preorders
Kalmurzayev B.S. Bazhenov N.A. Torebekova M.A.
March 2022Springer
Algebra and Logic
2022#61Issue 130 - 53 pp.
We study the complexity of index sets with respect to a universal computable numbering of the family of all positive preorders. Let ≤c be computable reducibility on positive preorders. For an arbitrary positive preorder R such that the R-induced equivalence ∼R has infinitely many classes, the following results are obtained. The index set for preorders P with R ≤c P is ∑30−complete. A preorder R is said to be self-full if the range of any computable function realizing the reduction R ≤c R intersects all ∼Rclasses. If L is a non-self-full positive linear preorder, then the index set of preorders P with P ≡c L is ∑30−complete. It is proved that the index set of self-full linear preorders is ∏30−complete.
computable reducibility , index set , positive equivalence , positive linear preorder , positive preorder
Text of the article Перейти на текст статьи
Al-Farabi Kazakh National University, Alma-Ata, Kazakhstan
Kazakh-British Technical University, Alma-Ata, Kazakhstan
Sobolev Institute of Mathematics, Novosibirsk, Russian Federation
Al-Farabi Kazakh National University
Kazakh-British Technical University
Sobolev Institute of Mathematics
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026