RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2010, том 51, номер 6, страницы 1435–1439 (Mi smj2172)

Эта публикация цитируется в 2 статьях

Вычислимые нумерации семейств низких множеств и тьюринговы скачки в иерархии Ершова

М. Х. Файзрахманов

Казанский (Приволжский) федеральный университет, кафедра алгебры и математической логики, Казань

Аннотация: Получен следующий результат: если даны $\Delta^0_2$-вычислимые нумерации $\nu,\mu$ семейств множеств натуральных чисел, то предикат $P(x,y)\Leftrightarrow\nu(x)'\not=\mu(y)$ является $\Sigma^0_2$-предикатом. Как следствия из этого результата можно получить достаточное условие существования $\Delta^0_2$-вычислимой нумерации подсемейства всех множеств данного семейства, тьюринговы скачки которых лежат в фиксированном уровне иерархии Ершова, и существование $\Sigma^{-1}_\omega$-вычислимой нумерации семейства всех супернизких множеств.

Ключевые слова: вычислимая нумерация, иерархия Ершова, конструктивный ординал, низкое множество, супернизкое множество.

УДК: 510.5

Статья поступила: 17.05.2009


 Англоязычная версия: Siberian Mathematical Journal, 2010, 51:6, 1135–1138

Реферативные базы данных:


© МИАН, 2024