On undecidability degree of theory of figures in linear spaces
Sergey Mikhailovich Dudakov · Mathematics and Theoretical Computer Science · 2025
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.