Scholarlink

Abstract <p> We construct a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\Sigma_1\)</EquationSource> </InlineEquation>-interpretation of the class <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(BiG_{\mathrm{fin}}\)</EquationSource> </InlineEquation> of all finite bipartite graphs in the class <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2Eq_{\mathrm{fin}}\)</EquationSource> </InlineEquation> of all pairs of equivalence relations with common finite domain; this gives the hereditary undecidability of the <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\Sigma_2\)</EquationSource> </InlineEquation>-theory of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(2Eq_{\mathrm{fin}}\)</EquationSource> </InlineEquation>. Next, we construct a <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\Sigma_1\)</EquationSource> </InlineEquation>-interpretation of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(2Eq_{\mathrm{fin}}\)</EquationSource> </InlineEquation> in the class <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(LEq_{\mathrm{fin}}\)</EquationSource> </InlineEquation> of all pairs consisting of a linear ordering and an equivalence relation with common finite domain; this gives the hereditary undecidability of the <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\Sigma_2\)</EquationSource> </InlineEquation>-theory of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(LEq_{\mathrm{fin}}\)</EquationSource> </InlineEquation>. The results obtained are, in a certain sense, optimal, since the <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\Pi_2\)</EquationSource> </InlineEquation>-theories of the classes under consideration are decidable. </p>

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

On Hereditarily Undecidable Fragments of Basic Elementary Theories

  • 期刊论文

  • 发表日期：

    2025年8月1日

查看全文
  • V. E. Karpov,
  • S. O. Speranski

摘要

Abstract

We construct a \(\Sigma_1\) -interpretation of the class \(BiG_{\mathrm{fin}}\) of all finite bipartite graphs in the class \(2Eq_{\mathrm{fin}}\) of all pairs of equivalence relations with common finite domain; this gives the hereditary undecidability of the \(\Sigma_2\) -theory of \(2Eq_{\mathrm{fin}}\) . Next, we construct a \(\Sigma_1\) -interpretation of \(2Eq_{\mathrm{fin}}\) in the class \(LEq_{\mathrm{fin}}\) of all pairs consisting of a linear ordering and an equivalence relation with common finite domain; this gives the hereditary undecidability of the \(\Sigma_2\) -theory of \(LEq_{\mathrm{fin}}\) . The results obtained are, in a certain sense, optimal, since the \(\Pi_2\) -theories of the classes under consideration are decidable.