Abstract
We study the computable reducibility ≤c for equivalence relations in the Ershov hierarchy. For an arbitrary notation a for a nonzero computable ordinal, it is stated that there exist a Πa−1 -universal equivalence relation and a weakly precomplete Σa−1 - universal equivalence relation. We prove that for any Σa−1 equivalence relation E, there is a weakly precomplete Σa−1 equivalence relation F such that E ≤cF. For finite levels Σm−1 in the Ershov hierarchy at which m = 4k +1 or m = 4k +2, it is shown that there exist infinitely many ≤c-degrees containing weakly precomplete, proper Σm−1 equivalence relations.
Original language | English |
---|---|
Pages (from-to) | 199-213 |
Number of pages | 15 |
Journal | Algebra and Logic |
Volume | 58 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Jul 2019 |
Keywords
- computable reducibility
- equivalence relation
- Ershov hierarchy
- universal equivalence relation
- weakly precomplete equivalence relation