## 1.4 Exercise 4

"(a) Prove by induction that given , every nonempty subset of has a largest element.

(b) Explain why you cannot conclude from (a) that every nonempty subset of has a largest element."

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

(a)

Let be the set of all positive integers for which this statement is true. Then contains 1, since when the only nonempty subset of is , and the element 1 is the largest element because it's greater than or equal to itself.

Now suppose contains , we want to show it contains as well.

Let be a nonempty subset of . If consists of alone, then this is the largest element of . In fact is the largest element of all sets containing it. Notice that the subsets containing constitute the totality of *additional* subsets that we can append to the set of subsets of (that have a largest element *already* from the inductive hypothesis).

Thus is inductive, , and the statement is true for all .

We can create a little table to show this formally.

(b)

Pick . It is nonempty, but has no largest element! For, suppose it did, and pick it. Say it is . Then is larger, with (since is inductive, e.g.). We've reached a contradiction in our argument, and thus has no largest element.