## Abstract

We study computably enumerable (c.e.) relations on the set of naturals. A binary relation R on ω is computably reducible to a relation S (which is denoted by R ≤_{c}S) if there exists a computable function f(x) such that the conditions (xRy) and (f(x)Sf(y)) are equivalent for all x and y. An equivalence relation E is called dark if it is incomparable with respect to ≤_{c} with the identity equivalence relation. We prove that, for every dark c.e. equivalence relation E there exists a weakly precomplete dark c.e. relation F such that E ≤_{c}F. As a consequence of this result, we construct an infinite increasing ≤_{c}-chain of weakly precomplete dark c.e. equivalence relations. We also show the existence of a universal c.e. linear order with respect to ≤_{c}.

Original language | English |
---|---|

Pages (from-to) | 22-30 |

Number of pages | 9 |

Journal | Siberian Mathematical Journal |

Volume | 59 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

## Keywords

- computable reducibility
- computably enumerable equivalence relation
- computably enumerable order
- equivalence relation
- lo-reducibility
- weakly precomplete equivalence relation