Problem 4: Prove by induction that given $$n \in \mathbb{Z}_+$$, every nonempty subset of $$\{1, \ldots, n\}$$ has a largest element. Explain why you cannot conclude from this fact that every nonempty subset of $$\mathbb{Z}_+$$ has a largest element.

We can use an argument symmetrical to what Munkres used to prove the well-ordering property. Let $$A$$ be the set of all $$n \in \mathbb{Z}_+$$ for which $$S_{n+1} = \{1, \ldots, n\}$$ has a largest element. It follows that $$n=1$$ is in $$A$$ because $$S_{2} = \{1\}$$, where $$1$$ is the largest element. Now, assuming what we are trying to prove is true for $$n$$, we must prove it for $$n+1$$. Consider a subset $$C$$ of the set $$\{1, \ldots, n+1\}$$.. If $$n+1 \in C$$, then $$n+1$$ is the largest element of $$C$$. Otherwise, $$C$$ will be a nonempty subset of $$\{1, \ldots, n\}$$, and since we assumed any subset of $$\{1, \ldots, n\}$$ has a largest element, $$C$$ must have a largest element. Thus, having also proved the base case of $$n=1$$, $$A$$ is inductive and so $$A = \mathbb{Z}_+$$.

However, we cannot conclude from this that every nonempty subset of $$\mathbb{Z}_+$$ has a largest element because $$\mathbb{Z}_+$$ is not bounded above, meaning there can exist subsets of $$\mathbb{Z}_+$$ which are also not bounded above and therefore cannot have a largest element.