Аннотация
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 199-213 |
Число страниц | 15 |
Журнал | Algebra and Logic |
Том | 58 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - 1 июл 2019 |