## Well-ordering of the reals

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

Recognitions:
Homework Help
 Quote by mathboy has someone proven that an explicit construction is impossible (despite its existence)?
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.

 And what about other infinite sets? Has it been proven no explicit contructed well-ordering is possible for any infinite set (that does not already have an explicit well-ordering defined)?
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.
 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... ?

Recognitions:
Homework Help

## Well-ordering of the reals

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.
 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).
 Recognitions: Homework Help Science Advisor 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 "$S_\Omega$" being used.
 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.

Recognitions:
Homework Help
From Wikipedia:

 The standard ordering ≤ of the positive real numbers is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. From the ZFC axioms of set theory (including the axiom of choice) one can show that there is a well-order of the reals; it is also possible to show that the ZFC axioms alone are not sufficient to prove the existence of a definable (by a formula) well-order of the reals. However it is consistent with ZFC that a definable well-ordering of the reals exists—for example, it is consistent with ZFC that V=L, and it follows from ZFC+V=L that a particular formula well-orders the reals, or indeed any set.
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.

 Quote by 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.
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?
 Recognitions: Homework Help Science Advisor 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..?).

 Quote by 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?
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.
 Recognitions: Gold Member Science Advisor Staff Emeritus 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.

 Quote by Hurkyl Alas, I'm not sufficiently familiar with how to construct weird models of set theory, to see if I can find a counterexample.
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.

Recognitions:
Gold Member
Staff Emeritus
 Quote by 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.
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.

 Quote by mathboy 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)?
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

Recognitions:
Homework Help
I'm curious about the relative consistency of ZF + "the reals have a well-ordering" + $\neg C.$
 Isn't $$\aleph_1$$ a constructible well-ordered (by epsilon) uncountable set?