On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces

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 admits interpreting second-order arithmetic and, therefore, it has such 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. For spaces of different cardinalities, we show that the additive theories of figures can be elementary non-equivalent. Then, we consider the case of countable figures only. In this case, we prove a variant of the Löwenheim–Skolem theorem. At last, we establish the exact undecidability degree that also corresponds to second-order arithmetic for original spaces of any infinite cardinality that is not less than continuum.