9
$\begingroup$

Goedel's incompleteness tells us that any system containing Robinson arithmetic is incomplete. OTOH, Presburger Arithmetic, which contains only the successor and addition, is complete. I'm pretty sure that I have read that it possible to define a complete arithmetic with only sucessor and multiplication axioms. So, this raises the question about what is special about the combination of addition and multiplication.

In reviewing the proof of Goedel's theorem, I thought I had located the key point: the $\beta$-function involves both addition and mutliplication. Without that, we cannot get to the primitive recursive functions, which means we cannot arithmetize syntax, so you cannot form the Goedel sentence, and there is nothing that says it cannot be proved. This isn't a 100% satisfying, but it makes a certain amount of sense.

But then I learned that there are self-verifying theories which can arithmetize syntax despite being much weaker than Robinson arithmetic. So that cannot be right.

Is there, then a simple explanation of why the combination of addition and multiplication is necessary for incompleteness to kick in?

$\endgroup$
  • $\begingroup$ I didn't think I would ever say this, and I don't know whether it's right, but this question could be a better fit over at math overflow $\endgroup$ – Arthur Sep 23 '17 at 7:18
  • $\begingroup$ Noah's answer already identifies "finite sequences" as the key. Any system that can perform basic reasoning about finite sequences will necessarily be incomplete. But I wish to point out that your question is based on a misconception (that I too once had) that it is due to some special interaction between addition and multiplication, or at least due to the number theoretic structure of the naturals. That is really quite false! See this post that explains why computability is the key. Note that the theory of concatenation is weak but incomplete. $\endgroup$ – user21820 Mar 27 '18 at 15:40
7
$\begingroup$

Figuring out exactly how much "strength" a system needs to have before Godel applies to it is a complicated task, and lots of questions have been asked on this topic both here at at mathoverflow (see e.g. this question or this other question).

However, there is a snappy answer to the more specific question

Is there, then a simple explanation of why the combination of addition and multiplication is necessary for incompleteness to kick in?

The necessary (but not sufficient!) component here is being able to represent finite sequences - this is necessary to even express the consistency of the system within its own language! If we have both addition and multiplication, we can do this via the $\beta$-function as you observe (and incidentally, this is why it's much easier to prove the incompleteness of PA with exponentiation, since throwing exponentiation into the mix makes it really easy to code sequences appropriately). If, however, we only have one of the two, we can't; an earlier math.stackexchange question shows that there is no pairing function definable in $(\mathbb{N};+)$, and it's not hard to show that the same is true for $(\mathbb{N}, \times)$ as well.

This leaves open the question of how we can have theories that can talk about $+$ and $\times$ and still avoid Godel (note that I was careful to say that coding sequences is not a sufficient condition for Godel to apply!). The culprit here is that these theories can talk about $+$ and $\times$, but "basic facts" about these operations aren't provable in the theory alone - e.g. the theory cannot prove that $\times$ is total! (The way this works syntactically is that, instead of a binary operation symbol, we have a ternary relation symbol representing "$a$ times $b$ equals $c$.") So while it's technically true to say that such a theory can talk about $+$ or $\times$, that doesn't mean what we tend to think it means: roughly speaking, for Godel's argument to apply we need to be able to code sequences appropriately and prove basic facts about the (image within the theory of the) coding apparatus; and it's this second part that self-verifying theories cleverly dodge.

$\endgroup$

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.