(Minor nitpick. Presburger arithmetic can represent integers and is decidable: https://en.wikipedia.org/wiki/Presburger_arithmetic You were probably looking for Peano arithmetic.)