Interpretations of Linear Orderings in Presburger Arithmetic

Abstract

Presburger Arithmetic $\mathrm{PrA}$ is the true theory of natural numbers with addition. We consider linear orderings interpretable in Presburger Arithmetic and establish various necessary and sufficient conditions for interpretability depending on dimension $n$ of interpretation. We note this problem is relevant to the interpretations of Presburger Arithmetic in itself, as well as the characterization of automatic orderings. For $n=2$ we obtain the complete criterion of interpretability.

10 pages