On the Theory of Computably Enumerable Linear Preorders with Concatenation

A preorder $ R $ 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.