18
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ See web.mat.bham.ac.uk/R.W.Kaye/logic/succ $\endgroup$ Commented Jul 22, 2013 at 2:05
  • $\begingroup$ I added the tag "logic" which is likely to have many more followers. I think it's a good idea in general to tag most logic questions with that tag and additional more-specific tags $\endgroup$ Commented Jul 22, 2013 at 2:10
  • $\begingroup$ @CarlMummert, thanks, I'll keep that in mind. $\endgroup$ Commented Jul 22, 2013 at 2:14
  • $\begingroup$ @CarlMummert, I've read over that link a few times, but I'm not quite sure of the significance. Are you saying that, 'okay, we COULD leave $+$ and $\times$ out of our non-logical symbols, but this would make quantifier elimination harder to prove'? $\endgroup$ Commented Jul 22, 2013 at 14:59
  • 3
    $\begingroup$ Peano arithmetic does not have quantifier elimination. Quantifier elimination, like decidability, is a sign that a foundational theory is not very strong. $\endgroup$ Commented Jul 23, 2013 at 1:01

3 Answers 3

22
$\begingroup$

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; but addition is definable over $\mathbb{N}$ 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. The reference A Survey of Arithmetical Definability by Bés was mentioned in the comments, with much more detailed results.

$\endgroup$
25
  • 1
    $\begingroup$ Hm. Interesting. Since successorship is definable from the order (on $\Bbb N$, that is), we can define $0,S,+,\cdot$ and show that the axioms of $\sf PA_2$ hold, just in the second-order structure $\langle\Bbb N,\leq\rangle$. That's very nice. (And now that I've written that, it makes a lot of sense because we actually define all those in the language of set theory where we only have $\in$ which functions as the surrogate for $<$...) $\endgroup$
    – Asaf Karagila
    Commented Jul 23, 2013 at 1:05
  • 1
    $\begingroup$ +5 for @CarlMummert's original answer. Surely a model of clarity and helpfulness! $\endgroup$ Commented Jul 23, 2013 at 9:45
  • 1
    $\begingroup$ @Dan Christensen: the issue is that neither ZFC nor second-order arithmetic has any syntax that literally makes the two recursion equations into a "definition". It is true that for well-posed recursive definitions there are techniques for converting the recursion equations into an actual definition; I indicate one in the answer. But the question claimed that we can define addition simply "by writing" the equations, when there is actually much more going on. It is easy to write a system of recursion equations that doesn't define any function. $\endgroup$ Commented Jul 25, 2013 at 10:58
  • 2
    $\begingroup$ @DanChristensen: Certainly. But the title of this post is "Why are addition and multiplication included in the signature of first-order Peano arithmetic?". If you're interested in 2nd order, Carl Mummert explains how to define + in SOL. $\endgroup$
    – Motorhead
    Commented Dec 7, 2015 at 19:07
  • 2
    $\begingroup$ I just stumbled on this old answer and wanted to make a quick correction. In the last paragraph, you say "addition is not definable from successor and multiplication". Actually, $a+b=c$ is definable by $S(a\cdot c)\cdot S(b\cdot c) = S(c\cdot c \cdot S(a\cdot b))$ (this works when $c\neq 0$, and we can handle the case $c = 0$ separately). This clever definition is due to Julia Robinson from her paper "Decidability and decision problems in arithmetic". $\endgroup$ Commented Nov 23, 2020 at 22:28
3
$\begingroup$

The reason is that it is impossible to define addition and multiplication using only successor operation in first-order logic.

$\endgroup$
7
  • 1
    $\begingroup$ For example, if we weaken Peano arithmetic by removing the multiplication sign and any axiom that mentioned it, we obtain Presberger arithmetic, which is known to be a much weaker theory than Peano arithmetic. If multiplication was definable in Presberger arithmetic, that could not be the case. $\endgroup$ Commented Jul 22, 2013 at 1:58
  • $\begingroup$ @Godot, why does the definition $x+0 = x$, $x+S(y)=S(x+y)$ suffice for defining addition in second-order arithmetic, but not in first order? $\endgroup$ Commented Jul 22, 2013 at 15:00
  • $\begingroup$ @CarlMummert Weaker in what sense? Presberger arithmetic is decideable, but Peano arithmetic isn't. Doesn't deciability count for anything in terms of strength? $\endgroup$ Commented Jul 23, 2013 at 0:18
  • $\begingroup$ @Doug Spoonwood: any sufficiently strong foundational theory is undecidable, and in fact essentially undecidable. Decidability of a theory is evidence that they theory is not very strong at all. $\endgroup$ Commented Jul 23, 2013 at 0:31
  • $\begingroup$ @user18921 Please check Carl's answer. I don't think that I can add much. $\endgroup$
    – Godot
    Commented Jul 23, 2013 at 12:30
-1
$\begingroup$

In a 2nd-order approach to PA, using the axioms of set theory, it is possible to construct the usual addition and multiplication (and exponentiation) functions starting with only a $0$ (or $1$) and a successor function.

In a 1st-order approach, since set theory is not available, you will need extra axioms for the addition and multiplication (and exponentiation) functions.

$\endgroup$
1
  • $\begingroup$ I downvoted this for the same reason I downvoted Godot's answer, but now I'm not sure your deserve a downvote. $\endgroup$ Commented May 8, 2022 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .