MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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.

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
Perhaps this is clear to you, but...though I agree that one can define exponentiation from (N,+,x,0,1), simply giving a recursion won't do...or one could define multiplication from addition in a similar way. One must give a two place predicate involving only the symbols (+,x,0,1) and logical apparatus satisfied precisely by pairs (x,c^x). The name "f" can't come into it. So one needs coding tricks to capture sequences in order to do recursion. – David Feldman Aug 4 '12 at 18:30
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.