On dark computably enumerable equivalence relations
type: Item
instance of: scholarly article
title: On dark computably enumerable equivalence relations
zbMATH Open document ID: 1406.03057
DOI: 10.1134/S0037446618010032
published in: Siberian Mathematical Journal
publication date: 2018-06-20T00:00:00Z
review text: 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.
reviewed by: Leon Harkleroad
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 6892016
zbMATH Keywords: equivalence relation
zbMATH Keywords: computably enumerable equivalence relation
zbMATH Keywords: computable reducibility
zbMATH Keywords: weakly precomplete equivalence relation
zbMATH Keywords: computably enumerable order
zbMATH Keywords: \(lo\)-reducibility
author: Nikolay Bazhenov
author: B. S. Kalmurzayev
MaRDI profile type: Publication
cites work: Classifying positive equivalence relations
cites work: A Note on Positive Equivalence Relations
cites work: On weakly pre-complete positive equivalences
cites work: Weakly precomplete computably enumerable equivalence relations
cites work: Positive equivalences
cites work: Computably enumerable equivalence relations
cites work: Universal computably enumerable equivalence relations
cites work: THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
cites work: A Survey on Universal Computably Enumerable Equivalence Relations
cites work: Reducibilities among equivalence relations induced by recursively enumerable structures
cites work: LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS
cites work: Q4956005
cites work: Turing degrees of certain isomorphic images of computable relations
full work available at URL: s0037446618010032
OpenAlex ID: W2792971020
Wikidata QID: Q130184918
description: scientific article; zbMATH DE number 6892016