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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Infinity[edit | edit source]

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 | edit source]

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 .