Theorem 4.12: If n is a natural number and

then there is a natural number m such that

Proof: We proceed by induction on n. If n = 0, then it is empty, and if

by hypothesis and since we also have

by Theorem 4.1 we would have

by Definition 1.2, and the identity function would establish a one to one correspondence between S and the natural number 0.

We next assume that the result is true for n = k, and seek to show that it is true for n = k + 1. Let

If S = k + 1, then the identity function on S will set up a one to one correspondence between S and the natural number k + 1. So we can assume that

In that case k + 1 will not be a subset of S or else we would have equality by Definition 1.2. Then there exists an element

with

Define a function

by

and

Note that g is one to one and onto. Let T = g(S). Since

it follows that

and therefore

By the induction hypothesis, there exists a natural number m and a one to one correspondence

Then

is a one to one correspondence by Theorem 3.3.