Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
About Godel Incompleteness and Multiplication
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?
logic incompleteness
mathNotebook
mathNotebookmathNotebook
$\begingroup$ 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. $\endgroup$ – Asaf Karagila♦ Feb 3 '12 at 10:05
$\begingroup$ 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. $\endgroup$ – Arturo Magidin Feb 3 '12 at 15:56
$\begingroup$ 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. $\endgroup$ – Ben Crowell Feb 3 '12 at 15:58
$\begingroup$ 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. $\endgroup$ – Michael Hardy Feb 3 '12 at 16:56
$\begingroup$ 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 math.stackexchange.com/questions/16665/… for more details on this... $\endgroup$ – Steven Stadnicki Feb 3 '12 at 18:48
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.
Mark BeadlesMark Beadles
$\begingroup$ Thanks! This had been bothering me for awhile. $\endgroup$ – mathNotebook Feb 3 '12 at 18:22
Thanks for contributing an answer to Mathematics Stack Exchange!
Not the answer you're looking for? Browse other questions tagged logic incompleteness or ask your own question.
Why is Peano arithmetic undecidable?
Why is the set of all true first-order statements about non-negative integers in the language with only equality, $+$ and $\times$ undecidable?
Why a system becomes incomplete once it's capable of doing arithmetic?
How to show incompleteness of second order logic?
What is "magic" about the combination of addition and multiplication in formal arithmetic?
FOL and Gödel's Incompleteness Theorem 1
Does infinity cause incompleteness in formal systems? Is a finite formal system complete?
How do "we" know the incompleteness of second-order logic?