## 1.4 Exercise 3

To get acquainted with the set of positive integers and how this set is related to "proving things by induction," this problem is a great primer!

"(a) Show that if is a collection of inductive sets, then the intersection of the elements of is an inductive set.

(b) Prove the basic properties of :

- (1) is inductive;
- (2) (Principle of induction). If is an inductive set of positive integers, then ."

(Taken from *Topology* by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 34.)

-----

SOLUTION

(a)

We want to attempt this by contrapositive. Thus we want to show that if the intersection of the sets in the collection is not inductive, then the collection is not a collection of inductive sets. There are two ways in which the intersection of the sets in the collection can fail to be inductive: if is not in the intersection of the collection, or if for some element in the intersection of the collection, is not in there too.

First, if is not in the intersection of the collection , this means at least one set of such collection does not contain as an element... such a set or several are therefore not inductive, differing from the definition of ``inductive.'' But then is not a collection of (all) inductive sets.

Second, if for some element in the intersection the collection, is not in the intersection of the collection, then this of course means that at least one of the sets of the collection does not contain as an element. Since each individual set of the collection did contain in the first place (this element being in the intersection of the collection), such a set or several fail the definition of ``inductive." Naturally, then the collection is not a collection of inductive sets.

(b)

To prove (1), we resort to the definition of : , with is a collection of (all) inductive subsets of . Next, apply the result of Part (a), and is inductive.

Recall that is an inductive set of positive integers. To show (2), we do so in the usual way we show mutual containment, first by proving and then . Thus:

. since is inductive, and since is inductive (by (1)). Next, is an element of , and since it is an (positive) integer, we know it is generated by successive additions of 1. Such an is common to all inductive sets, and so it belongs to the intersection of the collection of all inductive sets: . Well, is an element of being a positive integer too, and such element is common to all inductive sets as well; it lies in the collection of all inductive sets. (Notice we are using actual induction to show this inclusion). Thus all elements of lie in the intersection of all inductive sets of .

. Pick an element . Since , and is a member of such collection, then such an .