On dark computably enumerable equivalence relations (Q1642296)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On dark computably enumerable equivalence relations |
scientific article |
Statements
On dark computably enumerable equivalence relations (English)
0 references
20 June 2018
0 references
Ceers (c.e~equivalence relations) on \(\omega\) can be compared by \(\leq_c\), where \(R \leq_c S\) means that for some computable~\(f\), \(\forall x\forall y(xRy\Leftrightarrow f(x)Sf(y))\). A \textsl{dark} equivalence relation is one that is \(\leq_c\)-incomparable with the identity relation. A \textsl{weakly precomplete} equivalence relation~\(R\) is one for which some partial computable \(g\) satisfies \(\forall e[\varphi_e\text{\;total}\Rightarrow(g(e)\!\!\downarrow \&\, \varphi_e(g(e))Rg(e))]\). The main result of this paper is that every dark ceer~\(R\) satisfies \(R <_c S\) for some weakly precomplete dark ceer~\(S\). The authors also provide similarly flavored results for c.e.~preorders that mod out to linear orders.
0 references
equivalence relation
0 references
computably enumerable equivalence relation
0 references
computable reducibility
0 references
weakly precomplete equivalence relation
0 references
computably enumerable order
0 references
\(lo\)-reducibility
0 references
0 references