Classifying equivalence relations in the Ershov hierarchy

2020

Полный текст Открытый доступ: Hybrid Метаданные (CSL-JSON)
DOI 10.1007/s00153-020-00710-1
Достоверность данных 70 средняя
Как считается эта оценка

Складывается из проверяемых признаков самой записи: есть ли у статьи DOI, сколько независимых источников подтвердили её данные, заполнены ли обязательные поля и насколько свежо последнее подтверждение. Снижают оценку расхождения между источниками и отсутствие идентификатора. Значение от 80 означает, что запись опубликована без дополнительной проверки; от 60 до 79 — что она опубликована с пониженной достоверностью и ручная проверка желательна. Запись, выверенную редактором вручную, пересчёт не опускает ниже 90. Это оценка наших данных о статье, а не оценка самой статьи.

Аннотация

Abstract 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 $$\leqslant _c$$ ⩽ c . This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the $$\Delta ^0_2$$ Δ 2 0 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 $$\leqslant _c$$ ⩽ c on the $$\Sigma ^{-1}_{a}\smallsetminus \Pi ^{-1}_a$$ Σ a - 1 \ Π a - 1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees.