Эта публикация цитируется в
7 статьях
О структуре позитивных предпорядков
С. А. Бадаевa,
Н. А. Баженовb,
Б. С. Калмурзаевca a Казахстанско-Британский техн. ун-т, г. Алма-Ата, КАЗАХСТАН
b Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
c Казахский нац. ун-т им. аль-Фараби, г. Алма-Ата, КАЗАХСТАН
Аннотация:
Исследуется структура
Ceprs, индуцируемая степенями позитивных предпорядков относительно вычислимой сводимости
$\leq_c$. Доказывается, что структура степеней позитивных эквивалентностей определима в
Ceprs. Из этого факта и результатов У. Эндрюса, Н. Швебера и А. Сорби вытекает, что теория структуры
Ceprs рекурсивно изоморфна арифметике первого порядка. Показывается, что
$\Sigma_1$-фрагмент этой теории разрешим, а
$\Pi_3$-фрагмент наследственно неразрешим. Устанавливается, что любые две несравнимые степени в
Ceprs не обладают точной верхней гранью, а среди минимальных степеней структуры
Ceprs в точности две являются
$c$-степенями позитивных линейных предпорядков.
Ключевые слова:
позитивный предпорядок, вычислимая сводимость, структура, индуцируемая степенями позитивных предпорядков относительно вычислимой сводимости.
УДК:
512.5:510.6
Поступило: 19.03.2020
Окончательный вариант: 21.10.2020
DOI:
10.33048/alglog.2020.59.301