The structure of computably enumerable preorder relations
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.
- The theory of ceers computes true arithmetic
- The first-order theory of the computably enumerable equivalence relations in the uncountable setting
- Initial segments of the degrees of ceers
- A semilattice generated by superlow computably enumerable degrees
- Linear orders realized by c.e. equivalence relations
- Positive preorders
- Jumps of computably enumerable equivalence relations
- Rogers semilattices for families of equivalence relations in the Ershov hierarchy
- Joins and meets in the structure of ceers
- On the degree structure of equivalence relations under computable reducibility
- A survey on universal computably enumerable equivalence relations
- Classical recursion theory. Vol. II
- Classifying positive equivalence relations
- Computably enumerable equivalence relations
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- Initial segments of one-one degrees
- Joins and meets in the structure of ceers
- Jumps of computably enumerable equivalence relations
- On dark computably enumerable equivalence relations
- On the relation provable equivalence and on partitions in effectively inseparable sets
- Positive equivalences
- The theory of ceers computes true arithmetic
- Universal computably enumerable equivalence relations
- Weakly precomplete computably enumerable equivalence relations
- Jumps of computably enumerable equivalence relations
- Positive preorders
- Index sets for classes of positive preorders
- The theory of ceers computes true arithmetic
- Unions of rank/trace complete preorders
- On universal positive graphs
- The first-order theory of the computably enumerable equivalence relations in the uncountable setting
- Computable reducibility for computable linear orders of type
- A note on joins and meets for positive linear preorders
- Computably enumerable equivalence relations via primitive recursive reductions
- On the theory of computably enumerable linear preorders with concatenation
This page was built for publication: The structure of computably enumerable preorder relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2213931)
