Why is it impossible to define multiplication in Presburger arithmetic?

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.


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

Tags:

Logic

Peano Axioms

Presburger Arithmetic

Related

The Gaussian and Mean Curvatures of a Parallel Surface Is a broken clock right twice a day? Can there be generalization of Monty Hall Problem? Show that curvature and torsion are $κ = \frac{\left|γ'∧γ''\right|}{\left|γ'\right|^3}$ and $\tau = \frac{(γ'∧γ'')\cdot γ'''}{\left|γ'∧γ''\right|^2}$ Prove that $(G, \circ)$ is a group if $a\circ x = b$ and $x\circ a = b$ have unique solutions Show that the set of all $n \times n$ orthogonal matrices, $O(n)$, is a compact subset of $\mbox{GL} (n,\mathbb R)$ The greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$. In general, in what kind of ring does this hold? Commutative property of ring addition Does the torus have a boundary? And about the concept of boundary. Solving $\sin \theta + \cos \theta=1$ in the interval $0^\circ\leq \theta\leq 360^\circ$ Combinatorial identity using combinatorial argument: $\left[\sum\limits_{k=0}^{n} \binom nk\right] ^ 2 = \sum\limits_{k=0}^{2n}\binom{2n}k$ Why can't you flatten a sphere?

Recent Posts