Archive for September 10th, 2009

1.4 Exercise 4

September 10th, 2009 No comments

"(a) Prove by induction that given  n \in \mathbb{Z}_+ , every nonempty subset of  \{1, \ldots, n\} has a largest element.

(b) Explain why you cannot conclude from (a) that every nonempty subset of  \mathbb{Z}_+ has a largest element."

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


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

Now suppose  A contains  n , we want to show it contains  n+1 as well.

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

Thus  A is inductive,  A = \mathbb{Z}_+ , and the statement is true for all  n \in \mathbb{Z}_+ .

We can create a little table to show this formally.



Pick  \mathbb{Z}_+ \subset \mathbb{Z}_+ .  It is nonempty, but has no largest element!  For, suppose it did, and pick it. Say it is  x .  Then  x+1 is larger, with  x+1 \in \mathbb{Z}_+ (since  \mathbb{Z}_+ is inductive, e.g.).  We've reached a contradiction in our argument, and thus  \mathbb{Z}_+ has no largest element.