Proving the Properties of Natural Numbers

To develop a comprehensive theory of mathematical sets, you must start from the basics.  First, we prove the Commutative, Associative and Distributive Laws in the set of natural numbers N.  Then we 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 those 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.

Addition

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)'.

Multiplication

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.  See "Is Zero a Natural Number?" for more information about this issue.

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.

Internet References

Information on this page comes from Doctor Rob, The Math Forum 

Related Pages in this Website

Is Zero a Natural Number? -- a discussion of the fact that some authors include zero, and others do not.

Introduction to Counting -- explains what mathematicians mean by "counting" -- that is, putting sets in one-to-one correspondence.

Construction -- Construction of sets of numbers, starting with the original Peano Axioms, formulated so that zero is included in the set of natural numbers.

Set Theory -- an introduction to sets, including examples of some standard sets.

Counting Ordered Pairs of Integers -- An explanation of the "square spiral" that puts the set of natural numbers in one-to-one correspondence with the set of rational numbers.

Abstract Algebra -- definitions of terms associated with Ring Theory and Group Theory

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]