About Godel Incompleteness and Multiplication

Question

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?

Answer 1

The operation $\times$ is not a primitive operation in Presburger arithmetic. Now, we certainly could define a convention where $\times$ is a symbol replaced with a repeated series of $+$'s, where the number of repeats equals one of the multiplicands. So $x\times2$ you could define as $x+x$, and $x\times3$ as $x+x+x$, and similarly for 4, etc. It's the etc. that is the problem.

You would have to make this definition an infinite number of times. The problem is that there is no rule of induction that allows you to define $\times$ for all possible multiplicands. You can only define multiplication for some set of constants. There is no general rule allowing you to say $x\times y$ for two variables $x$ and $y$.

This is where the weakness of the system lies. The axiom schema isn't powerful enough to define generalized multiplication of variables, and therefore isn't powerful enough to be subject to the Godel technique.