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

Infinity edit

None of the Zermelo-Fraenkel axioms stated so far assert the existence of an infinite set. The next axiom of ZF set theory does just this.

First we need the concept of an inductive set.

Definition A set   is said to be inductive if   and   for all  . For a given set   we call   the successor of   and denote it  .

Axiom (Axiom of Infinity)

There exists an inductive set.

Whilst there are many inductive sets, we can prove the following.

Theorem There exists a unique inductive set which is a subset of all inductive sets.

Proof Let   be any inductive set. Such a set exists by the Axiom of Infinity.

Now let us define  . Note that   is a set by the Axiom Schema of Comprehension.

If   then   is in every inductive set. Thus   is a subset of every inductive set.

Since   is in every inductive set,  . Moreover, if   then   is in every inductive set and so   is in every inductive set. Thus  . Thus   is inductive.

To show that   is unique, suppose that   and   are both inductive sets which are subsets of all inductive sets. In particular we have that   and  . But then by the Axiom of Extensionality,  .  

Definition We denote   by   and   by   and   by  , etc. The unique inductive set that is a subset of all inductive sets is denoted  .

Note that  ,  ,  ,  .

In general   and so  .

Natural numbers edit

We have seen that   contains  . We call these the natural numbers. Note that in other fields of mathematics, the natural numbers do not include  , but in set theory it is convenient to include it.

Definition For natural numbers  , we shall write   instead of  .

One of the most useful theorems involving natural numbers is the following.

Theorem (Induction) Suppose   is a property of natural numbers for which   holds, and such that for all natural numbers   for which   holds, we have that   also holds. Then   holds for every natural number  .

Here is a straightforward result that can be proved using induction.

Theorem If   and   and   then  .

Proof We prove this by induction on  . In other words, we let   be the property that   and   then  .

  holds since in this case   is empty and there is nothing to prove.

Now suppose that   holds for some  . In other words, for that value of   we have that if   and   then  .

We wish to show that   holds. So assume that   and  . There are two cases.

As   there are two cases. The first case is  . Bu then by the inductive hypothesis,  . Thus  .

The other case is  . In this case  . Thus since   we have  . Thus we have shown that in either case   holds.

Thus by induction   holds for all natural numbers  .  

Here is another simple result that follows by induction.

Theorem Every element of   is either   or it is the successor of an element of  .

Proof We prove this by induction on   where   is the property that   is either   or the successor of some  .

Clearly   holds. Now suppose that   holds for some  . Thus either   or   for some  . In both cases   is the successor of   and thus   holds. Thus by induction   holds for all  .  

A useful variant of induction is the following.

Theorem (Strong induction) Let   be a property of the natural numbers such that if   holds for all   then   holds. Then such a property   holds for all natural numbers  .

Proof We prove this result by ordinary induction. Let   be the property that   holds for every  . Clearly   holds, since there are no elements of   to prove it for.

Now suppose that   holds for some  . In other words,   holds for all  .

But by assumption this implies that   holds. Thus   holds for all  . In other words,   holds.

Thus by ordinary induction,   holds for all natural numbers  .

But if   then   and so for all natural numbers   we have that   holds. But   and so in particular we have that   holds. In other words, we have shown that   holds for all natural numbers  .