3.2 Induction and recursive arithmetic

The recursive rules calculate addition and multiplication, but commutativity and distributivity do not appear in those rules. The order of proof matters: first establish identities for addition, then use them in multiplication proofs, and only then use cancellation to construct larger number systems.

Why the recursive rules define unique functions

Induction proves identities about a function after it exists. A recursion theorem supplies existence as well as uniqueness. The set-theoretic background here permits subsets, power sets and intersections; on $N$ we use successor injectivity, zero not being a successor, and induction.

Theorem 3.2.1

(Recursion theorem for the natural numbers)

Let $A$ be a set, choose $a_0\in A$, and let $T:A\to A$ be a function. There is a unique function $h:N\to A$ such that $h(0)=a_0$ and $h(S(n))=T(h(n))$ for every $n\in N$. No injectivity or surjectivity of $T$ is required.

Proof

(Existence from the smallest closed relation)

Consider all relations $R\subseteq N\times A$ containing $(0,a_0)$ and closed under $(n,a)\mapsto(S(n),T(a))$. This family is nonempty because it contains $N\times A$. Its intersection $R_*$ is again such a relation and is contained in every such relation. Induction proves that every $n$ occurs as a first coordinate: zero occurs, and any pair at $n$ produces a pair at $S(n)$.

We prove by induction that its second coordinate is unique. At zero, delete every pair $(0,a)$ with $a\ne a_0$. The remaining relation still contains the base pair and is closed, because a successor never equals zero. Minimality of $R_*$ forces this deletion to remove nothing.

Now assume there is exactly one pair $(n,a)$ at $n$. Closure supplies $(S(n),T(a))$. Delete all pairs at $S(n)$ whose second coordinate differs from $T(a)$. The base pair remains, since $S(n)\ne0$. Closure remains: a successor pair can enter this one affected fiber only from first coordinate $n$, by successor injectivity, and that coordinate has only the second coordinate $a$. Its required image is precisely the retained pair. Again minimality says nothing was removed. This proves uniqueness at $S(n)$. Thus $R_*$ is the graph of a total function $h$ with the required recursion.

If $h_1,h_2$ both satisfy the rule, they agree at zero. Agreement at $n$ implies agreement at $S(n)$ by applying the same function $T$. Induction gives $h_1=h_2$, completing uniqueness.

For each fixed $a\in N$, take $A=N$, $a_0=a$ and $T=S$. The resulting function of $b$ is $a+b$. After addition exists, use $a_0=0$ and $T(x)=x+a$ to define $a\cdot b$. The theorem therefore justifies both definitions without assuming their later algebraic laws. The proofs below then establish those laws in dependency order.

Recursive addition

Definition 3.2.2

(Recursive definition of addition)

For natural numbers $a$ and $b$, addition is defined by:

• $a + 0 = a$
• $a + S(b) = S(a + b)$

This is a recursive definition. You know the result when the second input is $0$, and every later value is built from an earlier one.

Worked example 3.2.3

(Compute $2 + 3$ from the definition)

Write $2 = S(S(0))$ and $3 = S(S(S(0)))$.

Then:

$2 + 3 = 2 + S(S(S(0)))$

$= S(2 + S(S(0)))$

$= S(S(2 + S(0)))$

$= S(S(S(2 + 0)))$

$= S(S(S(2)))$.

That is the number usually called $5$.

Common mistake

(A recursive formula is not yet a proof)

The formulas tell you how the operation is defined. They do not automatically prove a claim about all natural numbers. For that, you still need induction.

Recursive multiplication

Multiplication is introduced in the same recursive style. Once addition is available, multiplication can be read as repeated addition controlled by the second input.

Definition 3.2.4

(Recursive definition of multiplication)

For natural numbers $a$ and $b$, multiplication is defined by:

• $a \cdot 0 = 0$
• $a \cdot S(b) = (a \cdot b) + a$

The base case says that adding $a$ zero times gives $0$. The step says that if you already know $a \cdot b$, then multiplying by the successor $S(b)$ adds one more copy of $a$.

Worked example 3.2.5

(Compute $3 \cdot 2$ from the definition)

Write $2 = S(S(0))$. Then

$$3\cdot 2 =3\cdot S(S(0)) =(3\cdot S(0))+3$$

and

$$3\cdot S(0)=(3\cdot 0)+3=0+3=3.$$

Therefore

$$3\cdot 2=3+3=6.$$

The familiar interpretation “three, taken two times” is recovered from the recursive rule.

What induction proves

The induction principle is the reason recursive definitions can support ordinary algebraic laws. A typical proof has the following shape.

Theorem 3.2.6

(Induction principle)

Let $P(n)$ be a statement about a natural number $n$. If:

1. $P(0)$ is true, and
2. whenever $P(n)$ is true, $P(S(n))$ is also true,

then $P(n)$ is true for every $n\in N$.

The base case attaches the statement to the starting point $0$. The induction step proves that truth is preserved when we move one successor forward. The two parts together rule out the possibility that the statement holds at first but then fails later.

