ON THE STRUCTURE OF PUNCTUAL LINEAR ORDERS ISOMORPHIC TO THE LEAST LIMIT ORDINAL

The algorithmic complexity of presentations for various structures receives significant attention in modern literature. The main tool for determining such complexities is reducibility. It is a mapping that preserves relations of signature (for example, equivalence relation, orders, and so on). This work is dedicated to the study of punctual representations of the least limit ordinal with respect to primitive recursive reducibility. We denote this structure as PR(ω). In particular, the paper examines the properties of structures Ω, consisting of computable copies of the least limit ordinal with respect to computable reducibility, and Peq, consisting of punctual equivalence relations with respect to primitive recursive reducibility. We say that the linear order L is reducible to the linear order R, if there exists a total function ρ such that (χ, γ) Є L if and only if (ρ(χ), ρ(γ)) Є R. Reducibility is called computable (primitive recursive) if the function that performs the reducibility is computable (primitive recursive). It is shown that the degree of ω is not the least degree in PR(ω), as it was in Ω. The structure PR(ω) does not contain maximal degrees, and this structure is not dense. Also, an example of an incomparable pair that has the least upper bound is given.

1. Kalimullin I., Melnikov, A. and Ng K.M. Algebraic structures computable without delay. Theoretical Computer Science, no. 674, 2017, pp. 73–98.

2. Bazhenov N., Ng K.M., San Mauro L. and Sorbi A. Primitive recursive equivalence relations and their primitive recursive complexity. Computability, no.11(3–4), 2022, pp. 187–221.

3. Ershov Y. L. Positive equivalences. Algebra i Logika, 10(6), 1971, 620–650.

4. Bernardi C. and Sorbi A. Classifying positive equivalence relations. J. Symb. Logic, no. 48(3), 1983, pp. 529–538.

5. Gao S. and Gerdes P. Computably enumerable equivalence relations. Studia Logica, no. 67(1), 2011, pp. 27–59.

6. Andrews U. and Sorbi A. Joins and meets in the structure of ceers. Computability, no. 8(3–4), 2019, pp. 193–241.

7. Askarbekkyzy A., Bazhenov N.A. and Kalmurzayev B.S. Computable Reducibility for Computable Linear Orders of Type ω. Journal of Mathematical Sciences, no. 267(4), 2022, pp. 429–443.

8. Bazhenov N.A., Kalmurzayev B.S. and Zubkov M.V. A note on joins and meets for positive linear preorders, Siberian Electronic Mathematical Reports, vol. 20, no. 1, 2023, pp. 1–16.

9. Askarbekkyzy A. and Bazhenov N.A. Index sets of self-full linear orders isomorphic to some standard orders. Herald of the Kazakh-British technical university. 2023;20(2):36–42. https://doi.org/10.55452/19986688-2023-20-2-36-42.

10. Bazhenov N., Downey R., Kalimullin I. and Melnikov A. Foundations of online structure theory. Bulletin of Symbolic Logic, no. 25(2), 2019, pp. 141–181.

11. Kabylzhanova D.K. On positive preorders. Algebra i Logica, no. 57(3), 2018, pp. 279–284 [in Russian].

12. Kuznecov A.V. On primitive recursive functions of large oscillation. Doklady Akademii Nauk SSSR, 71, 1950, pp. 233–236 [in Russian].

13. Paolini L., Piccolo M. and Roversi L. A class of reversible primitive recursive functions. Electronic Notes in Theoretical Computer Science, no. 322, 2016, pp. 227–242.