The number of elements
For finite sets we can now agree upon what the number of elements is. We called (and still call) a set, F, finite if there is a natural number n such that F and {i:0≤i<n} have the same size. It seems clear that that n should be `the number of elements of F'. But that overlooks one important point: when we say "that n" we (implicitly) assume that there is exactly one such n. But that needs a proof. The following theorem makes that proof possible.
Theorem If m and n are different natural numbers then {i:0≤i<m} and {i:0≤i<n} do not have the same size.
From this theorem the uniqueness of n is readily established: if F has the same size as both {i:0≤i<m} and {i:0≤i<n} then the latter sets, {i:0≤i<m} and {i:0≤i<n}, also have the same size and the theorem tells us that m=n.
Now we can define the number of elements of F to be that unique n.
If you think that the theorem is `obviously true': explain why and use nothing more than the minimal amount of information about the natural numbers given in a previous post.
As an example of how such a proof might work we show that a subset of a finite set is again finite. To begin we show for every n that every subset of {i:0≤i<n} is finite.
For n=0 this is true: every subset of {i:0≤i<0} is the empty set and therefore finite.
Assume that for a certain n we have determined that the statement is true. We show that this implies that ever subset of {i:0≤i<n+1} is finite as well. Let X be such a subset. If n is not in X then X is actually part of {i:0≤i<n} and hence finite. If n is in X then we take the part of X that is in {i:0≤i<n} and call it Y. If Y is empty then X consists of just the number n and we can enumerate it as {x0}, where x0=n of course. If Y is not empty we can enumerate it as {y0,…,yk-1} for some k now put yk=n; we have enumerated all of X.
The set of natural numbers is the smallest set that contains 0 and with every member n also n+1; the set of numbers for which the statement is true has these properties, so it is all of N. Now complete this argument by showing that every subset of every finite set is also finite.
For those who think the above result is clear "of course a part of something finite is finite too": such is the mathematician's lot, if something is not part of the assumptions, and the latter statement definitely is not, then it must be proven.
What we did here constitutes a proof by Mathematical Induction. This the method to prove statements about natural numbers. We shall use it again in the proof of the Theorem but first we need to get some tools first.