A finite set always has a maximum and a minimum.

Question

I am pretty confident that this statement is true. However, I am not sure how to prove it. Any hints/ideas/answers would be appreciated.

Answer 1

Let $S = \{s_1, \ldots,s_n\}$ be a nonempty finite set of size $n > 0$. We will show by induction on $n \in \mathbb N$ that there exist some $m,M \in S$ such that for all $s \in S$, we have that $m \leq s \leq M$.

Base Case: For $n=1$, we have $S = \{s_1\}$, so taking $m = s_1$ and $M=s_1$ trivially satisfies the required condition.

Induction Hypothesis: Assume that the claim holds for $n=k$, where $k \geq 1$.

It remains to prove that the claim holds true for $n = k+1$. To this end, choose any set $S$ with $k+1$ elements, say $S = \{s_1 ,\ldots,s_k,s_{k+1}\}$. Now by the induction hypothesis, the subset: $$ S' = S \setminus \{s_{k+1}\} = \{s_1 ,\ldots,s_k\} $$ has a minimum element and a maximum element. That is, we know that there exists some $m',M' \in S'$ such that for all $s' \in S'$, we have that $m' \leq s' \leq M'$. Now observe that $s_{k+1}$ must fall under $1$ of $3$ cases:

Case 1: Suppose that $s_{k+1} < m'$. Then take $m = s_{k+1}$ and $M=M'$. To see why this works, observe that any element in $S$ is either $s_{k+1}$ or some $s' \in S'$, and: $$ m = s_{k+1} < m' \leq s' \leq M' =M $$

Case 2: Suppose that $m' \leq s_{k+1} \leq M'$. Then take $m = m'$ and $M=M'$. To see why this works, observe that any element in $S$ is either $s_{k+1}$ or some $s' \in S'$, and: $$ m = m' \leq s_{k+1} \leq M' = M $$ $$ m = m' \leq s' \leq M' = M $$

Case 3: Suppose that $s_{k+1} > M'$. Then take $m =m'$ and $M=s_{k+1}$. To see why this works, observe that any element in $S$ is either $s_{k+1}$ or some $s' \in S'$, and: $$ m = m' \leq s' \leq M' < s_{k+1} = M $$

Hence, we have shown that $S$ has a minimum and maximum element, as desired.

Answer 2

Let $F$ be a finite set. if $F$ is $\{x\} $ then we are done since we vacouly have $x \geq x $ and hence $x = \max \{ x \} $. If $F = \{ a_1 ,... a_n \} $. assume they are different, otherwise we are back again to singleton case. Now, take $a_1$. IF $a_1 $ is greater than any other $a_i$ then set $a_1 = \max F $ and we are done. IF not, take $a_2$, and repeat previous step. Continue in this manner inductively. Eventually, we get the max.

Answer 3

One needs to be careful about the set where to work, and the definition of the ordering. If the set is well ordered, then the above proof works fine. Otherwise, it can happen that there is a supremum, but not a maximum. We can, for example, consider the partial ordering on the set of $2\times 2$ real-valued matrices, where two matrices $A$ and $B$ are such that $A\le B$ if and only if all the entries of $B-A$ are non-negative.

With the above-mentioned order relation and set, we consider the subset $$ E = \left\{ \begin{pmatrix} 1 & 0 \\ 0& 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0& 1 \end{pmatrix} \right\} .$$

We can see that $E$ is bounded from above (by $ \begin{pmatrix} 1 & 0 \\ 0& 1 \end{pmatrix}$ for example), and from below( by $\begin{pmatrix} 0 & 0 \\ 0& 0 \end{pmatrix}$ for example). However, the two elements of $E$ are not comparable using the defined order relation, so none of them is the maximum.