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.

Answer 4

I would just say based on Suppes, that use of induction to prove this conjecture begs the question for the following reasons:

1. The minimality or maximality of the elements within a set, A, cannot be defined without specifying an ordering relation, R, on A.
2. Different R's will yield different minimal elements, called R-minimal elements.
3. Set A only has a unique R-minimal element iff all its non-empty subsets have unique R-minimal elements, R is connected, and R is asymmetric. (i.e. R is a well ordering)
4. Having a unique R-minimal element does not guarantee a unique R-maximal element unless A is finite.

Set A is finite iff every non-empty family of subsets of A has a minimal element [ordered by strict inclusion '$\subset$']- A. Tarski via Suppes

Furthermore, if one such family of subsets, F, has a minimal element , then it must also have a maximal element via the following argument:

If F has a minimal element, then construct G from the elements of F where z is an element of G iff for some y in F, z is Union F - y. If z is minimal in G, then y is maximal in F, and vice versa. If F does not have a maximal element, then G cannot have a minimal element, but G does have a minimal element, hence contradiction, and the theorem is proved.

Answer 5

I suppose you mean a set of numbers, $S=\{s_1,s_2,\dots,s_n\}$ and $n$ is the finite size, just let

$$ m=\min(s_1,s_2,\dots,s_n) $$ $$ M=\max(s_1,s_2,\dots,s_n) $$ Q.E.D.