Abstract:
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.
Keywords:computable reducibility, positive linear preorder, computably enumerable preorder, first-order arithmetic, countable linear preorder.
Fulltext:
PDF file (313 kB)
First page:
PDF file