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

Lobachevskii Journal of Mathematics. 2025. Vol. 46. No. 12. P. 6092–6102.

Dudakov S.

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.

Keywords: uncountability, Countable, algorithmic undecidability, linear space, second-order arithmetic, subset algebra