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