Do there exist known examples of predicates $P$ (possibly functional) such that


1) $P$ admits a first-order definition in the language ${\Bbb N}(+,\times,0,1)$;


2) $P$ admits no definition that does not involve both $+$ and $\times$;


3) the theory of ${\Bbb N}(+,P,0,1)$ is decidable?


(Or 


3') the theory of ${\Bbb N}(\times,P,0,1)$ is decidable? 


Or even better, both.)


Last I heard (a long time ago) no one can prove the undecidability of ${\Bbb N}(+,{\rm Prime}(),0,1)$, but Alan Woods showed that standard conjectures imply the definability of multiplication in this language.



Beyond Presburger Arithmetic
From a [paper by Françoise Point](http://www.math.osu.edu/~friedman.8/pdf/0AppB072710.pdf), "On the expansion $(N, +; 2^x)$ of Presburger arithmetic," I learned of a much more general result of Semenov, “Logical theories of one-place functions on the set of natural numbers”, Izv. Akad. Nauk SSSR Ser. Mat., 47:3 (1983), 623–658. 


Semenov's result implies that Presburger arithmetic together with the function $f(x) = c^x$ is decidable for any fixed $c \geq 2$. Of course, $f$ is characterized by the fact that $f(0) = 1$ and $f(x) = c \cdot f(x-1)$ for $x > 0$. So $f$ is definable in $(N,+,\times,0,1)$.


Something about the sparseness of powers of $2$, it seems... but I haven't read the details.


