5
$\begingroup$

Godel proved that every system strong enough to include standard arithmetic with multiplication is incomplete. But I've read that systems that do not include multiplication are complete. But multiplication is simply repeated addition. So, how can one system be complete and the other incomplete? I realize that the completeness is provable with respect to Presburger arithmetic, but I want to understand why. What is the deep difference between the two systems that allows this?

  • 5
    The fact that you can define "multiplying by 2/3/4/5/6/..." each on its own does not mean that you can define multiplication. Furthermore, sometimes you cannot even define addition. Lastly, sometimes you have addition and multiplication but you don't have a way of defining the integers so you cannot really express the needed ideas for the incompleteness theorems.2012-02-03
  • 3
    It is imprecise to say "every system strong enough to include standard arithmetic with multiplication is incomplete". The system *must* satisfy certain technical restrictions (intuitively, there must be an algorithm that decides whether a given statement is an axiom or not), and you must be able to define the integers.2012-02-03
  • 1
    As a concrete example of Asaf Karagila's final remark, consider the first-order theory of the real line. It's consistent and complete. The incompleteness theorems don't apply, because in this theory there is no way to express the notion that $x$ is an integer.2012-02-03
  • 1
    First time I've heard that "addition is repeated multiplication". I presume it's essentially a typo. If someone had written "thoerem" I would fix it, but I hesitate in a case like this.2012-02-03
  • 0
    Thanks for all these great responses! "first time I've heard addition is repeated multiplication"....oops. my brain reverses things all the time. thanks for pointing that out.2012-02-03
  • 2
    Also, Presburger arithmetic is 'closer than you think' to being incomplete - its (superexponential) hardness is a consequence of multiplication _almost_ being expressible in it. Have a look at http://math.stackexchange.com/questions/16665/why-is-peano-arithmetic-undecidable/16707#16707 for more details on this...2012-02-03

1 Answers 1