Специальные классы позитивных предпорядков
Ключевые слова:
позитивный предпорядок, позитивная эквивалентность, вычислимая сводимость, предполный, слабо предполный, минимальный предпорядок.Аннотация
Мы исследуем позитивные предпорядки относительно вычислимой сводимости. Предлагается подход, позволяющий переносить известные понятия теории позитивных эквивалентностей на позитивные предпорядки.
Показано, что каждый класс позитивных предпорядков специального вида (предполных, e-полных, слабо предполных,
эффективно конечных предполных и эффективно неотделимых предпорядков) содержит бесконечно много несравнимых элементов и содержит универсальный в этом классе предпорядок. Мы строим пару несравнимых тёмных позитивных предпорядков, имеющих наибольшую нижнюю грань. Показано, что для любого не универсального позитивного предпорядка P существует бесконечно много попарно несравнимых минимальных слабо предполных позитивных предпорядков, несравнимых с P.
