15
$\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$
    – Carl Mummert
    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$
    – Carl Mummert
    Jul 22, 2013 at 2:10
  • $\begingroup$ @CarlMummert, thanks, I'll keep that in mind. $\endgroup$
    – goblin GONE
    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$
    – goblin GONE
    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$
    – Carl Mummert
    Jul 23, 2013 at 1:01

3 Answers 3

Reset to default
20
$\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$ +5 for @CarlMummert's original answer. Surely a model of clarity and helpfulness! $\endgroup$
    – Peter Smith
    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$
    – Carl Mummert
    Jul 25, 2013 at 10:58
  • 1
    $\begingroup$ Sorry for digging out the old topic, but I have a question: can we do something similar in the language of second-order arithmetic which allows quantification over sets, and not functions? $\endgroup$
    – Wojowu
    Oct 23, 2014 at 19:35
  • 1
    $\begingroup$ @DanChristensen The above recursive formulation does indeed characterize addition, but its not a definition. In a true definition you can replace all occurrences of the function by the right hand side. Since you can't do that using the given characterization, you have to include those operators in the signature in order to use them and constrain them with axioms, and that is indeed what Peano does: (N,0,s,+,.,<). But the price you pay is that the theory of this structure is much richer than the theory of (N,0,s,<) (which has a decision procedure via Q.E.), and it turns out it is incomplete. $\endgroup$
    – Motorhead
    Dec 4, 2015 at 20:54
  • 1
    $\begingroup$ @DanChristensen You‘re quantifying over sets which is no longer 1st order $\endgroup$
    – Motorhead
    Dec 6, 2015 at 8:10
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$
    – Carl Mummert
    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$
    – goblin GONE
    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$
    – Doug Spoonwood
    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$
    – Carl Mummert
    Jul 23, 2013 at 0:31
  • $\begingroup$ @user18921 Please check Carl's answer. I don't think that I can add much. $\endgroup$
    – Godot
    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$
    – Arvid Samuelsson
    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 .