Prove that every nonempty finite set has a maximum.

Question

how do I prove that every nonempty finite set has a maximum. I know how to explain this by words but didn't know how to put it into mathematical form. I found a way to prove this by induction in MathExchange but it was so complicated.

Answer 1

Here is a proof by contradiction.

Pick $x_1$. If the last picked element is $x_i$, then either $x_i$ is a maximum or you can pick $x_{i+1}\gt x_i$. If the process terminates you have found a maximum.

Suppose there are $n$ elements in the set, and the process does not terminate. $\{x_1, \dots x_{n+1}\}$ must have two equal elements. Since the elements are distinct (because of the order), this is impossible. Hence the process terminates with a maximum.

This uses the pigeonhole principle - a fact about maps between finite sets.

Answer 2

This is really a statement about order.

You have some finite set $S$ and a total order $\le$ (that is, for any $x,y \in S$, either $x \le y $ or $y \le x$).

Given a non-empty finite set $S$, we say that $m$ is a maximum of $S$ iff $m \in S$ and for all $x \in S$, we have $x \le m$.

Induction is straightforward. Suppose $S$ is a non-empty, finite set.

The proposition is that for all sets of size $|S| \le n$ that a maximum of $S$ exists.

For $n=1$, just choose the element of the set.

Suppose the statement is true for $n$, and let $S$ be a set with $|S| = n+1$. Choose $x \in S$ and form $S' = S \setminus \{x\}$. By assumption, $S'$ has a maximum $m'$. If $x \le m'$, then let $m=m'$, otherwise if $m' \le x$ and $m' \neq x$, let $m = x$. Then we have $m \in S$ and $x \le m$ for all $x \in S$, hence $m$ is a maximum of $S$.