Vtgyjfy

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: as 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?

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.

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.