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

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

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

О слабо предполных отношениях эквивалентности в иерархии Ершова

Н. А. Баженовab, Б. С. Калмурзаевc

a Ин-т матем. им. С. Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
b Новосибирский гос. ун-т, ул. Пирогова, 1, г. Новосибирск, 630090, РОССИЯ
c Казахский нац. ун-т им. аль-Фараби, пр. аль-Фараби, 71, Алма-Ата, 050038, КАЗАХСТАН

Аннотация: Исследуется вычислимая сводимость $\leq_c$ для отношений эквивалентности в иерархии Ершова. Для произвольного обозначения $a$ ненулевого вычислимого ординала устанавливается существование $\Pi^{-1}_a$-универсального отношения эквивалентности и слабо предполного $\Sigma^{-1}_a$-универсального отношения эквивалентности. Доказывается, что для любого $\Sigma^{-1}_a$-отношения эквивалентности $E$ существует слабо предполное $\Sigma^{-1}_a$-отношение эквивалентности $F$, такое что $E\leq_c F$. Для конечных уровней иерархии Ершова $\Sigma^{-1}_m$, таких что $m=4k+1$ или $m=4k+2$, показывается существование бесконечного числа $\leq_c$-степеней, содержащих слабо предполные, собственные $\Sigma^{-1}_m$-отношения эквивалентности.

Ключевые слова: иерархия Ершова, отношение эквивалентности, вычислимая сводимость, универсальное отношение эквивалентности, слабо предполное отношение эквивалентности.

УДК: 510.54

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

DOI: 10.33048/alglog.2019.58.301


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

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


© МИАН, 2024