## 1.4 Exercise 4

"(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.)

(a)

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.

(b)

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.