Специальные классы позитивных предпорядков
Ключевые слова:
positive preorder, ceer, computable reducibility, precomplete, weakly precomplete, minimal preorderАннотация
Мы исследуем позитивные предпорядки относительно вычислимой сводимости. Предложен подход, позволяющий переносить известные понятия теории позитивных эквивалентностей на позитивные предпорядки. Показано, что каждый из специальных классов позитивных предпорядков (предполных, e-полных, слабопредполных, эффективно конечно предполных, эффективно неотделимых предпорядков) содержит бесконечно много несравнимых элементов, а также универсальный объект. Мы построили пару несравнимых тёмных позитивных предпорядков, имеющих инфимум. Доказано, что для каждого неуниверсального позитивного предпорядка P существует бесконечно много попарно несравнимых минимальных слабо предполных позитивных предпорядков, несравнимых с P.
Опубликован
2023-06-29
Выпуск
Раздел
МАТЕМАТИЧЕСКАЯ ЛОГИКА, АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