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/

[1] Yu. L. Ershov, “Pozitivnye ekvivalentnosti”, Algebra i logika, 10:6 (1971), 620–650 | MR

[2] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR

[3] C. Bernardi, “On the relation provable equivalence and on partitions in effectively inseparable sets”, Stud. Log., 40:1 (1981), 29–37 | DOI | MR | Zbl

[4] C. Bernardi, A. Sorbi, “Classifying positive equivalence relations”, J. Symb. Log., 48:3 (1983), 529–538 | DOI | MR | Zbl

[5] S. Gao, P. Gerdes, “Computably enumerable equivalence relations”, Stud. Log., 67:1 (2001), 27–59 | DOI | MR | Zbl

[6] U. Andrews, A. Sorbi, “Joins and meets in the structure of ceers”, Computability, 8:3/4 (2019), 193–241 | DOI | MR | Zbl

[7] U. Andrews, A. Sorbi, “Jumps of computably enumerable equivalence relations”, Ann. Pure Appl. Logic, 169:3 (2018), 243–259 | DOI | MR | Zbl

[8] U. Andrews, N. Schweber, A. Sorbi, “The theory of ceers computes true arithmetic”, Ann. Pure Appl. Logic, 171:8 (2020), 102811, 22 pp. | DOI | MR | Zbl

[9] U. Andrews, S. Lempp, J. S. Miller, K. M. Ng, L. S. Mauro, A. Sorbi, “Universal computably enumerable equivalence relations”, J. Symb. Log., 79:1 (2014), 60–88 | DOI | MR | Zbl

[10] U. Andrews, S. Badaev, A. Sorbi, “A survey on universal computably enumerable equivalence relations”, Computability and complexity, Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday, Lect. Notes Comput. Sci., 10010, eds. A. Day et al., Springer, Cham, 2017, 418–451 | DOI | MR | Zbl

[11] S. Badaev, A. Sorbi, “Weakly precomplete computably enumerable equivalence relations”, Math. Log. Q., 62:1/2 (2016), 111–127 | DOI | MR | Zbl

[12] J. C. Rosenstein, Linear orderings, Pure Appl. Math., 98, Academic Press, New York etc., 1982 | MR | Zbl

[13] N. A. Bazhenov, B. S. Kalmurzaev, “O temnykh vychislimo perechislimykh otnosheniyakh ekvivalentnosti”, Sib. matem. zh., 59:1 (2018), 29–40 | MR | Zbl

[14] A. H. Lachlan, “Initial segments of one-one degrees”, Pac. J. Math., 29:2 (1969), 351–366 | DOI | MR | Zbl

[15] P. G. Odifreddi, Classical recursion theory, v. II, Stud. Log. Found. Math., 143, Elsevier, Amsterdam, 1999 | MR | Zbl