2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ A proposition is a closed form in the language of the system. You cannot define a proposition recursively, because that is not a closed formula in the language of the system. You can define exponentiation in Peano because you can apply numerical tricks - addition and multiplication together gives you enough complexity. $\endgroup$ Mar 2 '15 at 14:26
2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Perhaps one could say the same thing in a different way: the only difference between induction in PA and induction in Presberger arithmetic is that induction in PA applies to all formulas with addition and/or multiplication, while in Presberger arithmetic induction only applies to formulas that do not have multiplication, because all formulas in Presberger arithmetic are required to be in terms of addition only. $\endgroup$ Feb 8 '16 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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