Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions

Abstract

We study the extension of Presburger arithmetic by the class of sub-polynomial Hardy field functions, and show the majority of these extensions to be undecidable. More precisely, we show that the theory $\mathrm{Th}(\mathbb{Z};<,+,\lfloor f\rceil )$, where $f$ is a Hardy field function and $\lfloor \cdot \rceil$ the nearest integer operator, is undecidable when $f$ grows polynomially faster than $x$. Further, we show that when $f$ grows sub-linearly quickly, but still as fast as some polynomial, the theory $\mathrm{Th}(\mathbb{Z};<,+,\lfloor f\rceil )$ is undecidable.

17 pages