“(a) Prove by induction that given 
, every nonempty subset of 
has a largest element.
(b) Explain why you cannot conclude from (a) that every nonempty subset of 
has a largest element.”
(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 34.)
(a)
Let 
be the set of all positive integers for which this statement is true. Then contains 1, since when 
the only nonempty subset of 
is 
, and the element 1 is the largest element because it’s greater than or equal to itself.
Now suppose contains 
, we want to show it contains 
as well.
Let 
be a nonempty subset of 
. If consists of 
alone, then this is the largest element of . In fact is the largest element of all sets containing it. Notice that the subsets containing constitute the totality of additional subsets that we can append to the set of subsets of (that have a largest element already from the inductive hypothesis).
Thus is inductive, 
, and the statement is true for all .
We can create a little table to show this formally.
(b)
Pick 
. It is nonempty, but has no largest element! For, suppose it did, and pick it. Say it is 
. Then 
is larger, with 
(since is inductive, e.g.). We’ve reached a contradiction in our argument, and thus has no largest element.