RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2019, том 58, номер 3, страницы 334–343 (Mi al898)

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

Вычислимые нумерации семейств бесконечных множеств

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

Новосибирский гос. ун-т, ул. Пирогова, 1, Новосибирск, 630090, РОССИЯ

Аннотация: У семейства всех бесконечных вычислимо перечислимых множеств нет вычислимой нумерации; у семейства всех бесконечных $\Pi^{1}_{1}$-множеств нет $\Pi^{1}_{1}$-вычислимой нумерации; у семейства всех бесконечных $\Sigma^{1}_{2}$-множеств нет $\Sigma^{1}_{2}$-вычислимой нумерации. При $k>2$ существование $\Sigma^{1}_{k}$-вычислимой нумерации семейства всех бесконечных $\Sigma^{1}_{k}$-множеств приводит к противоречивости $ZF$.

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

УДК: 510.5

Поступило: 27.01.2018
Окончательный вариант: 24.09.2019

DOI: 10.33048/alglog.2019.58.303


 Англоязычная версия: Algebra and Logic, 2019, 58:3, 224–231

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


© МИАН, 2024