III.67 The Peano Axioms

Everyone knows what the natural numbers are: 0, 1, 2, 3, and so on. But how would we make that “and so on” precise? Can we look at the way that we reason about natural numbers and isolate a few basic principles, or axioms, whose consequences do complete justice to our intuitive picture of what the natural numbers should be? To put it another way, when we are proving something about the natural numbers, what assumptions do we need in order to get started?

To answer this question, let us strip things down to the bare minimum: we have an object called 0, and an operation s, called the successor function, which we think of intuitively as “adding 1.” In this pareddown language, we would like to say two things: that all the numbers 0, s(0), s(s(0)),. . . are distinct natural numbers, and that there are no others.

One simple way is to use the following two axioms. The first says that 0 is not a successor:

(i) For all x, s(x) ≠ 0.

The second says that distinct elements stay distinct when you take their successors:

(ii) For all x and y, if x ≠ y, then s(x) ≠ s(y).

Note that this implies, for example, that s(s(s(0))) ≠ s(0), for if they were equal, then, from rule (ii), we could deduce that s(s(0)) = 0, contradicting rule (i).

Now, how can we say that there are no other natural numbers? One would like to say that, for every x, either x = 0 or x = s(0) or x = s(s(0)) . . . , but that is an infinitely long statement, and those are definitely not allowed. After the failure of that very natural attempt, one might guess that there is no way to achieve the goal, but in fact there is a brilliant solution: induction. Here is an axiom that expresses the principle of induction.

(iii) Let A be any subset of the natural numbers with the following properties: 0 ∈ A, and s(x) ∈ A whenever x ∈ A. Then A must be the set of all natural numbers.

Note that this does express our intuitive idea that there are no “extra” natural numbers, since we can take A to be the set of all the numbers 0, s(0), s(s(0)),. . . that were on our list.

Rules (i), (ii), and (iii) are called the Peano axioms for the natural numbers. As explained above, they “characterize” the natural numbers, in the sense that all reasoning about the natural numbers may be reduced or rewritten in such a way that the only assumptions one needs are the Peano axioms.

There is a related system used in logic, called the first-order Peano axioms. The idea here is that we want to express the Peano axioms in the language of FIRST-ORDER LOGIC [IV.23 §1]. This means that we are allowed variables (that are interpreted as ranging over the natural numbers), as well as the symbols 0 and s, logical connectives, and the like, but nothing more: so there is no “member of” symbol, and no sets are allowed. (However, for technical reasons one does allow symbols for “plus” and “times.”)

To give an idea of what is allowed and what is not, consider the statements “there are infinitely many perfect squares” and “every infinite set of positive integers contains either infinitely many odd numbers or infinitely many even numbers.” With a little effort, we can express the first of these statements in first-order logic, as follows:

(∀m) (∃n) (∃x)   xx m + n.

In words, this says that for every m you can find a perfect square of the form m + n (which is how we express the fact that it is larger than m). However, in order to express the second statement, we find ourselves wanting to write (∀A), where A ranges over all possible subsets of the natural numbers, rather than all possible elements: this is the main thing that is not allowed in first-order logic.

By this criterion, rules (i) and (ii) are fine, but rule (iii) is not. Instead, we have to use an “axiom scheme,” which is an infinite set of axioms, one for each first-order statement p(x). So our version of rule (iii) is this: for each statement p(x), we have an axiom saying that if p(0) is true, and p(x) implies p(s(x)), then p(x) is true for all x.

Note that these axioms do not have the full strength of the usual Peano axioms. For instance, there are only countably many possible formulas p(x), whereas there are uncountably many sets A. It turns out that in fact there are “nonstandard” models of these axioms, meaning structures other than the natural numbers that satisfy the axioms of first-order Peano arithmetic.

Actually, one also allows parameters in the statements p(x); for example, p(x) could be the statement “there exists z with x = y+z,” which would correspond to the set of all natural numbers greater than or equal to y, and would therefore depend on y. And one also adds some axioms saying how plus and times behave (for example, commutativity of addition). This whole collection of axioms is known as Peano arithmetic, or PA for short.

See MODEL THEORY [IV.23] for more on some of the topics discussed in this article.