RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Российской академии наук. Серия математическая // Архив

Изв. РАН. Сер. матем., 2025, том 89, выпуск 2, страницы 3–24 (Mi im9579)

Проблемы алгоритмической разрешимости и аксиоматизации алгебры конечных подмножеств для бинарных операций

С. М. Дудаковab

a Тверской государственный университет
b Национальный исследовательский университет "Высшая школа экономики", г. Москва

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

Ключевые слова: алгоритмическая неразрешимость, элементарная арифметика, рекурсивная аксиоматизируемость, линейное пространство, решетка подалгебр.

УДК: 510.65

MSC: 03B25, 03G10

Поступило в редакцию: 08.02.2024
Исправленный вариант: 18.05.2024

DOI: 10.4213/im9579



© МИАН, 2025