Classifying equivalence relations in the Ershov hierarchy

Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi, Mars Yamaleev

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

Аннотация

Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ⩽ c. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the Δ20 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by ⩽ c on the Σa-1\Πa-1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.

Язык оригиналаанглийский
Страницы (с-по)835-864
Число страниц30
ЖурналArchive for Mathematical Logic
Том59
Номер выпуска7-8
DOI
СостояниеПринято в печать - 1 янв 2020

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

  • Цитировать

    Bazhenov, N., Mustafa, M., San Mauro, L., Sorbi, A., & Yamaleev, M. (Принято в печать). Classifying equivalence relations in the Ershov hierarchy. Archive for Mathematical Logic, 59(7-8), 835-864. https://doi.org/10.1007/s00153-020-00710-1