Exercise 4.4

Proof. Let $A$ be the set of integers for which the hypothesis is true. Clearly, the result is then true if we can prove that $A={\mathbb{Z}}_{\text{+}}$. So first, clearly $1\in A$ since the set $\left\{1\right\}$ has only a single nonempty subset, i.e. $\left\{1\right\}$ itself, in which 1 is clearly the largest element. Now suppose that $n\in A$ so that every nonempty subset of $S_{n+1}=\left\{1,\dots ,n\right\}$ has a largest element. Consider any nonempty subset $B$ of $S_{n+2}=\left\{1,\dots ,n+1\right\}$, noting that $S_{n+2}=S_{n+1}\cup \left\{n+1\right\}$.

Case: $n+1\in B$. Then, for any other $k\in B$, $k\in S_{n+2}$ so that either $k=n+1$ or $k\in S_{n+1}$ so that $k<n+1$ by the definition of $S_{n+1}$. Thus in either case $k\le n+1$ so that $n+1$ is the largest element of $B$ since $k$ was arbitrary.

Case: $n+1\notin B$. Then clearly $B\subset S_{n+1}$ so that $B$ has a largest element by the induction hypothesis since $B$ is nonempty.

Hence in either case $B$ has a largest element so that $n+1\in A$ since $B$ was an arbitrary nonempty subset of $S_{n+2}=\left\{1,\dots ,n+1\right\}$. This shows that $A$ is an inductive set of positive integers so that $A={\mathbb{Z}}_{\text{+}}$, as desired by the Principle of Induction. □