Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies

2020

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

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

Аннотация

A standard tool for classifying the complexity of equivalence relations on $$\omega$$ is provided by computable reducibility. This reducibility gives rise to a rich degree structure. The paper studies equivalence relations, which induce minimal degrees with respect to computable reducibility. Let $$\Gamma$$ be one of the following classes: $$\Sigma^{0}_{\alpha}$$ , $$\Pi^{0}_{\alpha}$$ , $$\Sigma^{1}_{n}$$ , or $$\Pi^{1}_{n}$$ , where $$\alpha\geq 2$$ is a computable ordinal and $$n$$ is a non-zero natural number. We prove that there are infinitely many pairwise incomparable minimal equivalence relations that are properly in $$\Gamma$$ .