Sciact
  • EN
  • RU

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

Journal Сибирский математический журнал
ISSN: 0037-4474
Output data Year: 2025, Volume: 66, Number: 2, Pages: 131-146 Pages count : 15 DOI: 10.33048/smzh.2025.66.201
Tags вычислимая сводимость, позитивный линейный предпорядок, вычислимо перечислимый предпорядок, арифметика первого порядка, счетный линейный предпорядок.
Authors Алиш Д.Б. 1 , Баженов Н.А. 1,2 , Калмурзаев Б.С. 1
Affiliations
1 Казахстанско-Британский технический университет, ул. Толе би, 59, Алматы 050000, Казахстан
2 Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090;

Funding (1)

1 Sobolev Institute of Mathematics FWNF-2022-0011

Abstract: Предпорядок R называют линейным, если соответствующий факторпорядок является линейно упорядоченным. Данная работа посвящена изучению вычислимой сводимости на бинарных отношениях. В работе исследуется степенная структура Celps вычислимо перечислимых линейных предпорядков относительно вычислимой сводимости. Операция конкатенации дает упорядоченную сумму двух данных линейных предпорядков. Доказано, что элементарная теория структуры Celps с операцией конкатенации рекурсивно изоморфна арифметике первого порядка. Также показано, что теория всех счетных линейных предпорядков (относительно вычислимой сводимости) с операцией конкатенации рекурсивно изоморфна арифметике второго порядка.
Cite: Алиш Д.Б. , Баженов Н.А. , Калмурзаев Б.С.
О теории вычислимо перечислимых линейных предпорядков с конкатенацией
Сибирский математический журнал. 2025. Т.66. №2. С.131-146. DOI: 10.33048/smzh.2025.66.201 РИНЦ
Translated: Alish D.B. , Bazhenov N.A. , Kalmurzaev B.S.
On the Theory of Computably Enumerable Linear Preorders with Concatenation
Siberian Mathematical Journal. 2025. V.66. N2. P.235–247. DOI: 10.1134/S0037446625020016 WOS Scopus РИНЦ OpenAlex
Dates:
Submitted: Aug 20, 2024
Accepted: Feb 25, 2025
Published print: Apr 2, 2025
Published online: Apr 2, 2025
Identifiers:
Elibrary: 80537541
Citing: Пока нет цитирований
Altmetrics: