Why is it impossible to define multiplication in Presburger arithmetic?

Solution 1:

There is difference between definition by recursion and arithmetical definition (or explicit definition). An $n$-ary operation $F$ is arithmetically defined iff there is a formula $\varphi(x_1,\ldots,x_n,y)$ with $x_1,\ldots,x_n,y$ free, not containing any other symbols than primitive and previously defined and such that the equivalence: \[ F(x_1,\ldots,x_n)=y\longleftrightarrow\varphi(x_1,\ldots,x_n,y) \] holds (in this case the equivalence in question is to hold in the standard model of arithmetic). As MJD wrote in the comment above, you can add recursive characterization of multiplication to Presburger Arithmetic but the resulting system is no longer Presburger Arithmetic. And you cannot arithmetically define multiplication from other primitives in Presburger arithmetic.

EDIT: Corrected some minor and stylistic errors.

Solution 2:

Peano arithmetic doesn't actually define multiplication. The existence of multiplication is an axiom in the Peano system. The recursive definition of multiplication you provide in the question cannot prove the existence of multiplication function for all numbers (even though it can for any finite value of $n$ and $m$). There are two ways around it:

1. Use the recursive definition that you provide, and assume that a function with these properties exists (i.e. existence of multiplication is an axiom).
2. Add the Recursion Theorem as an axiom and use that prove the existence of multiplication.

Neither of these axioms exist in Presburger arithmetic and so it is not possible to define multiplication in Presburger arithmetic without extending it.

Note: The reason the Recursion Theorem is called a theorem and not an axiom is because it can be proved in ZF set theory. But if your only axioms are the Peano axioms, it can't be proved and needs to be it's own axiom.

A good explanation of the intricacies of defining multiplication in Peano arithmetic can be found in this blog: How multiplication is really defined in Peano arithmetic

Solution 3:

When people nowadays say ‘arithmetic’, rather than subject matter they are usually referring to an interpreted Formal System ( https://en.wikipedia.org/wiki/Formal_system) which includes a set of axioms (e.g., arithmetic axioms), a deductive apparatus (usually only modus ponens) and a particular language (usually First-order logic).

There are two aspects to defining functions, semantic and syntactic, the abstract mapping and its representations; the factorial function is a good example. In a Formal System setting, ‘definition’ means formal definition, a substitution of usually one symbol, the definiendum, for a set of others, the definiens, which without the necessary alphabet (a symbol for the definiendum) cannot be done.

On the other hand, anyone who has read Godel’s Incompleteness paper will have the same question as FUZxxl. Godel’s signature contains function alphabets for the successor and zero only, s and 0—fewer than those in Presburger Arithmetic, though he presumes use of equality, addition, multiplication, and other functions. This is because also included in Godel’s signature are higher order variables, ϕ1, ϕ2, ϕ3, … that allow for a formal definition of equality:

(a = b) ≡ ∀ϕ1[ϕ1(a) ⇔ ϕ1(b)]

(13.01, Principia Mathematica, page 176), as well as addition and multiplication:

(a+b = c) ≡ ∀ϕ1[∀x ∀y ( ϕ1(x,0) = x ∩ ϕ1(x,sy) = sϕ1(x,y)) ⇒ ϕ1(a,b) = c ]

(a⋅b = c) ≡ ∀ϕ1[∀x ∀y ( ϕ1(x,0) = 0 ∩ ϕ1(x,y) + x = ϕ1(x,sy)) ⇒ ϕ1(a,b) = c ]

(Foundations without Foundationalism, page 120). Godel could well have avoided this complication (as expositions of Godel Incompleteness commonly do—without explanation!) by simply including the needed symbols in his signature, but might have wanted to remain more faithful to Logicist austerity that wherever possible eliminates nonlogical symbols {+, ⋅ , =, etc.} in favor of logical ones {∩,∪, ∀, etc.}.

Presburger Arithmetic is defined to be the first-order Formal System of natural numbers, with non-logical alphabets { 0, +, =}; no higher-order variables. The line from Wikipedia’s Peano Axioms (https://en.wikipedia.org/wiki/Peano_axioms)

A weaker first-order system called Peano arithmetic is obtained by explicitly adding
the addition and multiplication operation symbols and replacing the second-order
induction axiom with a first-order axiom schema.

misses the broader point that “Arithmetic” in “Peano Arithmetic” does not signify arithmetic, commonly understood, but refers to the order of the language in which the Peano axioms and their deductions are cast, an unhelpful misnomer.