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)
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)