4

This might be answerable at the pure mathematical level but I'm hoping to gain some intuition here.

My understanding is that formal arithmetic systems employing only addition can be proven consistent/complete (Presburger I think?)

However Godelian incompleteness requires only one further operator, multiplication. Presumably this is in order to construct the G numbers for formulae in the system, but how does multiplication give you the tools to do this where addition does not? (Can't multiplication be rewritten as a series of additions...?)

Improve this question
3
  • You are right about Presburger arithmetic. – Mauro ALLEGRANZA Sep 29 '16 at 14:33
  • The issue is that "any number concept leading to multiplication cannot be defined in Presburger arithmetic, since that leads to incompleteness and undecidability." "Presburger arithmetic can be extended to include multiplication by constants, since multiplication is repeated addition." – Mauro ALLEGRANZA Sep 29 '16 at 14:35
  • Because while multiplication can be rewritten in Presburger for individual statements those that quantify over variables being multiplied can not be so rewritten, e.g. things like "multiplication commutes for all numbers" or "1 times any number is itself" are ineffable. This precludes the definition of Gödel numbering and blocks the construction of Gödel sentences, see philosophy.stackexchange.com/questions/37665/… – Conifold Sep 29 '16 at 17:41
4

The axioms of Peano arithmetic do not mention multiplication, but multiplication can be constructed in it from facts about addition, given complete induction. Unfortunately Peano's axiom of induction is not fully reducible to a collection of first-order statements.

The issue is not about multiplication per se, or even about the combination of addition and multiplication. The theory of Real Closed Fields has both, and is consistent and complete. The issue is about the strength of induction.

The induction axioms in Presburger arithmetic are the first order approximation of the Peano axiom, and basically do not allow for establishing facts about other facts that have, themselves, to be established inductively.

You cannot get real recursion off the ground unless you have a second order theory of counting, that allows you to represent the sets of integers for with the results are already established.

So to get a first order theory to start doing Gödel's proof, you have to bring in either infinitely many facts about addition, which are needed to establish the relevant results about multiplication, or a few facts about multiplication, itself, as additional axioms.

Improve this answer
3
  • This makes things very clear. It would be nice if you explain how this ties in to the cardinality of integers vs the cardinality of reals? – Alexander S King Sep 29 '16 at 17:18
  • 3
    By Lowenheim-Skolem, it can't. Every first-order system has countable models. So, although we cannot really get a grip on it intuitively, (it can be constructed in a way that makes sets of sentences stand for points, but that is not very helpful) there is some model between the rationals and the reals that makes up a full model of any finite, first-order axiomatization of the reals we can come up with. There is, in fact, a new countable model for each transcendental fact we add. (These models can be used to limit the complexity of proving various real-analytic results.) – user9166 Sep 29 '16 at 17:36
  • 1
    @AlexanderSKing (forgot the name tag) From a kind of hokey point of view, it has more to do with Zeno's Paradox, or Kant's Antinomy of Atomism than with cardinality. The real numbers are really in some sense simpler than the integers because of infinite divisibility -- calculus and analysis are somehow simpler than combinatorics and number theory. Space is simpler than language. – user9166 Sep 29 '16 at 20:39
2

Actually, multiplication alone does not lead to incompleteness. There is a complete system of arithmetic containing only multiplication.

From Peter Smith's An Introduction to Gödel's Theorems (2nd edition, p. 93):

Note, it isn't that multiplication is in itself somehow intrinsically intractable. In 1929 (the proof was published in his 1930), Thoralf Skolem showed that there is a complete theory for the truths expressible in a suitable first-order language with multiplication but lacking addition (or the successor function). Why then does putting multiplication together with addition and successor produce incompleteness?

The short answer is that this combination gives the language expressive power sufficient to formulate the undecided Gödel sentence.

Note that multiplication cannot be defined in terms of addition in Presburger arithmetic, because such a definition has to be recursive (e.g. like this), and you need a recursion theorem to guarantee the existence of such a recursive function. Presburger arithmetic (and even PA I think), isn't strong enough to prove the recursion theorem.

Improve this answer
0

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.