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

Сиб. журн. чист. и прикл. матем., 2018, том 18, выпуск 2, страницы 47–52 (Mi vngu471)

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

Однозначная нумерация для семейства всех $\Sigma^{1}_{2}$-множеств

М. В. Доржиева

Новосибирский государственный университет, ул. Пирогова, 1, Новосибирск, 630090, Россия

Аннотация: Изучается вопрос о существовании однозначной $\Sigma^{1}_{2}$-вычислимой нумерации для семейства всех $\Sigma^{1}_{2}$-множеств. Как известно, Фридберг построил однозначную нумерацию семейства всех вычислимо перечислимых множеств. Также на любом уровне $n$ арифметической иерархии и иерархии Ершова существуют однозначные нумерации всего семейства множеств уровня $n$. Однако Дж. Оуинс показал, что для первого уровня аналитической иерархии однозначной $\Pi^{1}_{1}$-вычислимой нумерации не существует. В данной работе доказывается, что и для второго уровня аналитической иерархии однозначной $\Sigma^{1}_{2}$-вычислимой нумерации для семейства всех $\Sigma^{1}_{2}$-множеств не существует.

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

УДК: 510.5

Поступила в редакцию: 12.12.2013

DOI: 10.17377/PAM.2018.18.5


 Англоязычная версия: Journal of Mathematical Sciences, 2020, 246:6, 788–792


© МИАН, 2024