Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
1  
You could, but then it wouldn't be Presburger arithmetic any longer. – MJD Mar 31 '13 at 3:03
1  
@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
1  
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
3  
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
4  
Presburger arithmetic is decidable, but with multiplication, hence Peano, one gets an undecidable theory. – coffeemath Apr 2 '13 at 4:50
up vote 7 down vote accepted

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.

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

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

share|cite|improve this answer

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.