3.1 Natural numbers and Peano's axioms

At first sight, the natural numbers seem too familiar to need a definition. We count with them from childhood, and it is tempting to think that the list

$$0, 1, 2, 3, \ldots$$

already says everything important.

A rigorous treatment asks what structure actually makes the natural numbers behave the way they do. The answer is not the shape of the symbols, but the presence of a distinguished starting point, a successor operation, and an induction principle.

Why a formal definition is needed

If we describe the natural numbers only by writing $0, 1, 2, 3, \ldots$, then we have not really explained what the dots mean, why the process continues, or why induction works.

The Peano viewpoint solves that problem by specifying the essential properties directly. It tells us what must be true in any model of the natural numbers, without depending on intuition alone.

The data of a model

Definition 3.1.1

(A model of the natural numbers)

Suppose $N$ is a set equipped with:

• a distinguished element $0 \in N$;
• a function $S : N \to N$, called the successor map.

The triple $(N, 0, S)$ is called a model of the natural numbers if it satisfies the Peano axioms:

1. $S$ is injective: if $S(x) = S(y)$, then $x = y$.
2. No element is its own successor: $S(x) \ne x$ for every $x \in N$.
3. Zero is not a successor: there is no $x \in N$ with $S(x) = 0$.
4. Induction holds: if a predicate $P$ is true of $0$, and whenever $P(x)$ is true it follows that $P(S(x))$ is true, then $P$ is true for every $x \in N$.

The central idea is that the natural numbers are characterized by how they are connected, not by how they are written.

What each axiom is doing

Each axiom rules out a specific kind of pathology.

• Injectivity says different numbers cannot suddenly merge after one successor step.
• $S(x) \ne x$ rules out fixed points.
• $S(x) \ne 0$ says zero is the starting point, not something reached later.
• Induction rules out disconnected extra pieces and ensures that every element lies in the chain generated from $0$.

Taken together, these axioms force the familiar picture of counting forward one step at a time.

Reading numbers through successor

Worked example 3.1.2

(How the usual numerals arise from $0$ and $S$)

Once $0$ and the successor map are fixed, the next numbers are interpreted as

$$1 = S(0), \qquad 2 = S(S(0)), \qquad 3 = S(S(S(0))),$$

and so on.

So the notation $2$ is shorthand for "the element obtained by applying the successor map twice to $0$." The notation is convenient, but the structure comes first.

This is why successor notation remains useful when we want the definition to remain visible instead of being hidden behind familiar symbols.

Induction is not an extra trick

Students often meet induction as a proof technique after they already believe the natural numbers are understood. A construction-first perspective reverses that order.

The induction principle is part of the definition of what the natural numbers are. In that sense, induction is not merely a useful method for proving statements about $N$; it is one of the structural facts that makes $N$ the natural numbers in the first place.

Theorem 3.1.3

(What induction gives you)

To prove a statement $P(n)$ for all $n \in N$, it is enough to show:

1. $P(0)$ is true.
2. For every $x \in N$, if $P(x)$ is true, then $P(S(x))$ is true.

Once these two facts are established, induction implies that $P(n)$ holds for every natural number $n$.

A model that fails

Worked example 3.1.4

(Why a finite cycle is not a model of the natural numbers)

Consider the set $\{0,1,2\}$ with successor map

$$S(0)=1, \qquad S(1)=2, \qquad S(2)=0.$$

This structure does not satisfy the Peano axioms.

First, $0$ is a successor because $S(2)=0$, so axiom 3 fails. This is already enough to reject the structure as a model of the natural numbers. The example should not be read as an induction-axiom failure: from $0$, repeated successors still visit the whole finite set. The problem is that the successor map loops back and makes $0$ a successor.

So although the symbols look familiar, this structure is not a model of the natural numbers.

This example is important because it shows why the Peano axioms are not ornamental. They exclude structures that resemble counting in superficial ways but do not behave like $N$.

Common mistakes

Common mistake

(Do not confuse the symbol with the structural role)

The Peano viewpoint does not say that the written mark $2$ has some built-in meaning. It says that the object denoted by $2$ is the second successor of $0$.

Common mistake

(Induction is not optional decoration)

Without the induction axiom, a structure can contain a familiar successor chain starting from $0$ and still have extra disconnected elements or loops. The induction principle rules those out.

Quick checks

Quick check

(Why does the axiom $S(x) \ne 0$ matter?)

Explain what would go wrong if $0$ were allowed to be a successor.

Solution · Answer

If $0$ were a successor, then the counting chain could loop back on itself instead of having a genuine starting point. The structure would no longer match the one-way progression we expect from the natural numbers.

Quick check

(What does injectivity of the successor map prevent?)

Answer in terms of two different numbers trying to behave like the same next number.

Solution · Answer

It prevents two different elements from having the same successor. Without injectivity, distinct numbers could collapse into a single next step, which would destroy the usual linear counting structure.

Quick check

(After proving a base case and an induction step, what exactly may you conclude?)

State the conclusion carefully.

Solution · Answer

You may conclude that the predicate holds for every element of $N$, not merely for the first few examples that you checked by hand.

Two ways a successor structure can fail

The four Peano axioms must be checked separately: (1) successor injectivity, (2) $S(x)\ne x$, (3) no successor equals $0$, and (4) induction.

Quick check

(Let $N=\{0,1,2\}$ with $S(0)=1$, $S(1)=2$, and $S(2)=1$. Which of the four Peano axioms fail?)

Check injectivity, fixed points, the image of $S$, and every subset containing $0$ that is closed under $S$.

Solution

Axiom (1) fails because $S(0)=S(2)=1$ while $0\ne2$. Axiom (2) holds: $1\ne0$, $2\ne1$, and $1\ne2$. Axiom (3) holds because the image of $S$ is $\{1,2\}$, which does not contain $0$. Axiom (4) also holds: any subset containing $0$ and closed under $S$ must contain $1=S(0)$, then $2=S(1)$, and hence all of $N$; the cycle returns to elements already present.

Quick check

(Let $M=\mathbb N\sqcup\{a,b,c\}$ with $S(n)=n+1$ on $\mathbb N$ and $S(a)=b$, $S(b)=c$, $S(c)=a$. Which of the four Peano axioms fail?)

Check the three cycle elements as well as the natural-number chain.

Solution

Axiom (1) holds: the natural-number successor is injective, and the three-cycle has distinct images disjoint from the natural-number images. Axiom (2) holds because the natural chain moves forward and the cycle has length three, so no element is fixed. Axiom (3) holds because no successor is $0$. Axiom (4) fails: $\mathbb N$ is a proper subset of $M$, contains $0$, and is closed under $S$, but it omits $a,b,c$.

Arithmetic from successor

Successor supplies one step. Addition and multiplication encode repeated steps through recursive rules. For $a,b\in N$, define

$$a+0=a,\qquad a+S(b)=S(a+b),$$

and

$$a\cdot0=0,\qquad a\cdot S(b)=a\cdot b+a.$$

The successor occurs in the second input, so later inductions must respect this orientation unless a left-hand lemma has already been proved.

Addition computes $2+3$ by reducing the second input to $2+2$, then $2+1$, then $2+0$, before rebuilding the successors. Multiplication reduces $2\cdot 3$ to $2\cdot 2+2$, and eventually to repeated addition. Each recursive call uses a predecessor of the second input, so the process terminates at zero. These rules calculate values; commutativity still requires proof.

The first recursive identity

The recursive definition of addition is written with the successor on the second input. To use it in other positions, we prove a separate identity rather than silently treating addition as commutative before commutativity has been established.

Theorem 3.1.5

(Successor on the left can be moved through addition)

For every $a,b\in N$,

$$S(a)+b=S(a+b).$$

Induction proof of $S(a)+b=S(a+b)$

Fix $a$ and let $P(b)$ be the statement $S(a)+b=S(a+b)$.

Base case. When $b=0$, the defining equation for addition gives

$$S(a)+0=S(a).$$

The right side is also

$$S(a+0)=S(a),$$

so $P(0)$ holds.

Induction step. Assume $P(b)$, so $S(a)+b=S(a+b)$. Then

$$\begin{aligned} S(a)+S(b) &=S(S(a)+b) &&\text{by the recursive rule,}\\ &=S(S(a+b)) &&\text{by the induction hypothesis,}\\ &=S(a+S(b)) &&\text{by the recursive rule for }a+S(b). \end{aligned}$$

Thus $P(b)$ implies $P(S(b))$. The induction principle gives the identity for every $b\in N$.

The proof illustrates a useful discipline: the induction hypothesis is used only after the expression has been rewritten into exactly the shape it recognizes. It is not a licence to replace arbitrary expressions by their successors.

Worked example 3.1.6

(Proving $0+n=n$ instead of assuming it)

The defining equation gives $0+0=0$, which is the base case. Suppose $0+n=n$. Then

$$0+S(n)=S(0+n)=S(n).$$

Therefore induction proves $0+n=n$ for every natural number $n$. This is the identity used later when a recursive calculation reaches a zero on the left.

Common mistake

(The induction hypothesis has a fixed input)

In the proof above, the induction hypothesis is $S(a)+b=S(a+b)$ for the current $b$. It does not say that the claim is already true with $S(b)$ in place of $b$; that is precisely what the induction step must establish.

Quick check

(Why does the proof of $S(a)+b=S(a+b)$ induct on $b$ rather than $a$?)

Connect the choice of induction variable to the recursive definition.

Solution · Answer

The recursive definition reduces the second input: $a+S(b)$ is rewritten in terms of $a+b$. Inducting on $b$ follows the direction in which the definition provides information. An induction on $a$ would require a different lemma before the recursive rule could be applied.

Theorem 3.1.7

(Every nonzero natural number has a unique predecessor)

For every $x\in N$, if $x\ne0$, then there is a unique $y\in N$ such that $S(y)=x$.

Why the predecessor statement follows from Peano induction

Let $P(x)$ say: either $x=0$, or there is a unique $y$ with $S(y)=x$. The base case is immediate because the first alternative holds for $0$. For the step, assume the statement for $x$. The successor $S(x)$ is itself the successor of $x$, so existence is immediate. If $S(y)=S(x)$, injectivity gives $y=x$, which proves uniqueness. Thus the successor structure supplies exactly one previous element for each nonzero natural number.

The scope of an induction proof

The successor map supplies the step; induction says that a property true at zero and preserved by that step holds throughout the model. A proof must therefore state its domain and base case, assume $P(n)$ for an arbitrary fixed $n$, and derive $P(S(n))$ using permitted identities. Checking several numerals, assuming the successor case itself, or proving the step only at one chosen input cannot establish the universal conclusion.

The recursive rule normally determines the useful induction variable. A different choice may work, but requires an appropriate identity already proved. This discipline also matters in the coming quotient constructions: there the property to preserve is independence from a chosen representative. In both settings, naming the property makes clear what each calculation must establish.

Optional model: von Neumann natural numbers

The Peano axioms describe what the natural numbers must do, but they do not force us to use any particular internal representation. One standard set-theoretic model is the von Neumann construction:

$$0:=\varnothing,\qquad 1:=\{0\},\qquad 2:=\{0,1\},\qquad 3:=\{0,1,2\}.$$

In general,

$$S(n)=n\cup\{n\}.$$

So each natural number is the set of all earlier natural numbers. In this model, membership mirrors order: $m\in n$ exactly when $m$ is less than $n$.

Worked example 3.1.8

(Why $2$ becomes $\{0,1\}$)

Starting with $0=\varnothing$, the successor rule gives

$$1=S(0)=0\cup\{0\}=\{0\},$$

and then

$$2=S(1)=1\cup\{1\}=\{0,1\}.$$

This does not mean the everyday numeral $2$ has changed its meaning. It means we have built a concrete set-theoretic representative that satisfies the same successor pattern.

Previous and next steps

This note sits at the start of the construction chapter. It connects forward to 3.2 Induction and recursive arithmetic and uses language prepared earlier in 2.2 Functions and relations.