Rogers Semilattices for Families of Equivalence Relations in the Ershov Hierarchy

N. A. Bazhenov, B. S. Kalmurzaev

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

Аннотация

The paper studies Rogers semilattices for families of equivalence relations in the Ershov hierarchy. For an arbitrary notation a of a nonzero computable ordinal, we consider ∑a−1-computable numberings of the family of all ∑a−1 equivalence relations. We show that this family has infinitely many pairwise incomparable Friedberg numberings and infinitely many pairwise incomparable positive undecidable numberings. We prove that the family of all c.e. equivalence relations has infinitely many pairwise incomparable minimal nonpositive numberings. Moreover, we show that there are infinitely many principal ideals without minimal numberings.

Язык оригиналаанглийский
Страницы (с-по)223-234
Число страниц12
ЖурналSiberian Mathematical Journal
Том60
Номер выпуска2
DOI
СостояниеОпубликовано - 1 мар 2019

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

  • Цитировать