Why are addition and multiplication included in the signature of first-order Peano arithmetic?
In the second-order approach to Peano Arithmetic, the only non-logical symbols are the constant $0$ and the successor function $S(*).$ But, when we go to first-order Peano Arithmetic, something goes wrong with this approach, and we need to include addition and multiplication among our non-logical symbols, as well as a whole slew of axioms in this larger language.
What goes wrong?
For instance, I've read that we can define addition in second-order arithmetic by writing
- $x+0 = x$
- $x+S(y) = S(x+y).$
Why does this work in second order arithmetic, but not in first-order?
Solution 1:
There is a point of confusion in the question:
For instance, I've read that we can define addition in second-order arithmetic by writing
- $x+0 = x$
- $x+S(y) = S(x+y).$
Why does this work in second order arithmetic, but not in first-order?
That does not work in second-order arithmetic. It is an implicit characterization of the addition function, but it is not an explicit definition of the addition function in terms of the successor function.
A genuine definition is a formula $\phi(n,m,p)$ in a language without the addition symbol $+$ such that, for all natural numbers $n,m,p$, we have $n + m = p$ if and only if $\phi(n,m,p)$ holds. A "pseudo-definition" that is able to refer to the object being defined is called an implicit definition, but implicit definability is much weaker than actual definability.
One actual definition of addition of natural numbers in second-order arithmetic is: $$ n + m = p \Leftrightarrow (\forall f)\left[ \left( f(0) = n \land (\forall k)[f(S(k)) = S(f(k)]\right ) \to f(m) = p\right]. $$ Here $n,m,p$ are natural numbers, $(\forall k)$ quantifies over the natural numbers, and $(\forall f)$ quantifies over all unary functions from the natural numbers to themselves. Notice that, crucially, the right side does not mention $+$. In the particular definition, we could also rewrite it with an existential function quantifier: $$ n + m = p \Leftrightarrow (\exists f)\left( f(0) = n \land (\forall k)[f(S(k)) = S(f(k))] \land f(m) = p\right.) $$
Why does this definition not work in first-order logic? Because, in a single-sorted first-order theory of arithmetic, it is not possible to quantify over functions in the way that the definition does.
Now, that does not prove that it is impossible to define addition of natural numbers in terms of successor. It only shows that the definition in second-order arithmetic does not go through unchanged.
One way to see that addition is not definable from successor is sketched in this answer by Alex Kruckman. The key point is that if we look at the first-order theory of the natural numbers with successor and a constant for 0, every formula in this language (with some free variables) is equivalent to a quantifier-free formula in the language (with the same free variables). A proof of that is given by Richard Kaye here. So if addition was definable in that structure, it would be definable by a quantifier-free formula. But by analyzing the form of such a formula we can show that it cannot define addition.
Actually, more is known. Neither addition nor multiplication is definable from successor alone; multiplication is not definable from successor and addition; and addition is not definable from successor and multiplication. The theory of the natural numbers with multiplication and addition is undecidable, but the restriction to just addition is decidable, and the restriction with just multiplication is decidable.
Solution 2:
The reason is that it is impossible to define addition and multiplication using only successor operation in first-order logic.