A strong version of Cobham's theorem

Abstract

Let $k,\ell \ge 2$ be two multiplicatively independent integers. Cobham's famous theorem states that a set $X\subseteq \mathbb{N}$ is both $k$-recognizable and $\ell$-recognizable if and only if it is definable in Presburger arithmetic. Here we show the following strengthening: let $X\subseteq {\mathbb{N}}^m$ be $k$-recognizable, let $Y\subseteq {\mathbb{N}}^n$ be $\ell$-recognizable such that both $X$ and $Y$ are not definable in Presburger arithmetic. Then the first-order logical theory of $(\mathbb{N},+,X,Y)$ is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of $(\mathbb{N},+,X)$ is decidable.