Is an Explicit Well-Ordering for the Reals Possible?

  • Thread starter mathboy
  • Start date
In summary, Wikipedia states that while a well-ordering for the set of real numbers R cannot be explicitly constructed, the Axiom of Choice guarantees its existence. It has not yet been proven whether an explicit construction is impossible, but it is believed to be the case and would require advanced mathematical machinery. This also applies to other uncountable sets, including the irrationals and transcendentals. However, specific constructions have been made for well-ordering certain sets under certain assumptions, such as V=L. It is also impossible to explicitly construct a well-ordering for an arbitrary uncountable set.
  • #1
mathboy
182
0
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)?
 
Last edited:
Mathematics news on Phys.org
  • #2
mathboy said:
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.
 
  • #3
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... ?
 
Last edited:
  • #4
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.
 
  • #5
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).
 
  • #6
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.
 
  • #7
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.
 
  • #8
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.
 
  • #9
morphism said:
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?
 
Last edited:
  • #10
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..?).
 
  • #11
mathboy said:
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.
 
Last edited:
  • #12
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. :frown:
 
  • #13
Hurkyl said:
Alas, I'm not sufficiently familiar with how to construct weird models of set theory, to see if I can find a counterexample. :frown:

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.
 
Last edited:
  • #14
mathboy said:
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.
 
  • #15
mathboy said:
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
 
  • #16
Hurkyl said:
I do not know for sure whether ZF+{reals do not have a well-ordering} is relatively consistent to ZF.

I'm curious about the relative consistency of ZF + "the reals have a well-ordering" + [itex]\neg C.[/itex]
 
  • #17
Isn't [tex]\aleph_1[/tex] a constructible well-ordered (by epsilon) uncountable set?
 

1. What is the well-ordering principle?

The well-ordering principle states that every non-empty subset of the natural numbers has a smallest element. This means that any collection of natural numbers can be arranged in a specific order, with the smallest number coming first.

2. How does well-ordering apply to the real numbers?

The well-ordering principle can be extended to the real numbers, but it is not as straightforward as it is with the natural numbers. In order to well-order the real numbers, we must use the axiom of choice, which allows us to choose an element from each non-empty subset of the real numbers.

3. What is the importance of the well-ordering of the reals?

The well-ordering of the reals has several important implications in mathematics. It allows us to prove the existence of certain mathematical objects, such as the cardinality of infinite sets. It also has applications in set theory, topology, and analysis.

4. Is the well-ordering of the reals a theorem or an axiom?

The well-ordering of the reals is considered an axiom in mathematics. This means that it is a fundamental assumption that is accepted without proof. However, it can be derived from other axioms, such as the axiom of choice.

5. Are there any limitations to the well-ordering of the reals?

The well-ordering of the reals is a powerful concept, but it does have some limitations. For example, it cannot be used to well-order the complex numbers or other more complex mathematical structures. Additionally, the axiom of choice, which is necessary for the well-ordering of the reals, is a controversial axiom and not accepted by all mathematicians.

Similar threads

Replies
9
Views
318
  • General Math
Replies
6
Views
2K
Replies
2
Views
1K
Replies
6
Views
942
  • Math Proof Training and Practice
3
Replies
80
Views
4K
Replies
33
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
28
Views
5K
  • General Math
Replies
16
Views
2K
  • Quantum Physics
Replies
3
Views
1K
Replies
2
Views
2K
Back
Top