The structure of computably enumerable preorder relations (Q2213931): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Nikolay Bazhenov / rank | |||
Property / reviewed by | |||
Property / reviewed by: Joseph S. Ullian / rank | |||
Revision as of 23:13, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The structure of computably enumerable preorder relations |
scientific article |
Statements
The structure of computably enumerable preorder relations (English)
0 references
4 December 2020
0 references
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.
0 references
computably enumerable preorder
0 references
computable reducibility
0 references
structure induced by degrees of computably enumerable preorder relations with respect to computable reducibility
0 references