Can there exist a definition of 'multiplication' in Presburger Arithmetic? According to Wikipedia, Presberger Arithmetic is the first-order theory of the natural numbers with addition.  It can be proved to be consistent, complete, and decidable.
Though it contains no axioms per se regarding multiplication or division, it certainly has wffs of the following type:
$n_1$+$n_2$+...+$n_m$=b, where $n_1$=$n_2$=...=$n_m$ (i.e., n is added 'm times').
This, of course is just the elementary-school definition of 'multiplication'.  The elementary-school definition of 'division' can be (seemingly) defined from this also, by 'stipulation'.  The notions of 'divisibility' and 'prime number' can also be (seemingly) defined in Presburger Arithmetic by 'stipulation' just as they were defined in elementary school.
Since all one has (seemingly) done is stipulated a particular type of 'addition' as 'multiplication' (and defined the notions of 'division', 'divisibility', and 'prime number' from this stipulation) one seems still safely within the bounds of Presburger arithmetic, and Presburger Arithmetic with these stipulations is still consistent, complete, and decidable(?).
Question: How does Peano Arithmetic differ from Presburger Arithmetic with the aforementioned stipulated 'definitions'?  
 A: I'll give first a proof that multiplication can't be defined in Presburger arithmetic by characterizing exactly the sets definable in this theory; in order to do this, I'll assume as known, but won't prove the results from Presburger himself about quantifier elimination for this theory. In particular, I'll assume that every formula in Presburger arithmetic is equivalent to one of four basic forms, to be specified. I'll then close with some more general remarks about this undefinability phenomenon. Incidentally, if you want a proof of quantifier elimination for Presburger arithmetic, I suggest checking out an introductory logic textbook, such as Enderton's, Hinman's, or Monk's. Smoryński's Logical Number Theory I also contains a rather detailed account of Presburger arithmetic, including the quantifier elimination procedure (which is rather tricky) and the result I'm about to prove.
Let's start with a definition: a set $X$ of natural numbers is eventually periodic iff there exist some positive numbers $p$ and $n$ such that, for all $x > n$, $x \in X \iff x+p \in x$ ($p$ is usually called the period of $X$).

Claim: that every finite and co-finite set is eventually periodic.

Proof: Suppose $X$ is finite and let $n \in X$ be the greatest element of $X$. Then, for every $x > n$, $x \in X \iff x + 1 \in X$ (clearly), so $X$ is eventually periodic. Similarly, let $X$ be a co-finite set and let $X'$ be its complement. Since $X$ is co-finite, $X'$ is finite. Let $n \in X'$ be its greatest element. Then, for every $x > n$, $x \not \in X'$, whence $x \in X$. Thus, for this $n$, $x \in X \iff x+1 \in X$, so $X$ is eventually periodic.
Next, I'll show that every set definable in Presburger arithmetic is eventually periodic. The proof relies on the quantifier elimination procedure. Using this procedure, it's possible to show that every formula from Presburger arithmetic is equivalent to a Boolean combination of four basic types:
\begin{align}
n v_0  &= k\\
n v_0  &< k\\
k &< n v_0 \\
n v_0  &\equiv_m k
\end{align}
Where $n v_0$ denotes $v_0 + \dots + v_0$ $n$ many $v_0$'s, $n v_0 + m \equiv_s k$ has the usual interpretation, $k$ is a fixed numeral (obtained by repeated application of the successor function to $0$), and with the convention that $0 v_0$ denotes $0$.

Claim: these four basic types define eventually periodic sets.

Proof: In the cases in which $n = 0$, each formula above reduces to a sentence that is either true or false. In the former case, the sentence will then define $\omega$, whereas in the latter case the sentence will define $\varnothing$, both of which are eventually periodic sets. Consider thus $n \geq 1$.
In the first two cases, the formulas will define finite sets (in the first one, a singleton, in the latter, the sets of multiples of $n$ less than $k$), which, by the above, are always eventually periodic. In the third case, the formula will define a co-finite set, which again, by the above, is eventually periodic. 
For the final case, let $d$ be the greatest common divisor of $n$ and $m$. If $d$ doesn't divide $k$, then the formula is not satisfiable by any natural number, whence it defines $\varnothing$, which is eventually periodic. On the other hand, if $d$ dives $k$, then divide $m$, $n$, and $k$ to obtain $m_0 v_0 \equiv_{n_0} k_0$, with $m_0$, $n_0$, and $k_0$ relatively prime. Using basic facts from modular arithmetic, it follows that $m_0$ has a multiplicative inverse $m'$ modulo $n_0$ (because $m_0$ and $n_0$ are relatively prime), whence we also have that $m'm_0 v_0 \equiv_{n_0} m' k$, i.e. $v_0 \equiv_{n_0} m' k$ (you can check any basic text on modular arithmetic for this). But this obviously defines a periodic set, so an eventually periodic set. This ends the proof.
Since any definable set in Presburger arithmetic must be obtained from those four basic types above, it follows that all definable sets in Presburger arithmetic are eventually periodic. From this it follows easily that the multiplication function is not definable in Presburger arithmetic.

Claim: the multiplication relation $R_\times = \{\langle m, n, p\rangle \; | \; p = m \times n \in \omega \}$ is not definable in Presburger arithmetic.

Proof: The idea is simple. If we could define $R_\times$, we could use it to define (say) the set of squares. But the set of squares is not eventually periodic, so it's not definable in Presburger arithmetic. Therefore, $R_\times$ is not definable in Presburger arithmetic. 

Some comments: the above gives a rather abstract answer to your question, but it does not answer directly why the procedure outlined in your question won't work. In particular, for each $n$, we can define, for a fixed $m$, the operation $n \times m$ (just use the repeated addition trick). So why can't we somehow merge these definitions into a single one which would capture multiplication? The short answer is: for that, we would need to use recursion (in fact, primitive recursion), but Presburger arithmetic is not enough to capture to recursive functions. In particular, say that a theory $T$ captures a binary function $f$ iff for any $m$, $n$ and $p$, if $f(m, n) = p$, then there's a formula $\phi(x, y, z)$ in $T$ such that $T$ proves that $\forall y(\phi(m, n, y) \iff y = p)$ (where $m, n, p$ are constants with the obvious denotations). Although we may have infinitely many formulas that "approximate" multiplication, there's no single formula that will do this work inside Presburger arithmetic.
A: You're right that Presburger arithmetic can talk about (standard) individual instances of multiplication. Here's why that doesn't get you very far:


*

*There's no way to talk about nonstandard instances of multiplication. Suppose $(N, +)$ is a nonstandard model of Presburger arithmetic, with $c$ a nonstandard element. How would you define "$c\times c$"?

*There's no way to talk about variable multiplication. You move blithely from individual instances of multiplication to "is prime," but if you try to write down a first-order sentence defining primality, you'll run into problems. It gets even worse if you try to involve aternating quantifiers - how would you define something like "square-free"? "A product of seven square-free numbers?" Etc. Even schemes won't really help you here - what you need are infinitary formulas. And sure enough this will make Presburger arithmetic complicated - even "computable infinitary" Presburger arithmetic is extremely complicated. But that's a very different thing than first-order Presburger arithmetic.
