О степени неразрешимости теории фигур в линейных пространствах
https://doi.org/10.26907/2949-3919.2024.4.51-65
Аннотация
Мы изучаем аддитивную теорию произвольных фигур в линейных пространствах, т.е. теорию множеств точек/векторов, на которые естественным образом распространена операция сложения. Наш основной результат: если линейное пространство бесконечно, то аддитивная теория фигур в нем позволяет интерпретировать арифметику второго порядка и, следовательно, имеет не меньшую степень неразрешимости. Для счетно бесконечных пространств мы доказываем обратный результат: теория фигур в них может быть проинтерпретирована в арифметике второго порядка, следовательно, две такие теории алгоритмически эквивалентны. Для несчетных пространств последний вопрос остается открытым; мы показываем, что для пространств разных мощностей аддитивные теории фигур в них могут не быть элементарно эквивалентны.
Об авторе
С. М. Дудаков
Тверской государственный университет; Университет HSE (Высшая школа экономики)
Россия
Россия
Сергей Михайлович Дудаков
ул. Желябова, д. 33, г. Тверь, 170100;
ул. Усачева, д. 6, г. Москва, 119048
Список литературы
1. S.M. Dudakov, B.N. Karlov, On decidability of theories of regular languages, Theory Comput. Syst. 65 (3), 462–478 (2021). DOI: https://doi.org/10.1007/s00224-020-09995-4
2. I. Rewitzky, C. Brink, Predicate transformers as power operations. Form. Asp. Comput. 7 (2), 169–182 (1995). DOI: https://doi.org/10.1007/BF01211604
3. J. van Benthem, N. Bezhanishvili, Modal structures in groups and vector spaces, J. Logic Comput. 34 (1), 75–124 (2024). DOI: https://doi.org/10.1093/logcom/exac105
4. C. Brink, Power structures, Algebra Universalis 30 (2), 177–216 (1993). DOI: https://doi.org/10.1007/BF01196091
5. T. Tamura, J. Shafer, Power semigroups, Math. Japon. 12, 25–32 (1967).
6. Б.Н. Карлов, Об элементарной эквивалентности некоторых уноидов и уноидов их подмножеств, Вестник ТвГУ. Серия: Прикладная математика (3), 18–32 (2021). DOI: https://doi.org/10.26456/vtpmk620
7. S.M. Dudakov, On undecidability of concatenation theory for one-symbol languages, Lobachevskii J. Math. 41 (2), 168–175 (2020). DOI: https://doi.org/10.1134/S1995080220020055
8. S.M. Dudakov, On undecidability of subset theory for some monoids, J. Phys.: Conf. Ser. 1902, art. 012060 (2021). DOI: https://doi.org/10.1088/1742-6596/1902/1/012060
9. S.M. Dudakov, On undecidability of finite subsets theory for torsion abelian groups, Mathematics 10 (3), art. 533 (2022). DOI: https://doi.org/10.3390/math10030533
10. А.И. Кострикин, Ю.И. Манин, Линейная алгебра и геометрия, Наука, М., 1986.
11. Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, М., 1972.
12. G.S. Boolos, J.P. Burgess, R.C. Jeffrey, Computability and logic, Cambridge Univ. Press, Cambridge, 2007. DOI: https://doi.org/10.1017/CBO9780511804076
Рецензия
Для цитирования:
Дудаков С.М. О степени неразрешимости теории фигур в линейных пространствах. Математика и теоретические компьютерные науки. 2024;2(4):51-65. https://doi.org/10.26907/2949-3919.2024.4.51-65
For citation:
Dudakov S.M. On undecidability degree of theory of figures in linear spaces. Mathematics and Theoretical Computer Science. 2024;2(4):51-65. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.51-65
Просмотров:
53
Послать статью по эл. почте 