Alexander Zapryagaev: Presburger arithmetic and related theories

Abstract

The talk introduces Presburger arithmetic $\mathrm{PrA}$, the theory of natural numbers with addition, and Büchi arithmetics $\mathrm{BA}_n$, a series of algorithmically decidable extensions of $\mathrm{PrA}$. The main logical and algorithmic properties of these theories and their fragments are explored, both classical and recently obtained. Various expressibility results are introduced as well as some data on the structure of the non-standard models of $\mathrm{PrA}$ and $\mathrm{BA}_n$. We discuss the Büchi-Bruyère theorem, establishing the direct connection between interpretations in Büchi arithmetics and automatic structures, as well as the Cobham-Semënov theorem, allowing to compare the expressive powers of $\mathrm{BA}_n$ for different $n$. The speaker’s result on the non-existence of interpretations from $\mathrm{BA}_n$ to itself unless isomorphic to the trivial one is presented and put in context.