Addition of natural numbers/proofs

From Wikipedia, the free encyclopedia

This mathematics article is devoted entirely to providing mathematical proofs and support for claims and statements made in the article Addition of natural numbers. This article is currently an experimental vehicle to see how well we can provide proofs and details for a math article without cluttering up the main article itself. See Wikipedia:WikiProject Mathematics/Proofs for some current discussion. This article is "experimental" in the sense that it is a test of one way we may be able to incorporate more detailed proofs in Wikipedia.

Here we will define it from Peano's axioms (see natural number) and prove some simple properties. The set of natural numbers will be denoted by N, and "0" will be used to denote the natural number which is not the successor of any other natural number.

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.

[edit] 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.

[edit] Proof of identity element

Definition [A1] states directly that 0 is a left identity. We prove that 0 is a right 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.

[edit] Proof of commutativity

We prove commutativity 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) [by A2]

= S((a + 1) + 0)

= 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