Mathematical Proof and the Principles of Mathematics/Numbers/Natural numbers

Earlier, we constructed the natural numbers as sets, based on the axioms of set theory.

Now, we approach the natural numbers numbers from an arithmetic viewpoint, and we will see how we can derive the familiar notions of addition and multiplication from the successor operation. As we are moving away from set theory and into arithmetic, we will write $\mathbb {N}$ instead of $\omega$ to denote the natural numbers. Since we are about to introduce arithmetic, but haven't done so yet, we will provisionally in this section use S(n) instead of n + 1 to denote the successor of n.

Definitions

Definition Addition is defined from 0 and the successor function by the two rules

Def. 1:	a + 0 = a
Def. 2:	a + S(b) = S(a + b)

We will see first how this definition justifies our previous usage of a + 1 for the successor of a:

For every natural number a, one has

	S(a)
=	S(a + 0)	[by Def. 1]
=	a + S(0)	[by Def. 2]
=	a + 1	[by Def. of 1]

Induction principle

We will now show how all those properties of addition that you know from school can be derived from the definition.

The proofs rely on the induction principle. Recall the theorem:

Induction principle Suppose $P(x)$ is a property of natural numbers for which $P(0)$ holds, and such that for all natural numbers $n$ for which $P(n)$ holds, we have that $P(n+1)$ also holds. Then $P(n)$ holds for every natural number $n$ .

When writing a proof using the induction principle, we call the proof of $P(0)$ the base case, and the proof of $P(a+1)$ from $P(a)$ the induction step. In the proof of the induction step, we will use the fact that we can assume $P(a)$ and call that the induction hypothesis. Let's see this in action:

Addition with 0

Definition [Def. 1] states directly that 0 is a right identity, that is, that for any number a, a + 0 = a.

We prove that 0 is a left identity, that is, that 0 + a = a by induction on the natural number a.

Theorem For every natural number a, 0 + a = a.

For the base case a = 0, 0 + 0 = 0 by definition [Def. 1].

So we proceed to the induction step. We can assume the induction hypothesis, that 0 + a = a. Then

	0 + S(a)
=	S(0 + a)	[by Def. 2]
=	S(a)	[by the induction hypothesis]

So we have shown that 0 + S(a) = a from the assumption that 0 + a = a. So, we can conclude with the induction principle that 0 + a = a for every natural number a.

Associativity

Let us try our hand at a more complex example, the associativity property:

Theorem For any three natural numbers a, b and c, (a + b) + c = a + (b + c).

The first thing to note is that we have three numbers here, a, b and c. So we will fix a and b to be arbitrary numbers and we will apply the induction principle to c.

More precisely, the property $P(c)$ is $(a+b)+c=a+(b+c)$ .

For the base case c = 0,

(a+b)+0 = a+b = a+(b+0)

Each equation follows by definition [Def. 1]; the first with a + b, the second with b.

Now, for the induction step. 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 Def. 2]
=	S(a + (b + c))	[by the induction hypothesis]
=	a + S(b + c)	[by Def. 2]
=	a + (b + S(c))	[by Def. 2]

In other words, $P$ holds for S(c). Therefore, the induction on c is complete.

Commutativity

Another important property that you will now from school is commutativity: When adding to numbers, the order doesn't matter.

Theorem For any two natural numbers a and b, a + b = b + a.

Since this is even more involved, we introduce a lemma first.

A helpful lemma

Lemma For any two natural numbers a and b, S(a) + b = S(a + b).

Let's perform induction on b, starting with the base case b = 0:

	S(a) + 0
=	S(a)	[by Def. 1]
=	S(a + 0)	[by Def. 1]

And now the induction step:

	S(a) + S(b)
=	S(S(a) + b)	[by Def. 2]
=	S(S(a + b)	[by the induction hypothesis]
=	S(a + S(b))	[by Def. 2]

There we go - the induction on b is complete.

The proof of commutativity

From this brief digression we have earned ourselves a property that we can now use in the proof of commutativity.

We will proceed again by induction on b, starting with the base case:

	a + 0
=	a	[by Def. 1]
=	0 + a	[by the Right identity theorem]

Note how the base case is just a straightforward consequence of the identity property we showed above.

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)
=	S(a + b)	[by Def. 2]
=	S(b + a)	[by the induction hypothesis]
=	S(b) + a	[by the lemma]

This completes the induction on b.

Multiplication

By now we introduced addition, and we derived all the basic properties we know about addition on the natural numbers. But arithmetic is more than addition, of course. So, just like we derived addition from the successor relation, we will derive multiplication from addition:

Definition Multiplication is derived from 0, addition and the successor function by the two rules

Def. 3:	$a\cdot 0=0$
Def. 4:	$a\cdot S(b)=a\cdot b+a$

We can quickly check mentally that those two equations are indeed true in our intuition of the natural numbers.

Since you are familiar now with how to approach problems using induction, we leave the proofs of commutativity and associativity to you.

Distributivity

Before we let you, though, let us go through one more property that arises from having two different operators present. It is known as distributivity.

Theorem For every three natural numbers a, b and c, $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ .

We prove distributivity by induction on c:

Start with the base case:

	$a\cdot (b+0)$
=	$a\cdot b$	[by Def. 1]
=	$a\cdot b+0$	[by Def. 1]
=	$a\cdot b+a\cdot 0$	[by Def. 3]

...and proceed by induction:

	$a\cdot (b+S(c))$
=	$a\cdot S(b+c)$	[by Def. 2]
=	$a\cdot (b+c)+a$	[by Def. 4]
=	$(a\cdot b+a\cdot c)+a$	[by the induction hypothesis]
=	$a\cdot b+(a\cdot c+a)$	[by associativity of addition]
=	$a\cdot b+a\cdot S(c)$	[by Def. 4]

And this was to be proven.

Exercises

Skeletal outline of the interdependencies between the properties and their proofs. The empty proofs are for you to find!

Now that you have seen various techniques of inductive argument in action, you should try and figure out the remaining properties of multiplication for yourself.

Try to write them up line by line, with the source of any identity you use to the right of the equation, just as it is laid out on this page.

To help you, there is a skeletal outline of the dependencies between the properties in the diagram on the right. It also includes derivations of the properties that we have already seen, as well as the definitions of multiplication and addition.

Good luck!

References

The classical reference for the induction proofs on this page is Edmund Landau's Foundations of Analysis, Chelsea Pub Co. ISBN 0-8218-2693-X. there you can find a wealth of further properties and exercises as well as an introduction of exponentiation along the same lines.