The Integers and Real Numbers
June 2020
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.
\[\tag*{$\blacksquare$}\]