A Dichotomy for $k$-automatic expansions of Presburger Arithmetic

Abstract

Let $k\ge 2$ and let $X$ be a subset of the natural numbers that is $k$-automatic and not eventually periodic. We show that the following dichotomy holds: either all $k$-automatic subsets are definable in the expansion of Presburger arithmetic in which we adjoin the predicate $X$, or $(\mathbb{N},+,X)$ has the same definable sets as $(\mathbb{N},+,k^{\mathbb{N}})$.

32 pages