RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2023 Volume 510, Pages 3–7 (Mi danma371)

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.

UDC: 510.652

Presented: L. D. Beklemishev
Received: 14.11.2022
Revised: 31.01.2023
Accepted: 03.02.2023

DOI: 10.31857/S2686954322600641


 English version:
Doklady Mathematics, 2023, 107:2, 89–92

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024