|
Ученые записки Казанского университета. Серия Физико-математические науки, 2017, том 159, книга 3, страницы 296–305
(Mi uzku1409)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Спектр отношения блока $1$-вычислимых линейных порядков
Р. И. Бикмухаметов, М. С. Еряшкин, А. Н. Фролов Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия
Аннотация:
Работа посвящена исследованию внутренне вычислимо перечислимых отношений на линейных порядках, таких как отношение соседства на вычислимых линейных порядках и отношение блока на $1$-вычислимых линейных порядках. Для удобства изложения линейные порядки, сигнатура которых обогащена отношением соседства, называются $1$-вычислимым линейным порядком. Этот термин согласуется с известными результатами.
Доказывается, что для каждого $\mathbf0'$-вычислимого линейного порядка $L$ существует $1$-вычислимый линейный порядок, спектр отношения блока которого совпадает с $\Sigma_1^0$-спектром линейного порядка $L$. Спектром отношения блока линейного порядка $R$ называется класс тьюринговых степеней образа отношения блока на вычислимых представлениях $R$, а $\Sigma_1^0$-спектром линейного порядка $L$ – класс тьюринговых перечислимых степеней представлений $L$.
Этот результат позволяет получить ряд примеров спектров отношения блока $1$-вычислимых линейных порядков. В частности, класс всех перечислимых $n$-высоких степеней и класс всех перечислимых степеней, не являющихся $n$-низкими, реализуются спектрами отношения блока некоторых $1$-вычислимых линейных порядков.
Ключевые слова:
линейные порядки, $1$-вычислимость, отношение блока, отношение соседства, спектр отношения, внутренне вычислимо перечислимые отношения.
Поступила в редакцию: 21.06.2017
Образец цитирования:
Р. И. Бикмухаметов, М. С. Еряшкин, А. Н. Фролов, “Спектр отношения блока $1$-вычислимых линейных порядков”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 159, № 3, Изд-во Казанского ун-та, Казань, 2017, 296–305
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzku1409 https://www.mathnet.ru/rus/uzku/v159/i3/p296
|
Статистика просмотров: |
Страница аннотации: | 337 | PDF полного текста: | 144 | Список литературы: | 40 |
|