32
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ See Every finite set... $\endgroup$ – J. W. Perry Nov 2 '13 at 8:49
  • 2
    $\begingroup$ 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,... $\endgroup$ – wannadeleteacct Nov 2 '13 at 8:49
  • 2
    $\begingroup$ You mean a nonempty finite set? $\endgroup$ – bof Nov 2 '13 at 9:11
  • $\begingroup$ isn't this weierstrass theorem? $\endgroup$ – Ant Nov 2 '13 at 13:31
  • $\begingroup$ See also math.stackexchange.com/questions/24996/… $\endgroup$ – Martin Sleziak Feb 13 '15 at 18:32
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – CoffeeIsLife Nov 2 '13 at 21:09
  • 3
    $\begingroup$ 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). $\endgroup$ – Adriano Nov 3 '13 at 1:48
  • $\begingroup$ Are you then implying that a finite set on $\mathbf{R}$ does not always have a maximum and a minimum? $\endgroup$ – CoffeeIsLife Nov 3 '13 at 21:13
  • 7
    $\begingroup$ 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). $\endgroup$ – Adriano Nov 4 '13 at 11:52
  • $\begingroup$ I have a question here: Why the finitude of the set forces the existence of the minimal and maximal elements? $\endgroup$ – Rachel Feb 4 '17 at 19:05
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, but this proves nothing. Besides, proving the statement in the question by induction is the way to go. $\endgroup$ – egreg Feb 1 '19 at 12:59
  • $\begingroup$ Sorry, but induction is actually proved from this theorem, so using it begs the question. $\endgroup$ – xxxx0xxxx Feb 1 '19 at 20:06
  • $\begingroup$ 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. $\endgroup$ – xxxx0xxxx Feb 1 '19 at 20:22
  • $\begingroup$ 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." $\endgroup$ – xxxx0xxxx Feb 1 '19 at 20:49
  • $\begingroup$ 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. $\endgroup$ – egreg Feb 1 '19 at 21:24
-4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How do you know that $m$ and $M$ even exist? This exactly what the question asks. $\endgroup$ – Asaf Karagila Nov 23 '15 at 20:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Nov 30 '15 at 13:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jul 30 '16 at 18:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jul 30 '16 at 18:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jul 30 '16 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.