1. Теоретические проблемы математики
Программа 1.1. Исследования в области алгебры и математической логики
Изучены типы изоморфизмов и элементарные теории полурешеток Роджерса. Доказано несовпадение типов изоморфизма вычислимых нумераций семейств множеств из различных уровней арифметической иерархии. Установлена бесконечность элементарных типов полурешеток Роджерса в каждом уровне арифметичес кой иерархии. Доказана формульная определимость главной подрешетки полурешетки Роджерса конечного частично упорядоченного множества. Для доказательства потребовалось найти обобщение теоремы Денисова о продолжении вложений полурешеток Лахлана на идеалы полурешеток Роджерса.
Получено описание всех подмножеств в группе автоморфизмов упорядочения на рациональных числах, определимых в языке первого порядка, а также в группах таких автоморфизмов, вычислимых в идеалах тьюринговых степеней.
Доказана сильная разрешимость проективного свойства Бета в расширениях модальной логики Гжегорчика.
Для всех элементарных теорий булевых алгебр найдены точные оценки для перехода от n-конструктивности моделей (разрешимости Sn-диаграммы) к сильной конструктивизируемо сти (существованию представления с разрешимой диаграммой первого порядка).
Доказано, что класс решеток, вложимых в решетки подполугрупп n-нильпотентных полугрупп, является конечно-базируемым многообразием. Установлено, что класс решеток, вложимых в решетки подполугрупп свободных полугрупп, совпадает с классом решеток, вложимых в прямые произведения конечных ограниченных снизу решеток.
Доказана реализуемость всех возможных пар вида «квазипорядок Рудина—Кейслера; функция распределения числа предельных моделей» в классе теорий с конечным числом счетных моделей.
Изучены связи между строением конечной группы и свойствами ее графа простых чисел. Получен критерий смежности в графе простых чисел для всех конечных простых групп. Для графа простых чисел каждой конечной простой группы найдены: независимое множество с наибольшим числом вершин; независимое множество с наибольшим числом вершин, содержащее 2, и порядки этих множеств.
Доказана теорема Лагранжа для конечных луп Муфанг.
Построены генераторы для порождения случайных нормальных форм для свободных конструкций свободных групп и алгоритмы для решения классических алгоритмических проблем в них. Доказано, что эти алгоритмы являются полиномиальными на генерическом (большом) множестве входных данных.