Follow an induction argument

An induction proof separates the initial case from the deduction at an arbitrary input. Keeping those roles distinct makes the use of the hypothesis visible.

The successor identity in arithmetic proofs

The left-successor identity from 3.1 Natural numbers and Peano axioms allows a later proof to move a successor through the first input. The identity follows from the recursive rule without assuming commutativity.

Proof: $S(a) + b = S(a + b)$ by induction on $b$

Fix $a$ and prove the statement for every $b\in N$.

Base case: when $b = 0$,

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

Induction step: assume $S(a) + b = S(a + b)$. Then

$S(a) + S(b) = S(S(a) + b)$ by the recursive rule,

$= S(S(a + b))$ by the induction hypothesis,

$= S(a + S(b))$ by the recursive rule again.

So the statement holds for $S(b)$ whenever it holds for $b$.

Why $a \cdot S(b) = a \cdot b + a$ is a definition

For multiplication, the formula

$$a\cdot S(b)=(a\cdot b)+a$$

is not something proved after multiplication is already known. It is the recursive step that defines multiplication. Later algebraic laws, such as distributivity, are the statements that require induction.

Algebraic laws come after the definitions

Once addition and multiplication have been defined recursively, the familiar laws of arithmetic become theorems.

Theorem 3.2.7

(Examples of arithmetic laws proved by induction)

For natural numbers $a$, $b$, and $c$, one proves:

$$a+b=b+a,$$$$a\cdot(b+c)=a\cdot b+a\cdot c,$$

and

$$a\cdot b=b\cdot a.$$

The important point is the order of logic: we first define the operations, then prove that they behave like the operations we already know.

Proof: associativity of addition

Fix $a$ and $b$, and induct on $c$ for

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

When $c=0$, both sides equal $a+b$ by $b+0=b$ and the defining rule. If the identity holds for $c$, then

$$\begin{aligned} (a+b)+S(c)&=S((a+b)+c)\\ &=S(a+(b+c))\\ &=a+S(b+c)\\ &=a+(b+S(c)). \end{aligned}$$

The second line is the induction hypothesis and the first and last rewrites use the recursive addition rule. Thus addition is associative before it is used to rearrange terms in later proofs.

Proof: $0 \cdot a = 0$

Induct on $a$. The base case is the defining equation $0\cdot 0=0$. If $0\cdot a=0$, then

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

Hence $0\cdot a=0$ for every natural number $a$.

From a recursive rule to a proof

There are two related but different uses of the successor pattern. A recursive definition tells us how to calculate a new value from an earlier value. An induction proof tells us how to establish a statement for every natural input. The calculation can suggest a theorem, but it does not replace the proof.

Worked example 3.2.8

(Compute $2 \cdot 3$ one successor at a time)

Using $3=S(S(S(0)))$ and the multiplication rule,

$$\begin{aligned} 2\cdot3 &=2\cdot S(S(S(0)))\\ &=(2\cdot S(S(0)))+2\\ &=((2\cdot S(0))+2)+2\\ &=(((2\cdot0)+2)+2)+2\\ &=((0+2)+2)+2\\ &=2+2+2=6. \end{aligned}$$

Each line reduces the second input until the base case $2\cdot0=0$ is reached. Only then do we simplify the resulting additions.

The left-zero identity needed for commutativity

Define $P(n)$ to be the statement $0+n=n$.

For the base case, the recursive addition rule gives $0+0=0$.

For the step, assume $P(n)$, so $0+n=n$. Then

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

The first equality is the recursive definition, and the second uses the induction hypothesis. Therefore $P(S(n))$ follows from $P(n)$. Induction concludes that $0+n=n$ for every $n\in N$.

This proof is small, but it supplies a fact needed by later algebra. It also shows why the induction hypothesis should be written explicitly instead of replaced by an informal phrase such as “the pattern continues.”

Theorem 3.2.9

(Addition is commutative after the induction lemmas)

For all $a,b\in N$, $a+b=b+a$.

Proof of commutativity of addition

Fix $a$ and induct on $b$.

When $b=0$,

$$a+0=a=0+a,$$

where the first equality is the definition and the second is the lemma $0+a=a$.

Now assume $a+b=b+a$. Then

$$\begin{aligned} a+S(b)&=S(a+b)\\ &=S(b+a)\\ &=S(b)+a. \end{aligned}$$

The middle equality is the induction hypothesis, and the last equality is the successor-on-the-left identity. Thus the claim holds for $S(b)$, completing the induction. The proof is a model for later algebra: first prove the identities forced by the recursive orientation, then use them to establish familiar symmetric laws.

Proof: cancellation in $N$

We prove the left-cancellation law

$$a+b=a+c\quad\Longrightarrow\quad b=c$$

