Well-ordering of the reals

mathboy

Wikipedia states "While we cannot construct a well-order for the set of real numbers R, AC guarantees that such an order exists."

Ok, so the Well-Ordering Theorem states that the reals R can be well-ordered. Yet no one has been able to find a well-ordering for R in 100 years since the Well-Ordering Theorem was proved based on the Axiom of Choice.

I just want to know if mathematicians are still looking for an explicit well-ordering of R right now, or has someone proven that an explicit construction is impossible (despite its existence)?

And what about other uncountable sets? Has it been proven no explicit contructed well-ordering is possible for any uncountable set (that does not already have an explicit well-ordering defined)?

morphism

I believe this is the case - such a construction isn't possible in ZFC. I've either read this somewhere or heard it from someone, but I haven't really looked into it in any detail. Evidently some heavy machinery is required to prove this.

I don't understand what you're saying here. Any countably infinite set can be well-ordered by putting it into bijection with the naturals.

mathboy

I meant uncountable set (the reals being just one case). If an explicit well-ordering of R has been proven to be impossibe in ZFC, then I suppose the same proof applies to the irrationals, the transcendentals, sets of cardinality >= aleph2, etc... ?

morphism

If you look at the very last page in Chapter 1 of Munkres, you can find an explicit construction of an uncountable well-ordered set.

mathboy

You meant the last page of chapter 10 of Munkres. The set A constructed is a well-ordered set having a largest element U such that the section under U is uncountable but every other section is countable. This section is an uncountable well-ordered set, but the construction of A assumes the existence of an uncountable well-ordered set to begin with (p.66 of Munkres).

morphism

Chapter 10 of Munkres is about complex analysis, at least in my copy of the second edition.

I'm talking about exercise 8 in the Supplementary Exercises of Chapter 1. Nowhere in it is the construction of "[itex]S_\Omega[/itex]" being used.

mathboy

Ah, yes. I see it. Thanks.

By the way, I clearly remember reading in some other book "...to date, no one has been able to find an explicit well-ordering of the reals...", which to me sounds like the search is still on, though perhaps someone proved later on that such a search will always be in vain.

morphism

From Wikipedia:

Of course, Wikipedia is not a very reliable source, but it's the only one I can find right now. Maybe someone who knows more about this stuff can chime in.

mathboy

Actually, what I was asking was: given any uncountable set A with some given description (other than having an explicit well-ordering already), is it also impossible to construct a well-ordering for A, just as it is impossible to do so for the reals?

For example, is it also impossible to construct a well-ordering for the set of all continuous functions on [0,1], for the power set of the irrationals, for the set of all bases of the vector space R over Q, etc... Why should R be special?

morphism

That's a good question. I've wondered about it myself, and discovered that the answer is yes, it's impossible to well-order an arbitrary set explicitly (which is the norm whenever the axiom of choice is involved). I also read/heard that it has been proven that such a construction (in ZFC) is impossible for the reals in particular. However if we accept V=L, then Goedel explicitly described a well-ordering for the reals in this case.

But I can't remember where I found this, and I can't find it again -- so it could be that what I'm saying isn't true after all. Set theory isn't really my thing. Again, hopefully someone more knowledgeable will chime in (Hurkyl..?).

mathboy

Perhaps no one here knows the answer because it is still an open problem. Except perhaps for the reals, but not for any arbitrary uncountable set.

Hurkyl

I do not know for sure whether ZF+{reals do not have a well-ordering} is relatively consistent to ZF.

And as you've said, there does not exist any 'algorithm' that takes an arbitrary set and produces a well-ordering. (no matter what you might mean by 'algorithm', as long as it doesn't invoke the axiom of choice)


Alas, I'm not sufficiently familiar with how to construct weird models of set theory, to see if I can find a counterexample.

mathboy

A counterexample to what? We are looking for a theorem that states that given ANY uncountable set (without a well-ordering already constructed), there will never be a way to construct a well-ordering without the axiom of choice. Unless by counterexample you meant that no such theorem exists.

Hurkyl

I would like to construct a specific example of set theory in which certain interesting sets (like the reals) are not well-orderable.

I thought we settled what you said here:
(1) There exist sets we can well-order. So an assertion we can never construct a well-ordering is clearly false.
(2) The axiom of choice is independent of the other axioms in ZF. So, there exist models in ZF where one cannot construct a well-ordering for certain sets.

dankoilik

My post comes 3 months after the discussion, but anyway, the result is proved here:

Feferman, S.: Some applications of the notions of forcing and generic sets. Funda-
menta Mathematicae 56 (1964) 325--345

CRGreathouse

I'm curious about the relative consistency of ZF + "the reals have a well-ordering" + [itex]\neg C.[/itex]

Dragonfall

Isn't [tex]\aleph_1[/tex] a constructible well-ordered (by epsilon) uncountable set?