[Math] Use the Well Ordering Principle to prove that every finite, nonempty set of real numbers has a minimum element

inductionorder-theoryproof-verification

This is a textbook problem.

Here's my "proof":

Assume for contradiction there exists a finite, nonempty set of real numbers which doesn't have a least element, call it $C$; suppose there are $n$ elements in $C$, and let's label them in a way such that $c_1\leq c_2\ldots \leq c_n$. Obviously $c_1$ is the least element, contradicting the assumption that $C$ doesn't have a least element. Therefore $C$ is non-existent and we proved the claim.

I didn't explicitly use W.O.P., so I'm not sure if what I did above is correct.

But if I were to explicitly start with W.O.P., I'm stuck on how to expand well-orderedness from the set of natural numbers to finite set of real numbers…any ideas?

Best Answer

The general idea is there, but you should consider exactly what you are proving.

For every $n>0$, if $\{x_i\mid i<n\}$ is a set of real numbers, then it has a minimal element (or minimum, since $\Bbb R$ is linearly ordered).

So to apply the WOP you need to consider the set $$\{n\in\Bbb N\mid\textsf{There exists a non-empty set of reals of size }n\textsf{ without a minimum}\}.$$

If this set is non-empty, take the least $n$ in it, and take $\{x_i\mid i<n\}$ to be a set witnessing that $n$ is in this set of counterexamples. Pick any $i<n$, for example $i=0$, then $\{x_i\mid 0<i<n\}$ is a set of reals of size $<n$. If it is empty, then $n=1$ and $\{x_0\}$ clearly has a minimum; if it is non-empty, then it has to have a minimum (why?), compare it to $x_0$ and arrive at a contradiction.

What you did is not quite good, since you really have to prove that you can label the set of reals as they are ordered, $c_1<\ldots<c_n$. There is no reason that you can do that, unless you proved by induction (which is equivalent to the WOP) that you can do that. In which case your proof is in fact fine.

Related Question