by induction on $a$. When $a=0$, the identity $0+b=0+c$ reduces to $b=c$ by $0+n=n$. For the step, suppose the result is known for $a$, and assume $S(a)+b=S(a)+c$. The successor-on-the-left lemma and injectivity of $S$ give $a+b=a+c$; the induction hypothesis then gives $b=c$. This cancellation theorem is the natural-number fact used to prove transitivity in 3.3 Integers from equivalence classes.

Common mistake

(A calculation of several cases is not induction)

Computing $2+0$, $2+1$, and $2+2$ checks only three inputs. An induction proof must name an arbitrary $n$, prove the base case, and show how the statement passes from $n$ to $S(n)$.

Quick check

(What is the difference between a recursive definition and an induction hypothesis?)

Mention what each one is allowed to do.

Solution · Answer

A recursive definition gives the value of an operation by reducing an input to a base case. An induction hypothesis is a temporary assumption that a particular statement holds at an arbitrary $n$, used to prove the statement at $S(n)$.

A full induction proof of distributivity

Fix $a$ and $b$, and let

$$P(c):\quad a\cdot(b+c)=a\cdot b+a\cdot c.$$

For $c=0$,

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

Assume $P(c)$. Since $b+S(c)=S(b+c)$, the recursive multiplication rule and the induction hypothesis give

$$\begin{aligned} a\cdot(b+S(c)) &=a\cdot S(b+c)\\ &=a\cdot(b+c)+a\\ &=(a\cdot b+a\cdot c)+a\\ &=a\cdot b+(a\cdot c+a)\\ &=a\cdot b+a\cdot S(c). \end{aligned}$$

The penultimate equality uses associativity of addition, itself proved by an earlier induction. Thus $P(S(c))$ follows, and distributivity holds for every natural $c$.

Proof: associativity of multiplication

We prove $(a\cdot b)\cdot c=a\cdot(b\cdot c)$ by induction on $c$, using the already established distributivity and addition laws. The base case is

$$(a\cdot b)\cdot0=0=a\cdot0=a\cdot(b\cdot0)$$

For the step, the induction hypothesis and distributivity give

$$\begin{aligned} (a\cdot b)\cdot S(c) &=(a\cdot b)\cdot c+a\cdot b\\ &=a\cdot(b\cdot c)+a\cdot b\\ &=a\cdot(b\cdot c+b)\\ &=a\cdot(b\cdot S(c)) \end{aligned}$$

The last equality uses the recursive multiplication rule, completing the induction. Positive factors also have positive product: write $r=S(r')$ and $s=S(s')$. Then

$$r\cdot s=r\cdot S(s')=r\cdot s'+S(r')=S(r\cdot s'+r')\ne0.$$

The last step uses recursive addition and the axiom that zero is not a successor. This will justify the signed-representative argument in $Z$.

Worked example 3.2.10

(Proving $n+1=1+n$ without assuming commutativity)

Write $1=S(0)$. First, the recursive rule gives

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

Now prove $S(n)=1+n$ by induction. At $n=0$, both sides are $S(0)$. If $S(n)=1+n$, then

$$S(S(n))=S(1+n)=1+S(n),$$

where the last equality is the recursive rule. Hence $S(n)=1+n$ for every $n$, and combining the two identities yields $n+1=1+n$.

How commutativity of multiplication is organized

The recursive definition expands the second input, so the identity $a\cdot b=b\cdot a$ cannot be justified by simply swapping symbols in the definition. A useful auxiliary lemma is proved first by induction on $a$:

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

For $a=0$, both sides are $0$. If the identity holds for $a$, the successor rule for the second input and the induction hypothesis give

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

Associativity and commutativity of addition, already established from the recursive addition rules, rearrange this to the expression required in the next induction step: using $S(x)=x+1$ and the recursive expansion $b\cdot S(a)=b\cdot a+b$, the target is $b\cdot S(a)+S(a)=b\cdot a+b+a+1=b\cdot a+a+S(b)$. The lemma therefore supplies the missing orientation. Now induction on $b$ proves commutativity: the base case is $a\cdot 0=0=0\cdot a$; for the successor case,

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

This proof architecture matters: each rearrangement cites a previously proved addition fact, while each recursive expansion follows the stated definition. It prevents the circular argument that treats multiplication as commutative merely because its notation looks symmetric.

Quick checks

Quick check

(What is the base case in the recursive definition of addition?)

Think about which input is fixed first.

Solution · Answer

The base case is $a + 0 = a$.

Quick check

(What is the base case in the recursive definition of multiplication?)

Look at the second input.

Solution · Answer

The base case is $a \cdot 0 = 0$.

Quick check

(Using the recursive rule, what is $a \cdot S(b)$?)

State the next multiplication value in terms of the previous one.

Solution · Answer

It is $(a \cdot b) + a$.

Quick check

(In an induction proof, what is the induction hypothesis?)

Use one short sentence.

Solution · Answer

It is the assumption that the claim holds for an arbitrary but fixed natural number $n$, used to prove it for $S(n)$.

Read this first

If you want the formal setup for the natural numbers, review 3.1 Natural numbers and Peano's axioms.