# Why is it impossible to define multiplication in Presburger arithmetic?

Peano arithmetic defines multiplication recursivly as:

$$\begin{gather}a\cdot0=a\\a\cdot S(b)=a+(a\cdot b)\end{gather}$$

Why is this not possible in Presburger arithmetic?

-
You could, but then it wouldn't be Presburger arithmetic any longer. –  MJD Mar 31 '13 at 3:03
@MJD Presburger arithmetic is an axiomatic system. People claim that it is impossible to define multiplication within this system. Why? –  FUZxxl Mar 31 '13 at 3:07
Because it only has axioms for addition and induction. If you add axioms for multiplication, as you did above, then you're working in Peano arithmetic, not Presburger arithmetic. –  MJD Mar 31 '13 at 3:09
It is a consequence of induction in Peano arithmetic. There is something nontrivial going on in the recursion theorem! –  Zhen Lin Mar 31 '13 at 8:25
Presburger arithmetic is decidable, but with multiplication, hence Peano, one gets an undecidable theory. –  coffeemath Apr 2 '13 at 4:50

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.

-
Ah, I see. Thank you for this answer. –  FUZxxl Apr 2 '13 at 10:51

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.

-
Welcome to MSE! It really helps readability to format questions using MathJax (see FAQ). Regards –  Amzoti Jun 3 '13 at 0:49