Geodesic
The structure of computably enumerable preorder relations
Algebra i logika, Tome 59 (2020) no. 3, pp. 293-314

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the structure Ceprs induced by degrees of computably enumerable preorder relations with respect to computable reducibility $\leq_c$. It is proved that the structure of computably enumerable equivalence relations is definable in Ceprs. This fact and results of Andrews, Schweber, and Sorbi imply that the theory of the structure Ceprs is computably isomorphic to first-order arithmetic. It is shown that a $\Sigma_1$-fragment of the theory is decidable, while its $\Pi_3$-fragment is hereditarily undecidable. It is stated that any two incomparable degrees in Ceprs do not have a least upper bound, and that among minimal degrees in Ceprs, exactly two are $c$-degrees of computably enumerable linear preorders.
Keywords: computably enumerable preorder, computable reducibility, structure induced by degrees of computably enumerable preorder relations with respect to computable reducibility. 
@article{AL_2020_59_3_a1,
     author = {S. A. Badaev and N. A. Bazhenov and B. S. Kalmurzaev},
     title = {The structure of computably enumerable preorder relations},
     journal = {Algebra i logika},
     pages = {293--314},
     publisher = {mathdoc},
     volume = {59},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2020_59_3_a1/}
}
TY  - JOUR
AU  - S. A. Badaev
AU  - N. A. Bazhenov
AU  - B. S. Kalmurzaev
TI  - The structure of computably enumerable preorder relations
JO  - Algebra i logika
PY  - 2020
SP  - 293
EP  - 314
VL  - 59
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2020_59_3_a1/
LA  - ru
ID  - AL_2020_59_3_a1
ER  - 
%0 Journal Article
%A S. A. Badaev
%A N. A. Bazhenov
%A B. S. Kalmurzaev
%T The structure of computably enumerable preorder relations
%J Algebra i logika
%D 2020
%P 293-314
%V 59
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2020_59_3_a1/
%G ru
%F AL_2020_59_3_a1
S. A. Badaev; N. A. Bazhenov; B. S. Kalmurzaev. The structure of computably enumerable preorder relations. Algebra i logika, Tome 59 (2020) no. 3, pp. 293-314. http://geodesic.mathdoc.fr/item/AL_2020_59_3_a1/