|
Эта публикация цитируется в 10 научных статьях (всего в 10 статьях)
О темных вычислимо перечислимых отношениях эквивалентности
Н. А. Баженовab, Б. С. Калмурзаевc a Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
b Новосибирский гос. университет, ул. Пирогова, 1, Новосибирск 630090
c Казахский национальный университет им. аль-Фараби, пр. аль-Фараби, 71, Алматы 050038, Казахстан
Аннотация:
Исследуются вычислимо перечислимые (в.п.) отношения эквивалентности на множестве натуральных чисел. Бинарное отношение $R$ на $\omega$ вычислимо сводится к отношению $S$ (обозначается через $R\leq_cS$), если существует вычислимая функция $f(x)$ такая, что для любых $x$ и $y$ условия $(xRy)$ и $(f(x)Sf(y))$ эквивалентны. Отношение эквивалентности $E$ называют темным, если оно не сравнимо относительно $\leq_c$ с тождественным отношением эквивалентности. Доказано, что для любого темного в.п. отношения эквивалентности $E$ существует слабо предполное темное в.п. отношение эквивалентности $F$ такое, что $E\leq_cF$. В качестве следствия этого результата построена бесконечная возрастающая $\leq_c$-цепь слабо предполных темных в.п. отношений эквивалентности. Также показано существование универсального относительно сводимости $\leq_c$ в.п. линейного порядка.
Ключевые слова:
отношение эквивалентности, вычислимо перечислимое отношение эквивалентности, вычислимая сводимость, слабо предполное отношение эквивалентности, вычислимо перечислимый линейный порядок, $lo$-сводимость.
Статья поступила: 07.06.2017
Образец цитирования:
Н. А. Баженов, Б. С. Калмурзаев, “О темных вычислимо перечислимых отношениях эквивалентности”, Сиб. матем. журн., 59:1 (2018), 29–40; Siberian Math. J., 59:1 (2018), 22–30
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj2951 https://www.mathnet.ru/rus/smj/v59/i1/p29
|
Статистика просмотров: |
Страница аннотации: | 295 | PDF полного текста: | 83 | Список литературы: | 38 | Первая страница: | 2 |
|