# Well-ordering of reals

If < is any total order in R, isn't it always possible to construct an infinite sequence
x1 > x2 > x3 > ... > y for some limit point y in R.

It seems to me that {x1, x2, x3, ...} is then a subset of R that does not have
least element in this ordering. No total order in R can be well-order?

Related Set Theory, Logic, Probability, Statistics News on Phys.org
The axiom of choice says that such a sequence exists. You may or may not accept that axiom.

Hurkyl
Staff Emeritus
Gold Member
If < is any total order in R, isn't it always possible to construct an infinite sequence
x1 > x2 > x3 > ... > y for some limit point y in R.
Why would it?

Do keep in mind that a total order on R does not have to bear much resemblance to the usual order.

Why would it?

Do keep in mind that a total order on R does not have to bear much resemblance to the usual order.
It's just an intuition of that uncountable set is necessarily kind of dense for any order, not just the common order.

I had in mind two assumptions which seem quite natural:
1. Uncountable set of reals must have uncountable interval (a,b) for any order <.
2. It's always possible to split uncountable interval into two parts, both uncountable.

Then what follows, we can split (a,b) into two parts, select x1 from the upper part. Then split lower part again into two parts, select x2 from the new upper part, and so on. This way should be formed a sequence {x1, x2, ...} where x1 > x2 > ... for the order <, and the sequence does not have a least element.

I'm just developing the idea, but if this is already flawed, I would appreciate any point.

Hurkyl
Staff Emeritus
Gold Member
2. It's always possible to split uncountable interval into two parts, both uncountable.
This is demonstratably false, by a rather slick argument. It depends on two facts:

(1) The class of all ordinal numbers is well-ordered
(2) There exists an uncountable ordinal

Therefore, there exists a smallest uncountable ordinal number; let's call it $\omega_1$.

Now, consider the (uncountable) half-open $[0, \omega_1)$ of ordinal numbers. If you choose any ordinal $\alpha$ in this interval, we have:
* $[0, \alpha]$ is countable,
* $[\alpha, \omega_1)$ is uncountable.​
In particular, every Dedekind cut of $[0, \omega_1)$ has a countable lower part.

Ok, thanks. Had fun trying, now I need to learn some ordinals.

Hurkyl
Staff Emeritus
Gold Member
Since you're researching it anyways -- it might interest you to look at another counterexample you can create using $\omega_1$: the long ray.

Therefore, there exists a smallest uncountable ordinal number; let's call it $\omega_1$.
I found an interesting article about smallest uncountable set:
http://www.math.fsu.edu/~bellenot/class/su08/found/other/omega-one.pdf

From there, I understood that it's possible to have uncountable set X for which every $seg(y) = \{x\in X | x < y\}$ is countable. This is exactly against an idea I had for proving my second assumption (yes it hurts, but I don't care).

But why is it impossible to have a sequence $\{x_n\}$ in X that takes up the whole X, i.e. for any x, $x < x_n$ for large enough n?

Existence of such a sequence seems almost obvious to me, and this would be enough to prove X as union of $seg(x_n)$ countable. Or is it just that because of initial assumptions, we must deny this kind of sequences. Do you happen to know any "real-world" example where any sequence cannot take the whole set?

Hurkyl
Staff Emeritus
Gold Member
But why is it impossible to have a sequence $\{x_n\}$ in X that takes up the whole X, i.e. for any x, $x < x_n$ for large enough n?
...
Existence of such a sequence seems almost obvious to me, and this would be enough to prove X as union of $seg(x_n)$ countable.
And since we know $\omega_1$ isn't countable, that tells you why it's impossible.

If this seems obvious to you, that just means your intuition isn't equipped to deal with orders of uncountable cofinality. ("cofinality" measures this quality of orders)

Do you happen to know any "real-world" example where any sequence cannot take the whole set?
"Real world" is very much in the eye of the beholder. As I mentioned in my previous post, $\omega_1$ can be used to construct counterexamples, such as the long ray -- which tells geometers if they want to study more "normal"-looking spaces, they need to require that manifolds aren't merely Hausdorff and locally Euclidean... one must also insist on second countability.

I've personally explicitly used uncountable ordinals in proofs because my preferred method of applying the axiom of choice is to use the well-ordering theorem along with transfinite iteration1.

I've also explicitly used them to help understand nonstandard analysis. (In particular, to understand just how ugly the hyperreals look when studied externally)

1: This refers to a form of transfinite induction that I find particularly natural, but I don't think it's a standard term.

This is the most messed up forum I've ever seen. It kept going round and round saying I wasn't logged in and then it said I was. I wrote my proof that the reals can't be well ordered and went to post it and then it said I wasn't logged in and erased it.
Whenever I write a long post for ANY online forum, I always Select All and Copy it before I hit Submit. That's because every website has occasional hiccups and sometimes your browser loses your text. It happens often enough that if I write something long or complicated enough, I'll make sure to save it in my Copy buffer just in case.

I actually picked up this good habit on the Craigslist forums, which used to have a fairly high frequency of these types of errors.

In any event, you should first convince yourself that you can prove that the existence of a well-ordering of the reals is equivalent to the Axiom of Choice. If you can then prove that no well-order exists, then a) If you assumed the negation of AC you have re-proven a known result; or b) If you assumed AC, you have discovered an inconsistency in mathematics and you will become famous.

So if you really have a proof, it's worth cleaning it up and posting it again. Not so much because I believe you've discovered an inconsistency in set theory; but because the effort to re-write and think through the math will help you learn more about the subject.

Over the years I always find that whenever I write something and the computer eats it, it comes out much better when I rewrite it.

Last edited by a moderator:
• berkeman
lavinia
Gold Member
If < is any total order in R, isn't it always possible to construct an infinite sequence
x1 > x2 > x3 > ... > y for some limit point y in R.
For an arbitrary total ordering there is no notion of distance.

It seems to me that {x1, x2, x3, ...} is then a subset of R that does not have
least element in this ordering. No total order in R can be well-order?
The Axiom of Choice guarantees that any set can be well ordered.

I'll have to retract what I said. If <* well orders R then each subset of R has a least element with respect to <*. I was thinking of a nonempty set {x: a<*x<*b} or {x:a<*x} with respect to <*. This should be a valid subset of R with no least element. But such a set by assumption should contain a least element, L ≠ to a, but there appears to be no way to prove there are numbers in this set between a and L with respect to <*. The fact that I can write such a set suggests that it exists and has no least element with respect to <*. The conclusion is If W.O. is correct there does exists an ordering <* such that there is no S subset of R such that
{x: xεS, a<*x<*b} or interval (a,b) with respect to <* exists.

I was going to add more, but this thing keeps telling me I'm not logged in.

I'll have to retract what I said. If <* well orders R then each subset of R has a least element with respect to <*. I was thinking of a nonempty set {x: a<*x<*b} or {x:a<*x} with respect to <*. This should be a valid subset of R with no least element. But such a set by assumption should contain a least element, L ≠ to a, but there appears to be no way to prove there are numbers in this set between a and L with respect to <*. The fact that I can write such a set suggests that it exists and has no least element with respect to <*. The conclusion is If W.O. is correct there does exists an ordering <* such that there is no S subset of R such that
{x: xεS, a<*x<*b} or interval (a,b) with respect to <* exists.

I was going to add more, but this thing keeps telling me I'm not logged in.