On undecidability degree of theory of figures in linear spaces
https://doi.org/10.26907/2949-3919.2024.4.51-65
Abstract
We study the additive theory of arbitrary figures in linear spaces, that is, the theory of addition extended to sets of vectors. Our main result is the following: if a linear space is infinite, then the additive theory of figures allows to interpret second-order arithmetic and, therefore, has this or higher degree of undecidability. For countably infinite spaces, we prove the opposite result, the theory of figures can be interpreted in second-order arithmetic. Therefore, these theories are algorithmically equivalent. For uncountable spaces, the last question remains open. We show that for spaces of different cardinalities, the additive theories of figures can be elementary non-equivalent.
About the Author
S. M. Dudakov
Tver State University; HSE University
Russian Federation
Russian Federation
Sergey Mikhailovich Dudakov
33 Zhelyabova str., Tver 170100;
6 Usacheva str., Moscow 119048
References
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. B.N. Karlov, On elementary equivalence of some unoids and unoids of their subsets, Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics] (3), 18–32 (2021) [in Russian]. 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. A.I. Kostrikin, Yu.I. Manin, Linear algebra and geometry, CRC Press, London, 1997. DOI: https://doi.org/10.1201/9781466593480
11. H. Rogers, Theory of recursive functions and effective computability, MIT Press, Cambridge, Mass., 1967.
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
Review
For citations:
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
Views:
67
Email this article 