|
MATHEMATICS
On interpretations of Presburger arithmetic in Büchi arithmetics
A. A. Zapryagaev National Research University "Higher School of Economics", Moscow, Russia
Abstract:
Büchi arithmetics $\mathrm{BA}_n$, $n\ge2$, are extensions of Presburger arithmetic with an unary functional symbol $V_n(x)$ denoting the largest power of $n$ that divides $x$. Definability of a set in $\mathrm{BA}_n$ is equivalent to its recognizability by a finite automaton receiving numbers in their $n$-ary expansion. We consider the interpretations of Presburger Arithmetic in the standard model of $\mathrm{BA}_n$ and show that each such interpretation has an internal model isomorphic to the standard one. This answers a question by A. Visser on the interpretations of certain weak arithmetical theories in themselves.
Keywords:
formal arithmetics, interpretations, automatic structures, automatic Abelian groups.
Citation:
A. A. Zapryagaev, “On interpretations of Presburger arithmetic in Büchi arithmetics”, Dokl. RAN. Math. Inf. Proc. Upr., 510 (2023), 3–7; Dokl. Math., 107:2 (2023), 89–92
Linking options:
https://www.mathnet.ru/eng/danma371 https://www.mathnet.ru/eng/danma/v510/p3
|
Statistics & downloads: |
Abstract page: | 128 | References: | 24 |
|