On the Theory of Computably Enumerable Linear Preorders with Concatenation | Sciact - Система учета научной деятельности ИМ СО РАН

On the Theory of Computably Enumerable Linear Preorders with Concatenation Научная публикация

Журнал

Siberian Mathematical Journal
ISSN: 0037-4466 , E-ISSN: 1573-9260

Вых. Данные

Год: 2025, Том: 66, Номер: 2, Страницы: 235–247 Страниц : 13 DOI: 10.1134/S0037446625020016

Ключевые слова

computable reducibility, positive linear preorder, computably enumerable preorder, firstorder arithmetic, countable linear preorder

Авторы

Alish D.B. ¹ , Bazhenov N.A. ^1,2 , Kalmurzaev B.S. ¹

Организации

1	Kazakh–British Technical University, Almaty, Kazakhstan
2	Sobolev Institute of Mathematics, Novosibirsk, Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0011

A preorder is linear whenever the corresponding quotient poset is linearly ordered. This article discusses computable reducibility on binary relations. We study the degree structure Celps of computably enumerable linear preorders under computable reducibility. Concatenation yields the ordered sum of two given linear preorders. We show that the elementary theory of Celps with concatenation is recursively isomorphic to first-order arithmetic. We also show that the theory of all countable linear preorders (under computable reducibility) with concatenation is recursively isomorphic to second-order arithmetic.

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

Алиш Д.Б. , Баженов Н.А. , Калмурзаев Б.С.
О теории вычислимо перечислимых линейных предпорядков с конкатенацией
Сибирский математический журнал. 2025. Т.66. №2. С.131-146. DOI: 10.33048/smzh.2025.66.201 РИНЦ

Поступила в редакцию:	20 авг. 2024 г.
Принята к публикации:	25 февр. 2025 г.
Опубликована в печати:	23 мар. 2025 г.
Опубликована online:	23 мар. 2025 г.

Web of science:	WOS:001572112100010
Scopus:	2-s2.0-105000706416
РИНЦ:	80504511
OpenAlex:	W4408735185

Пока нет цитирований