Geodesic
A note on joins and meets for positive linear preorders
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 1-16.

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

A positive preorder $R$ is linear if the corresponding quotient poset is linearly ordered. Following the recent advances in the studies of positive preorders, the paper investigates the degree structure Celps of positive linear preorders under computable reducibility. We prove that if a positive linear preorder $L$ is non-universal and the quotient poset of $L$ is infinite, then $L$ is a part of an infinite antichain inside Celps. For a pair $L,R$ from Celps, we obtain sufficient conditions for when the pair has neither join, nor meet (with respect to computable reducibility). We give an example of a pair from Celps that has a meet. Inside the substructure $\Omega$ of Celps containing only computable linear orders of order-type $\omega$, we build a pair that has a join inside $\Omega$.
Keywords: computable reducibility, computably enumerable preorder, positive linear preorder. 
@article{SEMR_2023_20_1_a0,
     author = {N. Bazhenov and B. Kalmurzayev and M. Zubkov},
     title = {A note on joins and meets for positive linear preorders},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1--16},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a0/}
}
TY  - JOUR
AU  - N. Bazhenov
AU  - B. Kalmurzayev
AU  - M. Zubkov
TI  - A note on joins and meets for positive linear preorders
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 1
EP  - 16
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a0/
LA  - en
ID  - SEMR_2023_20_1_a0
ER  - 
%0 Journal Article
%A N. Bazhenov
%A B. Kalmurzayev
%A M. Zubkov
%T A note on joins and meets for positive linear preorders
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 1-16
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a0/
%G en
%F SEMR_2023_20_1_a0
N. Bazhenov; B. Kalmurzayev; M. Zubkov. A note on joins and meets for positive linear preorders. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 1-16. http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a0/

[1] Yu.L. Ershov, “Positive equivalences”, Algebra Logic, 10 (1973), 378–394 | DOI | MR | Zbl

[2] Yu.L. Ershov, Theory of numerations, 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] A.H. Lachlan, “A note on positive equivalence relations”, Z. Math. Logik Grundlag. Math., 33:1 (1987), 43–46 | DOI | MR | Zbl

[6] 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, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, F. Rosamond, Springer, Cham, 2017, 418–451 | DOI | MR | Zbl

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

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

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

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

[11] U. Andrews, A. Sorbi, “Effective inseparability, lattices, and preordering relations”, Rev. Symb. Log., 14:4 (2021), 838–865 | DOI | MR | Zbl

[12] S.A. Badaev, B.S. Kalmurzayev, D.K. Kabylzhanova, K.Sh. Abeshev, “Universal positive preorders”, News of the National Academy of Sciences of the Republic of Kazakhstan. Physico-Mathematical Series, 6:322 (2018), 49–53 | MR

[13] S.A. Badaev, N.A. Bazhenov, B.S. Kalmurzaev, “On the structure of positive preorders”, Algebra Logic, 59:3 (2020), 201–215 | DOI | MR | Zbl

[14] S.A. Badaev, B.S. Kalmurzayev, N.K. Mukash, A.A. Khamitova, “Special classes of positive preorders”, Sib. Èlektron. Mat. Izv., 18:2 (2021), 1657–1666 | DOI | MR | Zbl

[15] A. Askarbekkyzy, N.A. Bazhenov, B.S. Kalmurzayev, “Computable reducibility for computable linear orders of type $\omega$”, J. Math. Sci., 267:4 (2022), 429–443 | DOI | MR

[16] C.J. Ash, J.F. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, 144, Elsevier, Amsterdam, 2000 | MR | Zbl

[17] J.G. Rosenstein, Linear orderings, Pure and Applied Mathematics, 98, Academic Press, New York, 1982 | MR | Zbl

[18] N.A. Bazhenov, B.S. Kalmurzaev, “On dark computably enumerable equivalence relations”, Sib. Math. J., 59:1 (2018), 22–30 | DOI | MR | Zbl

[19] V.S. Harizanov, “Turing degrees of certain isomorphic images of computable relations”, Ann. Pure Appl. Logic, 93:1-3 (1998), 103–113 | DOI | MR | Zbl