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 definitions of addition of the natural numbers, and the successor function S(a). In particular:

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

For the proof of commutativity, it is useful to define another natural number closely related to the successor function, namely "1". We define 1 to be the successor of 0, in other words,

1 = S(0).

Note that for all natural numbers a,

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). Clearly, for a = 0, we have 0 + 1 = 0 + S(0) = S(0 + 0) = S(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.

See also

References

    This article is issued from Wikipedia - version of the 12/4/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.