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

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<x_2` 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’’.