# Problem

Prove that a set $$R$$ of real numbers is well ordered iff there is no infinite decreasing sequence of numbers $$R$$. In other words, there is no set of numbers $$r_i \in R$$ such that

$$r_0 > r_1 > r_2 > \cdots$$

(Note: the textbook says, verbatim, "iff there is no infinite decreasing sequence of numbers $$R$$", but I'm assuming there is an "in" missing, and it should be "iff there is no infinite decreasing sequence of numbers in $$R$$".)

# Solution

To prove that a set $$R$$ of real numbers is well ordered iff (if and only if) there is no infinite decreasing sequence of numbers in $$R$$, it's necessary to prove both directions of the "if and only if":

1) If a set $$R$$ of real numbers is well ordered, then there is no infinite decreasing sequence of numbers in $$R$$:

Proof. If a set $$R$$ of real numbers is well ordered, then every non-empty subset of $$R$$ has a minimum element.

Therefore, there is no infinite decreasing sequence of numbers in $$R$$, because that would be a subset without a minimum element.

2) If there is no infinite decreasing sequence of numbers in a set $$R$$ of real numbers, then $$R$$ is well ordered:

Proof. If there is no infinite decreasing sequence of numbers in $$R$$, then every sequence of numbers in $$R$$ has a smallest element. Therefore, $$R$$ is well ordered.

Therefore, $$R$$ is well ordered iff there is no infinite decreasing sequence of numbers $$R$$.

Is this proof complete?

• You're giving the same argument twice. It's more subtle in the other direction. You're basically claiming it without proof for 2). – Henno Brandsma Feb 15 at 23:21

One direction is easy: a (strictly) decreasing sequence $$(x_n)$$ defines a subset $$A=\{x_n: n \in \Bbb N\}$$ that has no minimum (because if $$x_n \in A$$ were a minimum, $$x_{n+1} < x_n$$ contradicting the minimality).
The other direction needs a bit more care: If we have any non-empty set $$A$$ without a minimum, then use recursion (plus dependent choice): define $$x_0 \in A$$ as you want (it's non-empty after all). Note that having defined $$x_n$$ for some $$n$$, by assumption it is not $$\min(A)$$ so there is some $$a \in A$$ such that $$a < x_n$$, and then define $$x_{n+1} = a$$ and we continue the recursion. This defines a strictly decreasing sequence in $$A$$ (hence in $$\Bbb R$$) and we have a contradiction. So we have a well-order.
Note that we only use we're in a linear order and nothing specific about $$\Bbb R$$ e.g. This fact holds in all linear orders: well order iff no decreasing sequence (if you believe in dependent choice).
• Thank you. Can you please check if the following proof for direction 2 works better? Proof. Assume that R is not well ordered. So, R has some non-empty subset S that has no smallest element. Then, an infinite decreasing sequence $a_1,a_2,...,a_n,...$ can be built as follows: choose a member of S as $a_1$. Since $a_1$ is not a minimum of S, there is some element in S smaller than $a_1$. So, we can choose $a_2 < a_1$. In the same way, we can choose an $a_3 < a_2$. Continuing this way, an infinite decreasing sequence $a_1 > a_2 > ... > a_n > ...$ can be constructed, which is a contradiction. – favq Feb 16 at 12:00