Question

Let A be a finite, non-empty subset of R. Prove that A has a maximum and a minimum. (Recall that a maximum of a set A is an upper bound for the set that belongs to A, and a minimum of a set is a lower bound for the set that belongs to the set.) Hint: This result may seem so obvious that it isn't clear h One way is to use induction on the number of elements of the set.

Answer 1

Answer:

Let us use mathematical induction to prove the statement. So, we are going to start checking the statement for the first natural numbers.

$n=1$: Our set is $\{x_1\}$. So, obviously, $x_1$ is the maximum and minimum of our set. Then, the statement is true for $n=1$.

$n=2$: Our set is $\{x_1,x_2\}$. Necessarily, $x_1$ or $x_1>x_2$. In both cases, there is a minimum and a maximum.

Once we have our statement checked for the initial cases, we state our induction hypothesis:

For every finite set A of $n$ elements there exists a maximum and a minimum.

Now, let us prove the that the above assertion is true for sets with $n+1$ elements.

Our set is $A=\{x_1,x_2,\ldots,x_n,x_{n+1}\}$ and we want to find

$\max\{x_1,x_2,\ldots,x_n,x_{n+1}\}$.

Notice that this problem is equivalent to solve

$\max\{\max\{x_1,x_2,\ldots,x_n\},x_{n+1}\}$,

i.e, to find the maximum among $n+1$ numbers, we can find first the miximum among $n$ and then compare with the other one.

Now, using our induction hypothesis we know that there is a maximum in the set $\{x_1,x_2,\ldots,x_n\}$, because it has $n$ elements. Let us write

$x' =\max\{x_1,x_2,\ldots,x_n\}$.

So, in order to find the maximum of A, we have to find the maximum of $\A'={x',x_{n+1}\}$. As we have checked at the beginning, there is a maximum in $A'$, and it is the maximum of A.

Hence, we have completed the prove for the existence of the maximum of a set with $n+1$ elements. The prove for the existence of the minimum is analogue, we just need to change ‘‘maximum’’ for ‘‘minimum’’.