Proofs Involving The Addition of Natural Numbers - Proof of Commutativity

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)
= S(S(a) + 0)
= S((a + 1) + 0)
= S(a + 1)
= S(1 + a)
= 1 + S(a)

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)
= (a + b) + 1
= (b + a) + 1
= b + (a + 1)
= b + (1 + a)
= (b + 1) + a
= S(b) + a

This completes the induction on b.

Read more about this topic:  Proofs Involving The Addition Of Natural Numbers

Famous quotes containing the words proof of and/or proof:

    There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.
    François, Duc De La Rochefoucauld (1613–1680)

    O, popular applause! what heart of man
    Is proof against thy sweet, seducing charms?
    William Cowper (1731–1800)