9
$\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$
  • $\begingroup$ See web.mat.bham.ac.uk/R.W.Kaye/logic/succ $\endgroup$ – Carl Mummert Jul 22 '13 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 '13 at 2:10
  • $\begingroup$ @CarlMummert, thanks, I'll keep that in mind. $\endgroup$ – goblin Jul 22 '13 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 Jul 22 '13 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 '13 at 1:01
14
$\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; 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.

$\endgroup$
  • $\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 Jul 23 '13 at 1:05
  • $\begingroup$ @Asaf: this is really all a consequence of the fact that $\omega$ is the smallest (positive) limit ordinal, and as such has a very particular order structure that can be leveraged to make a model of PA in settings like second-order logic and ZFC. You can actually define a model of PA in any full second-order structure with an infinite domain and any language that includes equality. $\endgroup$ – Carl Mummert Jul 23 '13 at 1:09
  • 1
    $\begingroup$ +5 for @CarlMummert's original answer. Surely a model of clarity and helpfulness! $\endgroup$ – Peter Smith Jul 23 '13 at 9:45
  • 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 '14 at 19:35
  • 1
    $\begingroup$ @DanChristensen You‘re quantifying over sets which is no longer 1st order $\endgroup$ – S.N. Dec 6 '15 at 8:10
4
$\begingroup$

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

$\endgroup$
  • 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 '13 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 Jul 22 '13 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 '13 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 '13 at 0:31
  • $\begingroup$ @user18921 Please check Carl's answer. I don't think that I can add much. $\endgroup$ – Godot Jul 23 '13 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.