On the Theory of Computably Enumerable Linear Preorders with Concatenation
Alish D.B. Bazhenov N.A. Kalmurzaev B.S.
March 2025Pleiades Publishing
Siberian Mathematical Journal
2025#66Issue 2235 - 247 pp.
A preorder is linearwhenever the corresponding quotient poset is linearly ordered.This article discusses computable reducibility on binary relations.We study the degree structure Celpsof computably enumerable linear preordersunder computable reducibility.Concatenation yields the ordered sum of two given linear preorders.We show thatthe elementary theory of Celps with concatenationis recursively isomorphic to first-order arithmetic.We also show thatthe theory of all countable linear preorders(under computable reducibility)with concatenationis recursively isomorphic to second-order arithmetic.
510.5 , computable reducibility , computably enumerable preorder , countable linear preorder , first-order arithmetic , positive linear preorder
Text of the article Перейти на текст статьи
Kazakh–British Technical University, Almaty, Kazakhstan
Sobolev Institute of Mathematics, Novosibirsk, Russian Federation
Kazakh–British Technical University
Sobolev Institute of Mathematics
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026