|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
О структуре позитивных предпорядков
С. А. Бадаевa, Н. А. Баженовb, Б. С. Калмурзаевca a Казахстанско-Британский техн. ун-т, г. Алма-Ата, КАЗАХСТАН
b Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
c Казахский нац. ун-т им. аль-Фараби, г. Алма-Ата, КАЗАХСТАН
Аннотация:
Исследуется структура Ceprs, индуцируемая степенями позитивных предпорядков относительно вычислимой сводимости $\leq_c$. Доказывается, что структура степеней позитивных эквивалентностей определима в Ceprs. Из этого факта и результатов У. Эндрюса, Н. Швебера и А. Сорби вытекает, что теория структуры Ceprs рекурсивно изоморфна арифметике первого порядка. Показывается, что $\Sigma_1$-фрагмент этой теории разрешим, а $\Pi_3$-фрагмент наследственно неразрешим. Устанавливается, что любые две несравнимые степени в Ceprs не обладают точной верхней гранью, а среди минимальных степеней структуры Ceprs в точности две являются $c$-степенями позитивных линейных предпорядков.
Ключевые слова:
позитивный предпорядок, вычислимая сводимость, структура, индуцируемая степенями позитивных предпорядков относительно вычислимой сводимости.
Поступило: 19.03.2020 Окончательный вариант: 21.10.2020
Образец цитирования:
С. А. Бадаев, Н. А. Баженов, Б. С. Калмурзаев, “О структуре позитивных предпорядков”, Алгебра и логика, 59:3 (2020), 293–314; Algebra and Logic, 59:3 (2020), 201–215
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2615 https://www.mathnet.ru/rus/al/v59/i3/p293
|
Статистика просмотров: |
Страница аннотации: | 231 | PDF полного текста: | 34 | Список литературы: | 35 | Первая страница: | 6 |
|