Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics
I was thinking one can do things like define base case Multi(x, y, z) where y is 0 and z is 0, and then define Multi(x,y,z) being there exist z which is the sum of z2 from Multi(x, y2, z2) and y, where y2 is the predecessor of y?
Apparently for some reason this is not allowed? I assume this is to do with: "Presburger arithmetic is not strong enough to quantify over sequences", but why? what is the reason? is it because the induction schema is different between the two arithmetics?
There is no difference in induction between Peano arithmetic and Presburger arithmetic. In fact, there is only one difference between Peano arithmetic and Presburger arithmetic which is:
Peano arithmetic includes both addition and multiplication, while Presburger arithmetic only includes addition.
Once you include both addition and multiplication, you can represent any primitive recursive function (such as exponentiation) in Peano arithmetic. See proof here: http://www.cs.cornell.edu/courses/cs4860/2009sp/lec-22.pdf
The way you are defining multiplication is recursively as follows:
$$M(x,0) = 0$$ $$M(x, S(y)) = M(x, y) + x$$
That does not mean that a multiplication function with these properties exists. In Peano arithmetic, we assume it exists while in Presburger there is no such assumption. For a more detailed explanation on why such a definition doesn't work see my answer to a similar question: Why is it impossible to define multiplication in Presburger arithmetic?