# Is there a known well ordering of the reals?

So, from what I understand, the axiom of choice is equivalent to the claim that every set can be well ordered. A set is well ordered by a relation, $$R$$ , if every subset has a least element. My question is: Has anyone constructed a well ordering on the reals?

First, I was going to ask this question about the rationals, but then I realised that if you pick your favourite bijection between rationals and the integers, this determines a well ordering on the rationals through the natural well order on $$\mathbb{Z}$$ . So it's not the denseness of the reals that makes it hard to well order them. So is it just the size of $$\mathbb{R}$$ that makes it difficult to find a well order for it? Why should that be?

To reiterate:

• Is there a known well order on the Reals?
• If there is, does a similar construction work for larger cardinalities?
• Is there a largest cardinality for which the construction works?
• You read XKCD don't you?
– BCS
Oct 11, 2010 at 15:30
• @BCS yes, but I only saw todays in this question: math.stackexchange.com/questions/6489/… and in fact, the question I asked has been bugging me for some time. Oct 11, 2010 at 15:37
• Goedel explicitly constructed a subset of the reals and a well order on the subset such that (in ZF) it is consistent that the subset is all reals. But subsequently Cohen showed it is also consistent that the subset if NOT all reals. May 18, 2011 at 19:33
• @AsafKaragila I have added the tags (axiom-of-choice) (since I think that this is definitely related) and (order-theory) (since we do not have a separate tag for well-orders and this seems to me the closest one.) But since I see that you have previously removed this tag I pinged you. If needed, we can discuss this further in chat. May 8, 2016 at 5:44
• I presume "integers" (and Z) should be "naturals" (and N). I'm not sure what would be the "natural well order on Z". Oct 4, 2023 at 2:54

I assume you know the general theorem that, using the axiom of choice, every set can be well ordered. Given that, I think you're asking how hard it is to actually define the well ordering. This is a natural question but it turns out that the answer may be unsatisfying.

First, of course, without the axiom of choice it's consistent with ZF set theory that there is no well ordering of the reals. So you can't just write down a formula of set theory akin to the quadratic formula that will "obviously" define a well ordering. Any formula that does define a well-ordering of the reals is going to require a nontrivial proof to verify that it's correct.

However, there is not even a formula that unequivocally defines a well ordering of the reals in ZFC.

• The theorem of "Borel determinacy" implies that there is no well ordering of the reals whose graph is a Borel set. This is provable in ZFC. The stronger hypothesis of "projective determinacy" implies there is no well ordering of the reals definable by a formula in the projective hierarchy. This is consistent with ZFC but not provable in ZFC.

• Worse, it's even consistent with ZFC that no formula in the language of set theory defines a well ordering of the reals (even though one exists). That is, there is a model of ZFC in which no formula defines a well ordering of the reals.

A set theorist could tell you more about these results. They are in the set theoretic literature but not in the undergraduate literature.

Here is a positive result. If you work in $L$ (that is, you assume the axiom of constructibility) then a specific formula is known that defines a well ordering of the reals in that context. However, the axiom of constructibility is not provable in ZFC (although it is consistent with ZFC), and the formula in question does not define a well ordering of the reals in arbitrary models of ZFC.

A second positive result, for relative definability. By looking at the standard proof of the well ordering principle (Zermelo's proof), we see that there is a single formula $\phi(x,y,z)$ in the language of set theory such that if we have any choice function $F$ on the powerset of the reals then the formula $\psi(x,y) = \phi(x,y,F)$ defines a well ordering of the reals, in any model of ZF that happens to have such a choice function. Informally, this says that the reason the usual proof can't explicitly construct a well ordering is because we can't explicitly construct the choice function that the proof takes as an input.

• I think you can actually prove in an extension of ZF such as MK that ZF doesn't name a define a well-ordering on R. It might be worth including that in your answer. Aug 18, 2018 at 2:56
• @Timothy Do you have a reference for that? I'm fairly sure this is wrong - suppose there is a model with an inaccessible cardinal $\kappa$. Passing to this model's $L$ if necessary, we may assume the model satisfies $V=L$. Then there is a $\Delta^1_2$-definable well-ordering of $\mathbb R$ (see here), and it still works if we pass to $V_{\kappa+1}$, which is a model of MK. Jan 20, 2019 at 14:35
• What's the formula that well-orders the reals in L? May 24, 2020 at 19:59

No, it's not just the size. One can constructively prove the existence of large well-ordered sets, but for example even when one has the first uncountable ordinal in hand, one can't show that it is in bijection with $$\mathbb{R}$$ without the continuum hypothesis.

All the difficulty in the problem has to do with what you mean by "constructed." If one has a well-ordering on $$\mathbb{R}$$ then it is possible to carry out the construction of a Vitali set, which is a non-measurable subset of $$[0, 1]$$. And it is known that the existence of non-measurable subsets of $$\mathbb{R}$$ is independent of ZF. In other words, it is impossible to write down a well-ordering of $$\mathbb{R}$$ in ZF.

On the other hand given AC one can obviously write down a well-ordering in a non-constructive way (choose the first element, then the second element, then...). This is probably not what you meant by "construct," though.

• A quibble: "constructively prove" can connote systems that have various properties favored by constructivists. ZF set theory is not what is usually considered a constructive system, with or without the axiom of choice. Oct 11, 2010 at 11:52
• Does this mean we cannot determine which of some pairs of real numbers is the larger/smaller of the pair? Jan 10, 2020 at 20:43
• @matanster: It's the other way around: no formula can be proven (without additional axioms) to define a well-ordering of reals. Dec 5, 2020 at 20:26