Prove by induction that every finite nonempty set of reals has a minimum.

discrete mathematicsinductionsolution-verification

Exercise on Mathematical Induction is from Mathematics for Computer Science by Albert R. Meyer, Eric Lehman, and Frank Thomson Leighton. It says,

Prove by induction that every nonempty finite set of real numbers has a minimum element.

I rephrased it in the following way to make induction variable explicit.

Let $S_n$ denote the set of $n$ real numbers.
   Theorem: Every nonempty $S_n$ has a smallest element.
Proof. By ordinary induction. Let induction hypothesis $P(n)::=$ in any set $S_n$, containing $n$ real numbers, $\exists m \in S_n: \forall s \in S_n: m \leq s$. Prove $P(n)$ holds for all $n \geq 1$.
 Base case ($n=1$): $P(1)$ is obviously true. If we choose $m$ to be that single element of $S_n$, then it's simply less than or equal to itself. Therefore, $P(1)$ holds.
  Inductive step: Suppose $P(n)$ holds for some $n \geq 1$. Show that $P(n) \Rightarrow P(n+1)$.
   Since $P(n)$ holds, we can conclude there exists $m \in S_n$ such that $\forall s \in S_n: m \leq s$. Since $P(n)$ holds for any set containing $n$ real numbers, it must be hold for the first $n$ elements of $S_n$. That is, there exists an element $m$ smaller than all of the first $n$ elements. We just need to compare $m$ to the (n+1)th element of $S_{n+1}$ and take the minimum of these two as new $m$, which proves $P(n+1)$.
  We can conclude by induction principle $p(n)$ holds for all $n \in N$.

Note: $N::= \{1,2,…\}$
 I've doubt on the proof and structure of this induction proof. I know its inductive part is a bit wordy. I didn't use set notations to write, instead tried to explain it in this way. Is this way of proving acceptable? I appreciate your answers.

Best Answer

There are several problems.

  1. “Let $S_n$ denote the set of $n$ real numbers.” It makes no sense, since there are infinitely many such sets.
  2. “Theorem: Every nonempty $S_n$ has a smallest element.” The statement should be that every finite and non-empty set of real numbers has a smallest element.
  3. You write as if you were working on one set $S_n$ with $n$ elements and one set $S_{n+1}$ with $n+1$ elements. You can do it as follows: let $S$ be a set with $n+1$ elements. Take $m\in S$. If $m$ is the smallest element of $S$, you're done. otherwise, let $S'=S\setminus\{m\}$. The $S'$ has $n$ elements and therefore, by the induction hypothesis, it has a smallest element $m'$. Since $m$ is not the smallest element of $S$, $m'\leqslant m$ and, for each $k\in S'$, $m'\leqslant k$. Therefore, $m'$ is the smallest element of $S$.
Related Question