A strong version of Cobham's theorem

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