MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Is the existence of a well-ordering on R independent of ZF?

I am reasonably certain this is the case, but can't find a reference that actually states this, although the Wikipedia article states something close.

-

It is possible to have all the subsets of R be measurable (Solovay, Robert M. (1970). "A model of set-theory in which every set of reals is Lebesgue measurable". Annals of Mathematics. Second Series 92: 1–56.) which implies the nonexistence of a well ordering of R.

-
Alright, so I think I know what the argument should be: a well-ordering of R induces a well-ordering of the Borel algebra, so we can bijectively assign to every r a Borel set B(r) and let S = {r | r \not \in B(r)}). This subset is non-empty because some B(r) is the empty set, and it is clearly non-measurable. Is this correct? – Qiaochu Yuan Nov 11 2009 at 23:18
Well, you should also make it not differ from any Borel by a null set, and for this you need to also simultaneously diagonalize on the null Borel sets. But yeah, that's the idea. – Eric Wofsey Nov 11 2009 at 23:25
One minor quibble is that Solovay's model requires the existence of an inaccessible. This is a minor assumption, but it is unnecessary here. – Richard Dore Nov 12 2009 at 0:05
Richard: you're right, I forgot about that. – Ori Gurel-Gurevich Nov 12 2009 at 0:25
Qiaochu: there's a classical argument for this. Let $X$ and $Y$ be two independent $U[0,1]$ RV. What is the probability that $X<Y$ in the well-ordering? – Ori Gurel-Gurevich Nov 12 2009 at 0:27

Yes. Here's a sketched example:

Start in L. Let P be the forcing which adds ω1 many Cohen reals, and let G be an L-generic filter for P. Then L(ℝ)L[G] will model ZF, but will have no well ordering of the reals. The point is that if σ is an automorphism of P, then σ can be extended to an elementary map from L[G] to L[σ[G]], and this extension will fix L(ℝ)L[G]. So if there was a well ordering of ℝ in L(ℝ)L[G], it would give a well ordering of G which was fixed by σ. But σ can reorder the elements of G because of the homogeneity of P.

-