# Blog Archives

# Topic Archive: Presburger arithmetic

# Definability in linear fragments of Peano arithmetic

In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal *k*, the *k*-linear arithmetic (*LA _{k}*) is a full-induction arithmetical theory extending Presburger arithmetic by

*k*non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild.

I will present a quantifier elimination result for *LA _{1}* and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of

*LA*(or any

_{2}*LA*with

_{k}*k*at least

*2*) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible).

There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for *LA _{1}* implies interesting properties of the structure of saturated models of Peano arithmetic.

Slides from this talk.