Weakly Precomplete Equivalence Relations in the Ershov Hierarchy

N. A. Bazhenov, B. S. Kalmurzaev

Результат исследования: Научные публикации в периодических изданияхстатья

1 Цитирования (Scopus)

Аннотация

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

Fingerprint Подробные сведения о темах исследования «Weakly Precomplete Equivalence Relations in the Ershov Hierarchy». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать