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

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

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

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

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

Checkpoint

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.

Checkpoint

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.

Checkpoint

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.

Checkpoint

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.

Checkpoint

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$.

Recursive definitions used below

Before proving arithmetic identities, we state the recursive definitions that make the calculations meaningful. 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

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

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.

Checkpoint

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

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.

Successor paths and the scope of induction

The induction axiom concerns every element of the chosen model, but its proof mechanism follows a particular path. Begin at $0$, apply $S$ once to reach $1$, apply it again to reach $2$, and continue. A proof of $P(0)$ establishes the claim at the first point of this path. The implication $P(x)\Longrightarrow P(S(x))$ then transports the claim one edge at a time. The conclusion is global because the induction axiom says there are no relevant elements left outside the path.

This explains both the strength and the limitation of an induction proof. A calculation at $0$, $1$, and $2$ is evidence about three points; it is not an induction step. Conversely, an induction step must be a statement for an arbitrary $x$, with no hidden assumption that $x$ is a small numeral. Writing the variable explicitly is a practical way to detect an argument that has quietly changed from a universal statement to a finite check.

There is also a useful distinction between the successor operation and the induction principle. The successor map tells us how to move from one natural number to the next. Induction tells us that a predicate stable under that move, and true at the start, reaches all natural numbers. A structure may have a successor-looking map while failing one of the axioms; the finite cycle above shows why checking the axioms matters before importing conclusions about counting.

A reliable induction checklist

Before accepting an induction proof, identify four pieces. First, state the domain: is $P(n)$ meant for every $n\in N$, or only for a subset? Second, write the base statement exactly, including any side conditions. Third, state the induction hypothesis with an arbitrary variable, rather than replacing it by a particular numerical case. Fourth, show the successor statement by permitted rewrites until it has the form $P(S(n))$.

This checklist catches several common errors. Proving $P(0)$ and $P(1)$ is not the induction step. Assuming $P(S(n))$ in order to prove $P(S(n))$ is circular. And proving the step only for one displayed value of $n$ does not establish a universal implication. When the recursive definition is oriented toward one input, the induction variable should normally be that input; a different choice can still work, but it needs an auxiliary identity that has already been proved.

The payoff is more than a formal certificate. The same proof shape will reappear when we define integers by pairs and rationals by pairs with a nonzero second coordinate. There the invariant is no longer simply “the predicate survives a successor”; it is “the result does not depend on the chosen representative.” The habit of naming the invariant and checking the exact rewrite is already being developed here.

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

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.