Munkres - Integers & Real Numbers

Adar Kahiri
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.