Hacker News Reader

Comment by pdonis | Hacker News Reader

> The reals can be ordered, just use x < y.

That ordering is not a well-ordering, which is what the GP specified. A well ordering requires that every non-empty subset has a smallest element. That's not true for the reals ordered by x < y: for example, the set of all reals > 0 has no smallest element.

No one has explicitly shown that the reals can be well ordered, but it's a consequence of the axiom of choice that every set can be well-ordered. So in ZFC there must be a well ordering of the reals, even though no one has found one. Issues like this are why not all mathematicians accept the axiom of choice.

View on HN

> no one has found one

More than that: there is no way to build one (assuming the word "build" means some concrete construction), because it's consistent with ZF that the reals admit no well-ordering. Indeed, you can use forcing to construct a model of R in which there is an infinite but Dedekind-finite subset of R; and you can't well-order such a set, because a well-ordering would turn it into an ordinal, and any Dedekind-finite ordinal is finite. You must use some sort of choice principle to construct a well-ordering. (Of course, it's consistent that they can be well-ordered, too, as you say; or e.g. under the hypothesis V=L, where there's even a canonical well-ordering given by the lexicographic well-ordering L comes with.)

Not a mathematician, so this question may be a bit thick. I see the problem with the set of reals > 0, but is it perhaps that in this case > 0 is the problem and for sets specified as >= 0 it's fine because 0 is a nameable real and the smallest element. Obviously you can't just exclude certain expressions arbitrarily though, so I don't know how you could justify that mathematically.

A well ordering on a set is a total order such that all non empty subsets have a minimum element with respect to this order. The standard ordering of the reals is not a well ordering, but the axiom of choice is equivalent to the statement that all sets possess a well-ordering. A well-order of the reals would probably look pretty chaotic though.

We just used the standard ordering < to define the set, it has nothing to do with the candidate well-ordering. If that's confusing, consider the set { 10^-x | x \in N } instead. It also has no minimum element in the standard ordering.

If there is any non-empty subset that has no smallest element, then the ordering in question is not a well-ordering. You can of course define some subsets of the reals that do have a smallest element in the standard ordering, for example all of the reals that are greater than or equal to 0. But there are also subsets that do not have a smallest element, and that is enough to show that the standard ordering on the reals cannot be a well-ordering.

Reply on news.ycombinator.com