Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Well-ordering of reals

  1. Jun 19, 2009 #1
    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?
  2. jcsd
  3. Jun 20, 2009 #2
    The axiom of choice says that such a sequence exists. You may or may not accept that axiom.
  4. Jun 20, 2009 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why would it?

    Do keep in mind that a total order on R does not have to bear much resemblance to the usual order.
  5. Jun 20, 2009 #4
    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.
  6. Jun 20, 2009 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [itex]\omega_1[/itex].

    Now, consider the (uncountable) half-open [itex][0, \omega_1)[/itex] of ordinal numbers. If you choose any ordinal [itex]\alpha[/itex] in this interval, we have:
    * [itex][0, \alpha][/itex] is countable,
    * [itex][\alpha, \omega_1)[/itex] is uncountable.​
    In particular, every Dedekind cut of [itex][0, \omega_1)[/itex] has a countable lower part.
  7. Jun 20, 2009 #6
    Ok, thanks. Had fun trying, now I need to learn some ordinals.
  8. Jun 20, 2009 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Since you're researching it anyways -- it might interest you to look at another counterexample you can create using [itex]\omega_1[/itex]: the long ray.
  9. Jun 22, 2009 #8
    I found an interesting article about smallest uncountable set:

    From there, I understood that it's possible to have uncountable set X for which every [itex]seg(y) = \{x\in X | x < y\}[/itex] 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 [itex]\{x_n\}[/itex] in X that takes up the whole X, i.e. for any x, [itex]x < x_n[/itex] 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 [itex]seg(x_n)[/itex] 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?
  10. Jun 22, 2009 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And since we know [itex]\omega_1[/itex] 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)

    "Real world" is very much in the eye of the beholder. As I mentioned in my previous post, [itex]\omega_1[/itex] 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.
  11. Oct 9, 2011 #10
    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: Feb 6, 2017
  12. Oct 10, 2011 #11


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    For an arbitrary total ordering there is no notion of distance.

    The Axiom of Choice guarantees that any set can be well ordered.
  13. Oct 10, 2011 #12
    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.
  14. Oct 10, 2011 #13
    Try clearing your cookies and starting over. I've never had trouble with this site. I think they had some login issues a couple of weeks ago.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook