О теории вычислимо перечислимых линейных предпорядков с конкатенацией
О теории вычислимо перечислимых линейных предпорядков с конкатенацией
Аннотация:
Предпорядок $R$ называют линейным, если соответствующий фактор-порядок является линейно упорядоченным. Данная работа посвящена изучению вычислимой сводимости на бинарных отношениях. В работе исследуется степенная структура Celps вычислимо перечислимых линейных предпорядков относительно вычислимой сводимости.
Операция конкатенации дает упорядоченную сумму двух данных линейных предпорядков. Доказано, что элементарная теория структуры Celps с операцией конкатенации рекурсивно изоморфна арифметике первого порядка. Также показано, что теория всех счетных линейных предпорядков (относительно вычислимой сводимости) с операцией конкатенации рекурсивно изоморфна арифметике второго порядка.
Литература:
- Ершов Ю. Л. Позитивные эквивалентности // Алгебра и логика. 1971. Т. 10, № 6. С. 620–650.
- Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.
- Bernardi C. On the relation provable equivalence and on partitions in effectively inseparable sets // Stud. Logic. 1981. V. 40, N 1. P. 29–37.
- Bernardi C., Sorbi A. Classifying positive equivalence relations // J. Symbol. Logic. 1983. V. 48, N 3. P. 529–538.
- 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.
- Gao S., Gerdes P. Computably enumerable equivalence relations // Stud. Logic. 2001. V. 67, N 1. P. 27–59.
- Simpson S. G. First-order theory of the degrees of recursive unsolvability // Ann. Math. 1977. V. 105, N 1. P. 121–139.
- Shore R. A. The theory of degrees below 0′ // J. Lond. Math. Soc. 1981. V. 24, N 1. P. 1–14.
- Nerode A., Shore R. A. Reducibility orderings: Theories, definability and automorphisms // Ann. Math. Logic. 1980. V. 18, N 1. P. 61–89.
- Нис А. Последний вопрос о рекурсивно-перечислимых $m$-степенях // Алгебра и логика. 1994. Т. 33, № 5. С. 550–563.
- Andrews U., Sorbi A. Joins and meets in the structure of ceers // Computability. 2019. V. 8, N 3–4. P. 193–241.
- Andrews U., Schweber N., Sorbi A. The theory of ceers computes true arithmetic // Ann. Pure Appl. Logic. 2020. V. 171, N 8. P. 102811.
- Бадаев С. А., Баженов Н. А., Калмурзаев Б. С. О структуре позитивных предпорядков // Алгебра и логика. 2020. Т. 59, № 3. С. 293–314.
- 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.
- 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.
- Rosenstein J. G. Linear orderings. New York: Acad. Press, 1982.
- Баженов Н. А., Калмурзаев Б. С. О темных вычислимо перечислимых отношениях эквивалентности // Сиб. мат. журн. 2018. Т. 59, № 1. С. 29–40.
- Bazhenov N., Kalmurzayev B., Zubkov M. A note on joins and meets for positive linear preorders // Сиб. электрон. мат. изв. 2023. V. 20, N 1. P. 1–16.
- 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.
- Rogers H. Theory of recursive functions and effective computability. Cambridge, MA: MIT Press, 1987.
- 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.
- 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)
- Казахстанско-Британский технический университет,
ул. Толе би, 59, Алматы 050000, Казахстан
E-mail: alish.darynn@gmail.com
Баженов Николай Алексеевич (ORCID 0000-0002-5834-2770)
- Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, Новосибирск 630090 - Казахстанско-Британский технический университет,
ул. Толе би, 59, Алматы 050000, Казахстан
E-mail: bazhenov@math.nsc.ru
Калмурзаев Биржан Сеилханович (ORCID 0000-0002-4386-5915)
- Казахстанско-Британский технический университет,
ул. Толе би, 59, Алматы 050000, Казахстан
E-mail: birzhan.kalmurzayev@gmail.com
Статья поступила 20 августа 2024 г.
После доработки — 17 января 2025 г.
Принята к публикации 25 февраля 2025 г.