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:

    A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.
    Samuel Johnson (1709–1784)

    When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.
    Stephanie Martson (20th century)