Question

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.

Answer 1

From a paper by Françoise Point, "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.