Proofs involving the addition of natural numbers

This article contains mathematical proofs for some properties of addition of the natural numbers: the additive identity, commutativity, and associativity. These proofs are used in the article Addition of natural numbers.

Definitions

This article will use the Peano axioms for the definition of natural numbers. With these axioms, addition is defined from the constant 0 and the successor function S(a) by the two rules

A1:	a + 0 = a
A2:	a + S(b) = S(a + b)

For the proof of commutativity, it is useful to give the name "1" to the successor of 0; that is,

1 = S(0).

For every natural number a, one has

	S(a)
=	S(a + 0)	[by A1]
=	a + S(0)	[by A2]
=	a + 1	[by Def. of 1]

Proof of associativity

We prove associativity by first fixing natural numbers a and b and applying induction on the natural number c.

For the base case c = 0,

(a + b) + 0 = a + b = a + (b + 0)

Each equation follows by definition [A1]; the first with a + b, the second with b.

Now, for the induction. We assume the induction hypothesis, namely we assume that for some natural number c,

(a + b) + c = a + (b + c)

Then it follows,

	(a + b) + S(c)
=	S((a + b) + c)	[by A2]
=	S(a + (b + c))	[by the induction hypothesis]
=	a + S(b + c)	[by A2]
=	a + (b + S(c))	[by A2]

In other words, the induction hypothesis holds for S(c). Therefore, the induction on c is complete.

Proof of identity element

Definition [A1] states directly that 0 is a right identity. We prove that 0 is a left identity by induction on the natural number a.

For the base case a = 0, 0 + 0 = 0 by definition [A1]. Now we assume the induction hypothesis, that 0 + a = a. Then

	0 + S(a)
=	S(0 + a)	[by A2]
=	S(a)	[by the induction hypothesis]

This completes the induction on a.

Proof of commutativity

We prove commutativity (a + b = b + a) by applying induction on the natural number b. First we prove the base cases b = 0 and b = S(0) = 1 (i.e. we prove that 0 and 1 commute with everything).

The base case b = 0 follows immediately from the identity element property (0 is an additive identity), which has been proved above: a + 0 = a = 0 + a.

Next we will prove the base case b = 1, that 1 commutes with everything, i.e. for all natural numbers a, we have a + 1 = 1 + a. We will prove this by induction on a (an induction proof within an induction proof). We have proved that 0 commutes with everything, so in particular, 0 commutes with 1: for a = 0, we have 0 + 1 = 1 + 0. Now, suppose a + 1 = 1 + a. Then

	S(a) + 1
=	S(a) + S(0)	[by Def. of 1]
=	S(S(a) + 0)	[by A2]
=	S((a + 1) + 0)	[as shown above]
=	S(a + 1)	[by A1]
=	S(1 + a)	[by the induction hypothesis]
=	1 + S(a)	[by A2]

This completes the induction on a, and so we have proved the base case b = 1. Now, suppose that for all natural numbers a, we have a + b = b + a. We must show that for all natural numbers a, we have a + S(b) = S(b) + a. We have

	a + S(b)
=	a + (b + 1)	[as shown above]
=	(a + b) + 1	[by associativity]
=	(b + a) + 1	[by the induction hypothesis]
=	b + (a + 1)	[by associativity]
=	b + (1 + a)	[by the base case b = 1]
=	(b + 1) + a	[by associativity]
=	S(b) + a	[as shown above]

This completes the induction on b.

References

Edmund Landau, Foundations of Analysis, Chelsea Pub Co. ISBN 0-8218-2693-X.