ПРОБЛЕМЫ АЛГОРИТМИЧЕСКОЙ РАЗРЕШИМОСТИ И АКСИОМАТИЗАЦИИ АЛГЕБРЫ КОНЕЧНЫХ ПОДМНОЖЕСТВ ДЛЯ БИНАРНЫХ ОПЕРАЦИЙ

Известия РАН. Серия математическая. 2025. Т. 89. № 2. С. 3–24.

Дудаков С. М.

Рассматриваются алгебры конечных подмножеств, когда исходная алгебра является бесконечным группоидом. Доказывается, что для линейных пространств над полями конечной характеристики теория построенной алгебры алгоритмически эквивалентна элементарной арифметике. Далее этот результат обобщается на произвольные бесконечные абелевы группы. В качестве следствия получается, что общая теория классов всех алгебр конечных подмножеств имеет степень неразрешимости, не меньшую чем элементарная арифметика, для широкого круга исходных алгебр: абелевых групп, произвольных групп, моноидов, полугрупп, группоидов. Это также доказывает невозможность рекурсивной аксиоматизации теорий таких классов. Другим следствием является неразрешимость и невозможность рекурсивной аксиоматизации теории решетки подалгебр для абелевых групп конечной экспоненты, а также теорий классов таких решеток для групп, моноидов и полугрупп.Библиография: 17 наименований.

Ключевые слова: линейное пространство, алгоритмическая неразрешимость, algorithmic undecidability, first-order arithmetic, linear space, subalgebra lattice, recursive axiomatizability, элементарная арифметика, рекурсивная аксиоматизируемость, решетка подалгебр