It is known that there are a number of expansions of the structure $\mathfrak{N}:=(\mathbb{N};+)$ which are decidable (= have computable theories); one such example is the expansion by a predicate naming the powers of $2$, or even the function $x\mapsto 2^x$, see [here](https://mathoverflow.net/questions/52433/theory-of-addition-and-a-predicate-that-recognizes-powers-of-2). In each such case that I'm aware of, the proof of decidability of the expansion in fact establishes something more, namely that Presburger arithmetic + a small set of axioms for the additional structure is a complete theory.

This motivates the following question (conflating relations and symbols naming them for simplicity):

> For $n\in\mathbb{N}$ and $A\subseteq\mathbb{N}^n$, let $\mathfrak{N}_A$ be the expansion of $\mathfrak{N}$ by (a relation symbol interpreted as) $A$. If $\mathfrak{N}_A$ is decidable, must there be some finite $\{+,A\}$-theory $T$ such that $T$ + the full induction scheme for $\{+,A\}$-formulas is complete?

My suspicion is that the answer is **negative**, but I don't see how to prove it.