Topics Logic

Question I read that Gödel's incompleteness theorems don't effect Peano Arithmetic that doesn't include multiplication sign. This confuses me, since multiplication can be defined through addition. So, even if "PA without multiplication" doesn't have multiplication sign in itself, it provides everything that's needed for defining mul. sign. So what's the difference? That is, why is "PA without multiplication" (but that contains everything needed for defining mul.) different from PA (that already has multiplication defined)? From "Gödel without tears": "The formalized interpreted language L contains the language of basic arithmetic if L has at least the standard rst-order logical apparatus (including identity), has a term '0' which denotes zero and function symbols for the successor, addition and multiplication functions defined over numbers - either built-in as primitives or introduced by definition - and has a predicate whose extension is the natural numbers." Is there any difference between having those symbols defined as primitives (through axioms) and introducing them by definitions? I guess there is a difference, since PA is incomplete and PA without X isn't (and mul. definition is the only difference). If definitions (even if innocent-looking and seemengly talk only about what's already in system) are so powerful, then shouldn't people be more careful, because of it, when defining stuff? I noticed Gödel makes some other (primitive recursive) definitions in his proof (for example, function that returns n-th prime number). Could it be, in theory, that some of these definitions added certain functionality to system P that wasn't there before in P, and that without this new functionality P would be too weak for Gödel's theorems to affect it?

Accepted:
August 25, 2011

Comments

It's true that multiplication can be defined in terms of addition, but the crucial question is: What logical resources are needed for that definition? The usual definition would be in terms of repeated addition, which means that the definition is (primitive) recursive. And now the point is that the theory we're discussing, which is sometimes known as "Pressburger arithmetic", doesn't have the resources needed for that sort of definition. So, in fact, this theory does not provide everything that's needed for defining multiplication, only some of it.

Gödel does use primitive recursion to define various functions in the course of his proof. Indeed, as the proof is often presented, the central lemma is that every primitive recursive function is "representable" in PA (or whatever theory we're discussing). The details are not essential here, except that the construction crucially depends upon the presence of both addition and multiplication. (Yes: If you drop addition, then the first incompleteness theorem again fails to apply!) The reason, in short, is that we need both for the proof of the so-called Beta Function Lemma, which tells us that we can code finite sequences, which is what we then use to effect recursion.

Actually, however, it has been known since Tarski, Mostowski, and Robinson's Decidable Theories (which, by the way, is now available as a Dover book and so quite cheaply) that what we need to know about arithmetic and multiplication is very, very little. All we actually need to know are all the true equalities, like "3 + 5 = 8" and "2 x 4 = 8", and inequalities, like "3 + 3 ≠ 5" and "3 ≠ 5", and all things like: x < 4 iff x = 0 or x = 1 or x = 2 or x = 3, and all things like: x < 5 or x = 5 or 5 < x. That's enough to allow the representation of all primitive recursive functions, and so any function that can tell us just that much about addition and multiplication will be subject to the first incompleteness theorem.

Here's a related question to which I do not know the answer, though I am sure it is known and suspect that the answer is "No": Can you define a pairing function in Presburger arithmetic? That is, a function p(m,n) with the property that (provably): p(m1,n1) = p(m2,n2) iff m1 = m2 and n1 = n2. One would also want projection functions, that is, functions p1(k) and p2(k) such that:

p1(k) = m iff, for some n, k = p(m,n)
p2(k) = n iff, for some m, k = p(m,n)

That's much less than having finite sequences, since pairs are just 2-term sequences, and, as I said, I suspect you can't even have that much. The usual pairing functions always use both addition and multiplication.

Regarding the question whether it matters if these things are defined or primitive, the answer there is "No", at least so far as these sorts of issues are concerned. This can be stated precisely, in terms of the notion of interpretation studied by Tarski, Mostowski, and Robinson. Concretely speaking, an alternative to having addition and multiplication as primitives would be to have some method within the theory for giving recursive definitions. Then you can just have successor and use recursion to define addition, multiplication, and the like. This is one way of formalizing the theory known as "primitive recursive arithmetic", which is subject to the first incompleteness theorem.