# A finite set always has a maximum and a minimum.

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.

• Commented Nov 2, 2013 at 8:49
• Suppose there is no maximal element then what happens? For every element $x \in S$,you can always find $y \in S$ such that $x<y$.So,... Commented Nov 2, 2013 at 8:49
• You mean a nonempty finite set?
– bof
Commented Nov 2, 2013 at 9:11
• isn't this weierstrass theorem?
– Ant
Commented Nov 2, 2013 at 13:31
• Commented Feb 13, 2015 at 18:32

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.

• I see where you are coming from, and your proof is through. Thank you for taking the time for answering this. However, I am not really sure whether I can use proof for induction when such elements are not in $\mathbf{N}$. Some time in the past, I tried to use a similar method for proving a statement about $\mathbf{R}$ and was told that I couldn't use proof by induction. I found this link which says otherwise and is pretty through: math.stackexchange.com/questions/4202/induction-on-real-numbers. Would you mind elaborating on why do you think induction would work in this case? Commented Nov 2, 2013 at 21:09
• It is true that you cannot use induction on a set where well-ordering does not hold, such as the real numbers. However, notice that my proof uses induction on $n \in \mathbb N$, and induction holds for the natural numbers due to well-ordering. We are NOT inducting on the elements of $S$ (for all we know, each $s_i \in S$ could be real numbers, or matrices, or purple hippos). Commented Nov 3, 2013 at 1:48
• Are you then implying that a finite set on $\mathbf{R}$ does not always have a maximum and a minimum? Commented Nov 3, 2013 at 21:13
• No, I'm not. As I have proven, finite sets on $\mathbb R$ always have a maximum and a minimum. I suspect that you are confusing the set that we are induction on (that is, the natural numbers, since finite sets always have a cardinality that belongs to $\mathbb N$) with the set that the elements of $S$ belong to (say, the real numbers). Commented Nov 4, 2013 at 11:52
• I guess the proof here assumes there's an order relation on the elements of S. Commented Dec 6, 2018 at 20:14

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.

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.

• If you really want to argue this silly point, a simpler and clearer example is $\{ \text{potato}, \text{bicycle}\}$.
– MJD
Commented Sep 3, 2021 at 13:14
• That's a good point! One must be careful when dealing with order theory. By the way, did you mean "if the set is totally ordered" ? Instead of "well ordered" Commented Jun 1, 2023 at 9:16

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.

• Sorry, but this proves nothing. Besides, proving the statement in the question by induction is the way to go. Commented Feb 1, 2019 at 12:59
• Sorry, but induction is actually proved from this theorem, so using it begs the question. Commented Feb 1, 2019 at 20:06
• Suppes uses Tarski's definition of a finite set, which is: A set is finite iff all its non-empty families of subsets have a minimal element. Thus G and F must have minimal elements if the set is finite. But if one doesn't have a maximal element, then the other can't have a minimal element, which contradicts Tarski's definition. Commented Feb 1, 2019 at 20:22
• And I quote from Suppes et al. "The proof of the theorem about induction for finite sets is facilitated by having available the already defined notion of maximal element of a family of subsets." Commented Feb 1, 2019 at 20:49
• There's no hint in the question that Tarski's definition is used and I find it unlikely. Anyway, the argument you sketch should be better written. Commented Feb 1, 2019 at 21:24

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.

• How do you know that $m$ and $M$ even exist? This exactly what the question asks. Commented Nov 23, 2015 at 20:48
• How do you prove they are well-defined? The question is essentially requiring to show that you can do that. The answer by ILoveMath use an approach similar to yours, but with an actual proof that this is well-defined for any finite number of arguments. You can't just reduce something to an equivalent problem and call it a proof, especially if you don't actually solve that equivalent problem. Commented Nov 30, 2015 at 13:49
• Yes, that's fine, but it is an inductive definition, and the question is about a rigorous proof that a finite set has minimum and maximum. So the inductive argument needs to be brought up. You can't avoid it, and your answer sweeps this under the rug. Commented Jul 30, 2016 at 18:02
• Which appears in details in the two answers there were there two years before you posted your answer; and does not appear in your answer at all. Commented Jul 30, 2016 at 18:06
• Sure, and I wouldn't expect anyone to prove to me that this is well-defined when I referee a paper. I would, however, expect someone who is asking why a finite set has a minimum and maximum (and clearly, the real analysis tag means this is a set of real numbers) expect the answer to be more than "well, just apply the minimum and maximum functions to the set" which is circular and terrible. And if someone would have written me this answer in a set theory exam, they would have received exactly 0 points for it. Commented Jul 30, 2016 at 19:31