<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">kaz29</journal-id><journal-title-group><journal-title xml:lang="ru">Вестник Казахстанско-Британского технического университета</journal-title><trans-title-group xml:lang="en"><trans-title>Herald of the Kazakh-British Technical University</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1998-6688</issn><issn pub-type="epub">2959-8109</issn><publisher><publisher-name>Казахстанско-Британский Технический Университет</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.55452/1998-6688-2024-21-1-94-102</article-id><article-id custom-type="elpub" pub-id-type="custom">kaz29-1026</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>МАТЕМАТИЧЕСКИЕ НАУКИ</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>MATHEMATICAL SCIENCES</subject></subj-group></article-categories><title-group><article-title>О  СТРУКТУРЕ  ПУНКТУАЛЬНЫХ  ЛИНЕЙНЫХ  ПОРЯДКОВ ИЗОМОРФНЫХ  НАИМЕНЬШЕМУ  ПРЕДЕЛЬНОМУ  ОРДИНАЛУ</article-title><trans-title-group xml:lang="en"><trans-title>ON  THE  STRUCTURE  OF  PUNCTUAL  LINEAR  ORDERS  ISOMORPHIC  TO  THE  LEAST  LIMIT  ORDINAL</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0003-0075-4438</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Аскарбеккызы</surname><given-names>А.</given-names></name><name name-style="western" xml:lang="en"><surname>Askarbekkyzy</surname><given-names>A.</given-names></name></name-alternatives><bio xml:lang="ru"><p>докторант</p><p>г. Алматы, 050000</p><p> </p></bio><bio xml:lang="en"><p>Doctoral student</p><p>Almaty, 050000</p></bio><email xlink:type="simple">ms.askarbekkyzy@gmail.com</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0009-0005-2550-2079</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Искаков</surname><given-names>А. М.</given-names></name><name name-style="western" xml:lang="en"><surname>Iskakov</surname><given-names>A. M.</given-names></name></name-alternatives><bio xml:lang="ru"><p>магистрант</p><p>г. Алматы, 050000</p></bio><bio xml:lang="en"><p>Master Student</p><p>Almaty, 050000</p></bio><email xlink:type="simple">bheadr73@gmail.com</email><xref ref-type="aff" rid="aff-2"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0002-4386-5915</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Калмурзаев</surname><given-names>Б. C.</given-names></name><name name-style="western" xml:lang="en"><surname>Kalmurzayev</surname><given-names>B. S.</given-names></name></name-alternatives><bio xml:lang="ru"><p>Ph.D., ассоц., профессор</p><p>г. Алматы, 050000</p></bio><bio xml:lang="en"><p>PhD., Associate Professor</p><p>Almaty, 050000</p></bio><email xlink:type="simple">birzhan.kalmurzayev@gmail.com</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru">Казахстанско-Британский технический университет<country>Казахстан</country></aff><aff xml:lang="en">Kazakh-British Technical University<country>Kazakhstan</country></aff></aff-alternatives><aff-alternatives id="aff-2"><aff xml:lang="ru">Казахский национальный университет им. аль-Фараби<country>Казахстан</country></aff><aff xml:lang="en">Al-Farabi Kazakh National University<country>Kazakhstan</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2024</year></pub-date><pub-date pub-type="epub"><day>25</day><month>03</month><year>2024</year></pub-date><volume>21</volume><issue>1</issue><fpage>94</fpage><lpage>102</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Аскарбеккызы А., Искаков А.М., Калмурзаев Б.C., 2024</copyright-statement><copyright-year>2024</copyright-year><copyright-holder xml:lang="ru">Аскарбеккызы А., Искаков А.М., Калмурзаев Б.C.</copyright-holder><copyright-holder xml:lang="en">Askarbekkyzy A., Iskakov A.M., Kalmurzayev B.S.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://vestnik.kbtu.edu.kz/jour/article/view/1026">https://vestnik.kbtu.edu.kz/jour/article/view/1026</self-uri><abstract><p>Алгоритмическая сложность представлений различных структур является объектом значительного интереса в современной научной литературе. Основным инструментом исследования в данном контексте является сводимость. Это отображение, сохраняющее отношения сигнатуры (такие как отношение эквивалентности, порядка и так далее). Данная работа посвящена исследованию пунктуальных представлений наименьшего предельного ординала относительно примитивно рекурсивной сводимости, обозначим данную структуру через PR(ω). В частности, в работе исследуется выполнение свойств структур Ω, состоящей из вычислимых копий  относительно вычислимой сводимости и Peq, состоящей из пунктуальных отношений эквивалентности относительно примитивно рекурсивной сводимости. Говорим, что линейный порядок L сводится к линейному порядку R, если существует всюду определенная функция P такая, что (χ, γ) Є Lтогда и только тогда (ρ(χ), ρ(γ)) Є R. Сводимости называют вычислимыми (примитивно рекурсивными), если функция, осуществляющая сводимость, является вычислимой (примитивно рекурсивной). Показано, что степень стандартной копии порядка ω не является наименьшей в PR(ω), как это было в Ω. Структура PR(ω) не содержит главные и максимальные степени, и данная структура не является плотной. Также приводится пример несравнимой пары с наименьшей верхней гранью.</p><p>   </p></abstract><trans-abstract xml:lang="en"><p>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.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>примитивно рекурсивная функция</kwd><kwd>линейный порядок</kwd><kwd>примитивно рекурсивная сводимость</kwd><kwd>пунктуальные представления линейных порядков</kwd><kwd>самополные порядки</kwd></kwd-group><kwd-group xml:lang="en"><kwd>primitive recursive function</kwd><kwd>linear order</kwd><kwd>primitive recursive reducibility</kwd><kwd>punctual representations of linear order</kwd><kwd>self-full orders</kwd></kwd-group><funding-group xml:lang="ru"><funding-statement>The work was supported by the Ministry of Science and Higher Education of the Republic of Kazakhstan, grant AP19576325 “Algorithmic complexities of presentations for algebraic structures”.</funding-statement></funding-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Kalimullin I., Melnikov, A. and Ng K.M. Algebraic structures computable without delay. Theoretical Computer Science, no. 674, 2017, pp. 73–98.</mixed-citation><mixed-citation xml:lang="en">Kalimullin I., Melnikov, A. and Ng K.M. Algebraic structures computable without delay. Theoretical Computer Science, no. 674, 2017, pp. 73–98.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Ershov Y. L. Positive equivalences. Algebra i Logika, 10(6), 1971, 620–650.</mixed-citation><mixed-citation xml:lang="en">Ershov Y. L. Positive equivalences. Algebra i Logika, 10(6), 1971, 620–650.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Bernardi C. and Sorbi A. Classifying positive equivalence relations. J. Symb. Logic, no. 48(3), 1983, pp. 529–538.</mixed-citation><mixed-citation xml:lang="en">Bernardi C. and Sorbi A. Classifying positive equivalence relations. J. Symb. Logic, no. 48(3), 1983, pp. 529–538.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Gao S. and Gerdes P. Computably enumerable equivalence relations. Studia Logica, no. 67(1), 2011, pp. 27–59.</mixed-citation><mixed-citation xml:lang="en">Gao S. and Gerdes P. Computably enumerable equivalence relations. Studia Logica, no. 67(1), 2011, pp. 27–59.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Andrews U. and Sorbi A. Joins and meets in the structure of ceers. Computability, no. 8(3–4), 2019, pp. 193–241.</mixed-citation><mixed-citation xml:lang="en">Andrews U. and Sorbi A. Joins and meets in the structure of ceers. Computability, no. 8(3–4), 2019, pp. 193–241.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Kabylzhanova D.K. On positive preorders. Algebra i Logica, no. 57(3), 2018, pp. 279–284 [in Russian].</mixed-citation><mixed-citation xml:lang="en">Kabylzhanova D.K. On positive preorders. Algebra i Logica, no. 57(3), 2018, pp. 279–284 [in Russian].</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Kuznecov A.V. On primitive recursive functions of large oscillation. Doklady Akademii Nauk SSSR, 71, 1950, pp. 233–236 [in Russian].</mixed-citation><mixed-citation xml:lang="en">Kuznecov A.V. On primitive recursive functions of large oscillation. Doklady Akademii Nauk SSSR, 71, 1950, pp. 233–236 [in Russian].</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
