# Why is it impossible to define multiplication in Presburger arithmetic yet possible to define exponentiation in Peano Arithmethic?

Hello my question is related to Why is it impossible to define multiplication in Presburger arithmetic? and to How is exponentiation defined in Peano arithmetic?. I would have preferred to add it as a comment to one of the above discussions but I don't have commenting powers yet :-( Anyway, when I look at the answer to how exponentiation is defined, using sequences and the Chinese remainder theorem, I assume that Presburger is simply not powerful enough to play the same trick to define $\times$ in terms of +?

thanks

• The proof that exponentiation is Diophantine is weirdly technical and off-putting, but it is the reason. Jan 25, 2015 at 1:58
• Specifically, there is a polynomial $f(x,y,z,w_1,w_2,\dots,w_n)$ such that for any $(x,y,z)\in\mathbb N$, $\exists w_1,w_2,\dots,w_n$ yielding a solution to $f$ if and only if $x^y=z$. That's a deep and weird result. Note that a polynomial can be expressed in terms of sum and product only: $x^3+3xy+z=x\cdot x\cdot x + 3\cdot x\cdot y + z$. Jan 25, 2015 at 2:01
• Once you've defined ore assumed $+$ and $\times$, you can define exponentiation without encodings or the like using this result. @CarlMummert Jan 25, 2015 at 2:08
• @CarlMummert Having read the proof that exponentiation is Diophantine, I saw nowhere in it that it assumed a particular model. Maybe I'm wrong. Jan 25, 2015 at 2:12
• Sigh, no, you just need to prove that the triples $(x,y,z)$ satisfy the recursive definition of triples satisfying it, including that it is single-valued. You don't need to already have exponentiation defined in the structure. @CarlMummert Jan 25, 2015 at 2:17