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. 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):
(Question 1) 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 axiomatizes $Th(\mathfrak{N}_A$)?
My suspicion is that the answer is negative, but I don't see how to prove it. There is, though, a natural(-to-me) additional hypothesis on $A$ we can add to make a positive answer more plausible:
(Question 2) What if in Question 1 we additionally required $A$ to have the property that there is a finite $\{+,A\}$-theory $S$ such that $\mathfrak{N}_A\models S$ and the characteristic function of $A$ is strongly representable in $S$ + the full induction scheme for $\{+,A\}$-formulas?
I have no intuition for what the answer for Question 2 may be.
