scientific article; zbMATH DE number 1512851

From MaRDI portal
Publication:4508549





The paper is devoted to the study of certain extensions of Presburger arithmetic. Let \(R=(r_{n})\) be a strictly increasing sequence of natural numbers with \(r_{0}=1\). Denote by the same letter the unary predicate \(R(x)\) expressing that \(x\) belongs to the sequence \(R\); let \(S\) be the successor function on \(R\), i.e., \(S(r_{n}) = r_{n+1}\). Two kinds of extensions are considered, namely \(\langle N, +, R \rangle\) and \(\langle N, <, R \rangle\). It is shown, under certain conditions on \(R\), that relative quantifier elimination results hold. It is also shown (a model-theoretic proof is given) that for \(R\) a sparse unary predicate the theory Th\((\langle N, +, R, S \rangle\)) is existential (a syntactic proof was given by A. L. Semenov in 1980). Further, it is discussed under which conditions a sequence \(R\) is (almost) sparse. Finally the theory of \(\langle N, <, R, S \rangle\) is examined. It is proved (by model-theoretic methods) that under certain conditions on \(R\) this theory is existential. For the entire collection see [Zbl 0939.00010].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508549)