20
$\begingroup$

I read that Presburger arithmetic is decidable while Peano arithmetic is undecidable, and actually Peano arithmaetic extends Presburger arithmetic just with the addition of the multiplication operator. Can someone please give me the 'intutive' idea behind this?

Or probably a formula in Peano arithmetic that cannot be proved. Does it have something to do with the self reference paradox in Goedel's Incompleteness Theorem?

Regards

  • 4
    It has everything to do with the self-reference aspect of Godel's First Incompleteness Thm., which is effectively a rigorous form of the Liar's Paradox. It requires multiplication because to obtain the self-reference Godel develops an effective numbering of formulas (and proofs) that uses prime factorization. So if we have only addition, the proof will not go through (because you don't have prime factors to talk about).2011-01-07
  • 0
    @hardmath: so there is no bijection between numbers and formulas which can be expressed only with addition?2011-01-07
  • 0
    I edited the tags since the question isn't about algebraic number theory.2011-01-07
  • 1
    What I'm about to say is very "intuitive" and I honestly don't know if it can be formalized in any sense, but this is something my first logic professor said once: since, in a sense, natural number multiplication is "adding a number to itself finitely many times", multiplication sneaks in a reference to "finite" vs. "infinite". Theories with finite models are decidable, so the infinite "lurks" in undecidability; it is this sudden ability to refer, indirectly, to the infinite that causes problems. Steven Stadnicki's answer seems to me to mesh well with this idea.2011-01-07

4 Answers 4