0
$\begingroup$

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?

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

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – favq Feb 16 at 12:00
  • 1
    $\begingroup$ @favq that’s essentially what I did. If you have shown a recursion theorem in your course, you should explicitly appeal to that. “ continuing this way” can be more formalised and your course might demand a more formal approach. $\endgroup$ – Henno Brandsma Feb 16 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.