|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Однозначная нумерация для семейства всех $\Sigma^{1}_{2}$-множеств
М. В. Доржиева Новосибирский государственный университет, ул. Пирогова, 1, Новосибирск, 630090, Россия
Аннотация:
Изучается вопрос о существовании однозначной $\Sigma^{1}_{2}$-вычислимой нумерации для семейства всех $\Sigma^{1}_{2}$-множеств. Как известно, Фридберг построил однозначную нумерацию семейства всех вычислимо перечислимых множеств. Также на любом уровне $n$ арифметической иерархии и иерархии Ершова существуют однозначные нумерации всего семейства множеств уровня $n$. Однако Дж. Оуинс показал, что для первого уровня аналитической иерархии однозначной $\Pi^{1}_{1}$-вычислимой нумерации не существует. В данной работе доказывается, что и для второго уровня аналитической иерархии однозначной $\Sigma^{1}_{2}$-вычислимой нумерации для семейства всех $\Sigma^{1}_{2}$-множеств не существует.
Ключевые слова:
нумерация, минимальная нумерация, однозначная нумерация, аналитическая иерархия.
Поступила в редакцию: 12.12.2013
Образец цитирования:
М. В. Доржиева, “Однозначная нумерация для семейства всех $\Sigma^{1}_{2}$-множеств”, Сиб. журн. чист. и прикл. матем., 18:2 (2018), 47–52; J. Math. Sci., 246:6 (2020), 788–792
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vngu471 https://www.mathnet.ru/rus/vngu/v18/i2/p47
|
Статистика просмотров: |
Страница аннотации: | 169 | PDF полного текста: | 41 | Список литературы: | 38 | Первая страница: | 7 |
|