# Definition of Presburger Arithmetic

## Minimalistic Language of Presburger Arithmetic

Consider and consider as the set of all interpretations with domain where is interpreted as addition of natural numbers (these interpretations differ only in values for free variables. This is one definition of Presburger arithmetic over natural numbers.

This theory is very simple to describe, but it is very far from allowing quantifier-elimination. For example, it does not have a name for zero, so we cannot express . It also does not have a way to express .

## Language of Presburger Arithmetic that Admits QE

We look at the theory of integers with addition.

• introduce constant for each integer constant
• to be able to restrict values to natural numbers when needed:
• introduce not only addition but also subtraction
• to conveniently express certain expressions, introduce function for each , to be interpreted as multiplication by a constant, . We write as • to enable quantifier elimination from introduce for each predicate (divisibility by constant)

The resulting language 