Scholarlink

Abstract <p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • S. M. Dudakov

摘要

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 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.