О СТРУКТУРЕ ПУНКТУАЛЬНЫХ ЛИНЕЙНЫХ ПОРЯДКОВ ИЗОМОРФНЫХ НАИМЕНЬШЕМУ ПРЕДЕЛЬНОМУ ОРДИНАЛУ

Алгоритмическая сложность представлений различных структур является объектом значительного интереса в современной научной литературе. Основным инструментом исследования в данном контексте является сводимость. Это отображение, сохраняющее отношения сигнатуры (такие как отношение эквивалентности, порядка и так далее). Данная работа посвящена исследованию пунктуальных представлений наименьшего предельного ординала относительно примитивно рекурсивной сводимости, обозначим данную структуру через PR(ω). В частности, в работе исследуется выполнение свойств структур Ω, состоящей из вычислимых копий  относительно вычислимой сводимости и Peq, состоящей из пунктуальных отношений эквивалентности относительно примитивно рекурсивной сводимости. Говорим, что линейный порядок L сводится к линейному порядку R, если существует всюду определенная функция P такая, что (χ, γ) Є Lтогда и только тогда (ρ(χ), ρ(γ)) Є R. Сводимости называют вычислимыми (примитивно рекурсивными), если функция, осуществляющая сводимость, является вычислимой (примитивно рекурсивной). Показано, что степень стандартной копии порядка ω не является наименьшей в PR(ω), как это было в Ω. Структура PR(ω) не содержит главные и максимальные степени, и данная структура не является плотной. Также приводится пример несравнимой пары с наименьшей верхней гранью.

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.