The structure of computably enumerable preorder relations (Q2213931): Difference between revisions

This paper builds on ideas of Ershov, drawing on recent work of \textit{U. Andrews} et al. [Ann. Pure Appl. Logic 171, No. 8, Article ID 102811, 22 p. (2020; Zbl 1442.03021)]. The structure CEPRS consists of c-degrees of preorder relations, binary numerical relations that are both reflexive and transitive. A CEPR that is also symmetric is an equivalence relation. The structure of c.e. equivalence relations is definable in CEPRS and is computably isomorphic to first-order arithmetic. A binary relation $R$ that is reflexive and transitive is a preorder. $R$ is reducible to $S$ iff there is a computable function $f$ such that for all $x$ and $y$, $xRy$ iff $f(x)Sf(y)$. It is known that no two incomparable degrees in CEPRS have a least upper bound. The paper also examines the structures CEERS of c.e. equivalence relations and CELPS, of c.c. linear preorders. Both are definable in CEPRS. CEERS and CELPS are not elementarily equivalent. If $P$ and $Q$ are incomparable CEPRS with respect to $\leq_c$ then their degrees have no supremum in CEPRS. The sentence asserting that there are at least 3 distinct minimal degrees is true in CEPRS but not in CELPS, marking them as different structures.