{
  "id": "2405.08422",
  "version": "v1",
  "published": "2024-05-14T08:31:29.000Z",
  "updated": "2024-05-14T08:31:29.000Z",
  "title": "Hereditary undecidability of fragments of some elementary theories",
  "authors": [
    "Vladimir E. Karpov"
  ],
  "comment": "in Russian language",
  "categories": [
    "math.LO"
  ],
  "abstract": "It is well known that whenever a class of structures $\\mathcal{K}_1$ is interpretable in a class of structures $\\mathcal{K}_2$, then the hereditary undecidability of (a fragment of) the theory of $\\mathcal{K}_1$ implies the hereditary undecidability of (a suitable fragment of) the theory of $\\mathcal{K}_2$. In the present paper, we construct a $\\Sigma_1$-interpretation of the class of all finite bipartite graphs in the class of all pairs of equivalence relations on the same finite domain; from this we obtain the hereditary undecidability of the $\\Sigma_2$-theory of the second class. Next, we construct a $\\Sigma_1$-interpretation of the class of all pairs of equivalence relations on the same finite domain in the class of all pairs consisting of a linear ordering and an equivalence relation on the same finite domain; this gives us the hereditary undecidability of the $\\Sigma_2$-theory of the second class. The corresponding results are, in a sense, optimal, since the $\\Pi_2$-theories of the classes under consideration are decidable. Keywords: undecidability, elementary theories, prefix fragments",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-05-14T08:31:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hereditary undecidability",
      "elementary theories",
      "finite domain",
      "equivalence relation",
      "second class"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "ru",
      "license": "arXiv",
      "status": "editable"
    }
  }
}