Проблемы алгоритмической разрешимости и аксиоматизации алгебры конечных подмножеств для бинарных операций
- Авторы: Дудаков С.М.1,2
-
Учреждения:
- Тверской государственный университет
- Национальный исследовательский университет "Высшая школа экономики", г. Москва
- Выпуск: Том 89, № 2 (2025)
- Страницы: 3-24
- Раздел: Статьи
- URL: https://journal-vniispk.ru/1607-0046/article/view/303944
- DOI: https://doi.org/10.4213/im9579
- ID: 303944
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Рассматриваются алгебры конечных подмножеств, когда исходная алгебра является бесконечным группоидом. Доказывается, что для линейных пространств над полями конечной характеристики теория построенной алгебры алгоритмически эквивалентна элементарной арифметике. Далее этот результат обобщается на произвольные бесконечные абелевы группы. В качестве следствия получается, что общая теория классов всех алгебр конечных подмножеств имеет степень неразрешимости, не меньшую чем элементарная арифметика, для широкого круга исходных алгебр: абелевых групп, произвольных групп, моноидов, полугрупп, группоидов. Это также доказывает невозможность рекурсивной аксиоматизации теорий таких классов. Другим следствием является неразрешимость и невозможность рекурсивной аксиоматизации теории решетки подалгебр для абелевых групп конечной экспоненты, а также теорий классов таких решеток для групп, моноидов и полугрупп. Библиография: 17 наименований.
Об авторах
Сергей Михайлович Дудаков
Тверской государственный университет; Национальный исследовательский университет "Высшая школа экономики", г. Москва
Автор, ответственный за переписку.
Email: sergeydudakov@yandex.ru
доктор физико-математических наук, доцент
Список литературы
- S. Feferman, R. Vaught, “The first order properties of products of algebraic systems”, Fund. Math., 47 (1959), 57–103
- A. Mostowski, “On direct products of theories”, J. Symb. Log., 17 (1952), 1–31
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, Алгоритмы: построение и анализ, 3-е изд., Вильямс, М., 2013, 1328 с.
- T. Tamura, J. Shafer, “Power semigroups”, Math. Japon., 12 (1967), 25–32
- S. Dudakov, B. Karlov, “On decidability of theories of regular languages”, Theory Comput. Syst., 65:3 (2021), 462–478
- T. Place, M. Zeitoun, “Separating regular languages with first-order logic”, Log. Methods Comput. Sci., 12:1 (2016), 5, 31 pp.
- M. Ferrara, M. Trombetti, “A lattice-theoretic characterization of pure subgroups of Abelian groups”, Ric. Mat., 72:2 (2023), 779–783
- S. M. Dudakov, “On undecidability of concatenation theory for one-symbol languages”, Lobachevskii J. Math., 41:2 (2020), 168–175
- A. Blumensath, E. Grädel, “Automatic structures”, Proceedings of the 15th annual IEEE symposium on logic in computer science (Santa Barbara, CA, 2000), IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 51–62
- С. М. Дудаков, “Об алгоритмических свойствах алгебры конечных подмножеств некоторых уноидов”, Вестник ТвГУ. Сер. Прикл. матем., 2019, № 4, 108–116
- S. M. Dudakov, “On undecidability of subset theory for some monoids”, J. Phys. Conf. Ser., 1902 (2021), 012060, 11 pp.
- S. M. Dudakov, “On undecidability of finite subsets theory for torsion Abelian groups”, Mathematics, 10:3 (2022), 533, 14 pp.
- А. И. Кострикин, Ю. И. Манин, Линейная алгебра и геометрия, Изд-во Моск. ун-та, М., 1980, 320 с.
- Л. Фукс, Бесконечные абелевы группы, т. 1, Мир, М., 1974, 335 с.
- С. Ленг, Алгебра, Мир, М., 1968, 564 с.
- G. S. Boolos, J. P. Burgess, R. C. Jeffrey, Computability and logic, 5th ed., Cambridge Univ. Press, Cambridge, 2007, xiv+350 pp.
- Б. Н. Карлов, “Об элементарной эквивалентности некоторых уноидов и уноидов их подмножеств”, Вестник ТвГУ. Сер. Прикл. матем., 2021, № 3, 18–32
Дополнительные файлы
