Proving the Properties of Natural Numbers

Date: 03/09/2000 at 10:53:15
From: Harsha
Subject: How to prove a+b = b+a

Dear Dr. Math,

Can you please tell me how to prove or derive the commutative property 
of addition (i.e. a+b = b+a)? Does this have something to do with set 
theory?

Also, how does one go about proving or deriving the associative and 
distributive properties of numbers?

Thanks,
Harsha

Date: 03/10/2000 at 11:13:39
From: Doctor Rob
Subject: Re: How to prove a+b = b+a

Thanks for writing to Ask Dr. Math, Harsha.

First you prove the Commutative, Associative and Distributive Laws in 
the set of natural numbers N. Then you use the definitions of the 
larger systems of the integers Z, the rational numbers Q, the real 
numbers R, and the complex numbers C, to show that the Laws in each of 
these systems follows from that in N. So it all boils down to proving 
this in N.

Here are the proofs of all the usual arithmetic properties of the 
natural numbers.

=====================================================================
The Peano Postulates

The smallest set N which satisfies the following postulates is 
indistinguishable from, and can be taken to be, the natural numbers:

     P1.  1 is in N.
     P2.  If x is in N, then its "successor" x' is in N.
     P3.  There is no x in N such that x' = 1.
     P4.  If y in N isn't 1, then there is a x in N such that x' = y.
     P5.  If x and y are in N and x' = y', then x = y.
     P6.  If S is a subset of N, 1 is in S, and the implication
          (x in S ==> x' in S) holds, then S = N.

This is the recursive definition of addition:

     D+:  Let a and b be in N.
          (1) If b = 1, then define a + b = a' (using P1 and P2).
          (2) If b isn't 1, then let c' = b, with c in N (using P4), 
              and define a + b = (a + c)'.

This can be restated as D+(1) a + 1 = a', and D+(2) a + b' = (a + b)'.

This is the recursive definition of multiplication:

     D*:  Let a and b be in N.
          (1) If b = 1, then define a * b = a.
          (2) If b isn't 1, then let c' = b, with c in N (using P4), 
              and define a * b = (a * c) + a.

This can be restated as D*(1) a * 1 = a, and D*(2) a * b' = (a*b) + a.


Theorem 1: If a is in N, then 1 + a = a + 1.

Proof: Let T(1) be the set of all a for which 1 + a = a + 1. Then 1 is 
in S trivially. Now suppose that a is in S. Then

     1 + a' = (1 + a)'   by D+(2)
            = (a + 1)'   since a is in S by hypothesis
            = (a')'      by D+(1)
            = a' + 1     by D+(1)

Thus a' is in S. Then by P6, S = N, and the theorem is proven.


Theorem 2 (Commutative Law of Addition): If a and b are in N, then 
                                                        a + b = b + a.

Proof: Let S be the set of all b such that a + b = b + a for every a 
in N. By Theorem 1, 1 is in S. Suppose that b is in S.  Now let T(b') 
be the set of all a such that a + b' = b' + a. By Theorem 1, 1 is in 
T(b'). Then if a is in T(b')

     a' + b' = (a' + b)'     by D+(2)
             = (b + a')'     since b is in S by hypothesis
             = ((b + a)')'   by D+(2)
             = ((a + b)')'   since b is in S by hypothesis
             = (a + b')'     by D+(2)
             = (b' + a)'     since a is in T(b') by hypothesis
             = b' + a'       by D+(2)

Thus a' is in T(b'). Then by P6, T(b') = N. Thus b' is in S. Then by 
P6, S = N, and the theorem is proven.


Theorem 3 (Associative Law of Addition): If a, b, and c are in N, then 
                                            a + (b + c) = (a + b) + c.

Proof: Let S be the set of all c such that a + (b + c) = (a + b) + c 
for every a and b in N. Then

     a + (b + 1) = a + b'        by D+(1)
                 = (a + b)'      by D+(2)
                 = (a + b) + 1   by D+(1)

Thus 1 is in S. Now suppose that c is in S. Then

   a + (b + c') = a + (b + c)'     by D+(2)
                = (a + (b + c))'   by D+(2)
                = ((a + b) + c)'   since c is in S by hypothesis
                = (a + b) + c'     by D+(2)

Thus c' is in S. Then by P6, S = N, and the theorem is proven.


Theorem 4: If a is in N, 1 * a = a.

Proof: Let S be the set of all a in N such that 1 * a = a. Then 1 is 
in S by D*(1). Let a be in S. Then

     1 * a' = (1 * a) + 1   by D*(2)
            = a + 1         since a is in S by hypothesis
            = a'            by D+(1)

Thus a' is in S. Then by P6, S = N, and the theorem is proven.


Theorem 5 (Commutative Law of Multiplication): If a and b are in N, 
                                                   then a * b = b * a.

Proof: Let S be the set of all b such that a * b = b * a for every a 
in N. Then 1 is in S by Theorem 4. Let b be in S. Let T(b') be the set 
of all a in N such that a * b' = b' * a. Then 1 is in T(b') by Theorem 
4. Let a be in T(b'). Then

     a * b' = (a' * b) + a'          by D*(2)
            = (b * a') + a'          since b is in S by hypothesis
            = ((b * a) + b) + a'     by D*(2)
            = ((a * b) + b) + a'     since b is in S by hypothesis
            = (a * b) + (b + a')     by Theorem 3
            = (a * b) + (b + a)'     by D+(2)
            = ((a * b) + (b + a))'   by D*(2)
            = (((a * b) + b) + a)'   by Theorem 3
            = (((b * a) + b) + a)'   by Theorem 2
            = ((b * a') + a)'        by D*(2)
            = (b * a') + a'          by D+(2)
            = b' * a'                by D*(2)

Thus a' in is T(b'). Then by P6, T(b') = N. Thus b' is in S. Then by 
P6, S = N, and the theorem is proven.


Theorem 6 (Distributive Law): If a, b, and c are in N, then 
                                      (a + b) * c = (a * c) + (b * c).

Proof: Let S be the set of all c for which the equation is true for 
all a and b in N. Then

     (a + b) * 1 = a + b               by D*(1)
                 = (a * 1) + (b * 1)   by D*(1)

Thus 1 is in S. Now suppose that c is in S. Then

     (a + b) * c' = ((a + b) * c) + (a + b)         by D*(2)
                  = ((a * c) + (b * c)) + (a + b)   since c is in S
                  = (((a * c) + (b * c)) + a) + b   by Theorem 3
                  = ((a * c) + ((b * c) + a)) + b   by Theorem 3
                  = ((a * c) + (a + (b * c))) + b   by Theorem 2
                  = (((a * c) + a) + (b * c)) + b   by Theorem 3
                  = ((a * c) + a) + ((b * c) + b)   by Theorem 3
                  = (a * c') + (b * c')             by D*(2)

Thus c' is in S. Then by P6, S = N, and the theorem is proven.


Theorem 7 (Associative Law of Multiplication): If a, b, and c are in 
                                    N, then (a * b) * c = a * (b * c).

Proof: Let S be the set of all c such that (a * b) * c = a * (b * c) 
for all a and b in N. Then

     (a * b) * 1 = a * b         by D*(1)
                 = a * (b * 1)   by D*(1)

Thus 1 is in S. Now let c be in S. Then

     a * (b * c') = a * ((b * c) + b)         by D*(2)
                  = (a * (b * c)) + (a * b)   by Theorem 6
                  = ((a * b) * c) + (a * b)   by Theorem 5
                  = (a * b) * c'              by D*(2)

Thus c' is in S. Then by P6, S = N, and the theorem is proven.
=====================================================================
Be aware that some authors have a different version of the Peano 
Postulates where 0 replaces 1 in P1, P3, P4, and P6, and D+(1) reads 
"a + 0 = a," and D*(1) reads "a * 0 = 0."  This makes the proofs above 
not quite right, but slight adjustments are all that is needed. It 
also means that for them, the natural numbers include 0. There is 
quite a debate about whether 0 should or should not be considered a 
natural number, and no general agreement on this point.

There are also versions where P3 and P4 are combined into one axiom, 
and lots of other wordings and notations, but essentially, these are 
the Peano Postulates.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/12/2000 at 00:39:08
From: Harsha
Subject: Re: How to prove a+b = b+a

Dear Dr. Rob,

Thanks a lot for proving the Properties of Natural Numbers. This 
really cleared up my doubts about the natural numbers.

Thanks,
Harsha