On the Theory of Computably Enumerable Linear Preorders with Concatenation Full article
| Journal |
Siberian Mathematical Journal
ISSN: 0037-4466 , E-ISSN: 1573-9260 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 66, Number: 2, Pages: 235–247 Pages count : 13 DOI: 10.1134/S0037446625020016 | ||||
| Tags | computable reducibility, positive linear preorder, computably enumerable preorder, firstorder arithmetic, countable linear preorder | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
Abstract:
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.
Cite:
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 Scopus РИНЦ OpenAlex
On the Theory of Computably Enumerable Linear Preorders with Concatenation
Siberian Mathematical Journal. 2025. V.66. N2. P.235–247. DOI: 10.1134/S0037446625020016 Scopus РИНЦ OpenAlex
Original:
Алиш Д.Б.
, Баженов Н.А.
, Калмурзаев Б.С.
О теории вычислимо перечислимых линейных предпорядков с конкатенацией
Сибирский математический журнал. 2025. Т.66. №2. С.131-146. DOI: 10.33048/smzh.2025.66.201 РИНЦ
О теории вычислимо перечислимых линейных предпорядков с конкатенацией
Сибирский математический журнал. 2025. Т.66. №2. С.131-146. DOI: 10.33048/smzh.2025.66.201 РИНЦ
Dates:
| Submitted: | Aug 20, 2024 |
| Accepted: | Feb 25, 2025 |
| Published print: | Mar 23, 2025 |
| Published online: | Mar 23, 2025 |
Identifiers:
| Scopus: | 2-s2.0-105000706416 |
| Elibrary: | 80504511 |
| OpenAlex: | W4408735185 |
Citing:
Пока нет цитирований