О теории вычислимо перечислимых линейных предпорядков с конкатенацией

О теории вычислимо перечислимых линейных предпорядков с конкатенацией

Алиш Д. Б., Баженов Н. А., Калмурзаев Б. С.
Сибирский математический журнал, 66, 2, 131-146 (2025)
Скачать статью

УДК 510.5 
DOI: 10.33048/smzh.2025.66.201

Аннотация:

Предпорядок $R$ называют линейным, если соответствующий фактор-порядок является линейно упорядоченным. Данная работа посвящена изучению вычислимой сводимости на бинарных отношениях. В работе исследуется степенная структура Celps вычислимо перечислимых линейных предпорядков относительно вычислимой сводимости. 

Операция конкатенации дает упорядоченную сумму двух данных линейных предпорядков. Доказано, что элементарная теория структуры Celps с операцией конкатенации рекурсивно изоморфна арифметике первого порядка. Также показано, что теория всех счетных линейных предпорядков (относительно вычислимой сводимости) с операцией конкатенации рекурсивно изоморфна арифметике второго порядка.

Литература:
  1. Ершов Ю. Л. Позитивные эквивалентности // Алгебра и логика. 1971. Т. 10, № 6. С. 620–650.
     
  2. Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.
     
  3. Bernardi C. On the relation provable equivalence and on partitions in effectively inseparable sets // Stud. Logic. 1981. V. 40, N 1. P. 29–37.
     
  4. Bernardi C., Sorbi A. Classifying positive equivalence relations // J. Symbol. Logic. 1983. V. 48, N 3. P. 529–538. 
     
  5. Andrews U., Badaev S. A., Sorbi A. A survey on universal computably enumerable equivalence relations // Lect. Notes Comput. Sci. 2017. V. 10010. P. 418–451.
     
  6. Gao S., Gerdes P. Computably enumerable equivalence relations // Stud. Logic. 2001. V. 67, N 1. P. 27–59.
     
  7. Simpson S. G. First-order theory of the degrees of recursive unsolvability // Ann. Math. 1977. V. 105, N 1. P. 121–139.
     
  8. Shore R. A. The theory of degrees below 0′ // J. Lond. Math. Soc. 1981. V. 24, N 1. P. 1–14.
     
  9. Nerode A., Shore R. A. Reducibility orderings: Theories, definability and automorphisms // Ann. Math. Logic. 1980. V. 18, N 1. P. 61–89.
     
  10. Нис А. Последний вопрос о рекурсивно-перечислимых $m$-степенях // Алгебра и логика. 1994. Т. 33, № 5. С. 550–563.
     
  11. Andrews U., Sorbi A. Joins and meets in the structure of ceers // Computability. 2019. V. 8, N 3–4. P. 193–241. 
     
  12. Andrews U., Schweber N., Sorbi A. The theory of ceers computes true arithmetic // Ann. Pure Appl. Logic. 2020. V. 171, N 8. P. 102811.
     
  13. Бадаев С. А., Баженов Н. А., Калмурзаев Б. С. О структуре позитивных предпорядков // Алгебра и логика. 2020. Т. 59, № 3. С. 293–314.
     
  14. Andrews U., Belin D. F., San Mauro L. On the structure of computable reducibility on equivalence relations of natural numbers // J. Symb. Logic. 2023. V. 88, N 3. P. 1038–1063.
     
  15. Andrews U., Lempp S., Mustafa M., Schweber N. D. The first-order theory of the computably enumerable equivalence relations in the uncountable setting // J. Logic Comput. 2022. V. 32, N 1. P. 98–114.
     
  16. Rosenstein J. G. Linear orderings. New York: Acad. Press, 1982.
     
  17. Баженов Н. А., Калмурзаев Б. С. О темных вычислимо перечислимых отношениях эквивалентности // Сиб. мат. журн. 2018. Т. 59, № 1. С. 29–40.
     
  18. Bazhenov N., Kalmurzayev B., Zubkov M. A note on joins and meets for positive linear preorders // Сиб. электрон. мат. изв. 2023. V. 20, N 1. P. 1–16.
     
  19. Kach A. M., Montalbán A. Undecidability of the theories of classes of structures // J. Symb. Logic. 2014. V. 79, N 4. P. 1001–1019.
     
  20. Rogers H. Theory of recursive functions and effective computability. Cambridge, MA: MIT Press, 1987.
     
  21. Askarbekkyzy A., Bazhenov N. A., Kalmurzayev B. S. Computable reducibility for computable linear orders of type $\omega$// J. Math. Sci. 2022. V. 267, N 4. P. 429–443.
     
  22. Harizanov V. S. Turing degrees of certain isomorphic images of computable relations // Ann. Pure Appl. Logic. 1998. V. 93, N 1–3. P. 103–113.

Исследование поддержано Комитетом науки Министерства образования и науки Республики Казахстан (грант № AP19576325). Работа Н. А. Баженова выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0011).

Алиш Дарын Бакытович (ORCID 0000-0002-4933-0575)
  1. Казахстанско-Британский технический университет, 
    ул. Толе би, 59, Алматы 050000, Казахстан

E-mail: alish.darynn@gmail.com

Баженов Николай Алексеевич (ORCID 0000-0002-5834-2770)
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Академика Коптюга, 4, Новосибирск 630090
  2. Казахстанско-Британский технический университет, 
    ул. Толе би, 59, Алматы 050000, Казахстан

E-mail: bazhenov@math.nsc.ru

Калмурзаев Биржан Сеилханович (ORCID 0000-0002-4386-5915)
  1. Казахстанско-Британский технический университет,
    ул. Толе би, 59, Алматы 050000, Казахстан

E-mail: birzhan.kalmurzayev@gmail.com

Статья поступила 20 августа 2024 г. 
После доработки — 17 января 2025 г.
Принята к публикации 25 февраля 2025 г.