# Beyond Presburger Arithmetic

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.

-

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.
You're right - it was misleading for me to describe the recursive definition, when it requires a more complicated formula to define $(x,c^x)$. I didn't follow the golden rule: look for every instance of "Of course" -- that's where the mistakes are. – Marty Aug 4 '12 at 22:03