This is an old revision of the document!

Definition of Presburger Arithmetic

Minimalistic Language of Presburger Arithmetic

$(\mathbb{N},+)$ where $\mathbb{N} = \{0,1,2,\ldots\}$ and $+$ is addition of natural numbers. We consider of all interpretations with domain $\mathbb{N}$ where $+$ is interpreted as addition of natural numbers (these interpretations differ only in values for free variables, not in truth value for sentences).

This language is a good motivation, illustrates the simplicity, but is very far from allowing QE. For example, it does not have a name for zero, so we cannot express $\forall x. x+y=x$ .

We instead look at $(\mathbb{Z},+,\le,0)$ where $\mathbb{Z}$ is the set of integers.