|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Об индексных множествах для классов позитивных предпорядков
Б. С. Калмурзаевab, Н. А. Баженовc, М. А. Торебековаb a Казахский нац. ун-т им. аль-Фараби, г. Алма-Ата, КАЗАХСТАН
b Казахстанско-Британский техн. ун-т, г. Алма-Ата, КАЗАХСТАН
c Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
Аннотация:
Изучается сложность индексных множеств относительно универсальной вычислимой нумерации семейства всех позитивных предпорядков. Пусть $\leq_c$ — вычислимая сводимость на позитивных предпорядках. Для произвольного позитивного предпорядка $R$, такого что $R$-индуцированная эквивалентность $\sim_R$ имеет бесконечно много классов, устанавливаются следующие результаты. Индексное множество предпорядков $P$, таких что $R\leq_c P$, является $\Sigma^0_3$-полным. Предпорядок $R$ называют самополным, если область значений любой вычислимой функции, осуществляющей сводимость $R \leq_c R$, пересекает все $\sim_R$-классы. Если $L$ — позитивный линейный предпорядок, не являющийся самополным, то индексное множество предпорядков $P$, таких что $P\equiv_c L$, является $\Sigma^0_3$-полным. Доказывается, что индексное множество самополных линейных предпорядков является $\Pi^0_3$-полным.
Ключевые слова:
позитивный предпорядок, позитивная эквивалентность, позитивный линейный предпорядок, вычислимая сводимость, индексное множество.
Поступило: 28.07.2021 Окончательный вариант: 07.06.2022
Образец цитирования:
Б. С. Калмурзаев, Н. А. Баженов, М. А. Торебекова, “Об индексных множествах для классов позитивных предпорядков”, Алгебра и логика, 61:1 (2022), 42–76
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2696 https://www.mathnet.ru/rus/al/v61/i1/p42
|
Статистика просмотров: |
Страница аннотации: | 126 | PDF полного текста: | 42 | Список литературы: | 23 | Первая страница: | 6 |
|