# “Nice” well-orderings of the reals

I have a question which I believe could be easily resolved if I happened to look at the right source - hence my asking it here as opposed to at MathOverflow. I've tried googling it, but I haven't been able to find a satisfactory answer.

Question: is it equiconsistent with reasonable large cardinals that there is a well-ordering of the reals which - as a relation on $\mathbb{R}^2$ - is Lebesgue measurable?

I know that "ZFC + there is a measurable cardinal + there is a $\Delta^1_3$-well ordering of $\mathbb{R}$" is equiconsistent with "ZFC + there is a measurable cardinal," and I know that Projective Determinacy is equiconsistent with reasonable large cardinals, but I don't know whether "ZFC + there is a $\Delta^1_3$-well ordering of $\mathbb{R}$ + PD" is equiconsistent with reasonable large cardinals.

-

No well-ordering of the reals is Lebesgue measurable. This is essentially due to Sierpiński, but one usually finds a weaker version in books (for example, in Rudin's "Real and Complex Analysis"), namely, that if CH holds, then a well-ordering of smallest order type is non-measurable.

The proof is via Fubini's theorem. The argument can be made shorter, but let me go into full detail, as this is a question that appears with some frequency.

Theorem. No well-ordering of a non-null set of reals is Lebesgue measurable. No well-ordering of a non-meager set of reals has the Baire property.

Suppose that $S\subseteq{\mathbb R}$ is a non-null set, that $(r_\alpha\mid\alpha<\lambda)$ is a well-ordered enumeration of $S$, and that $W = \{ (r_\alpha, r_\beta) \mid \alpha<\beta<\lambda\}$. I will argue that $W$ is non-measurable. (The argument below admits dualization, giving the result for the property of Baire.)

By contradiction, suppose there is a least $\lambda$ such that for some $S$, $(r_\alpha\mid\alpha<\lambda)$, and $W$ as above, we have that $W$ is measurable.

For $\alpha\le\lambda$, let $S_\alpha=\{r_\beta\mid\beta<\alpha\}$ and $S^\alpha=\{r_\beta\mid\beta>\alpha\}$. Let $\mu_n$ denote the $n$-dimensional Lebesgue measure (we only use $n=1$ or $n=2$). For $x\in{\mathbb R}$, let $r^{−1}x$ denote the $\alpha<\lambda$ such that $x=r_\alpha$.

Let $\rho\le\lambda$ be first such that $S_\rho$ is non-null. Since $S = S_\lambda$, such $\rho$ exists. Let $W_\rho=W \cap (S_\rho \times S_\rho)$ and, for $\alpha<\rho$ let $T^\alpha=S^\alpha\cap S_\rho$. I will prove that $W_\rho$ is non-measurable, and then use this to show the non-measurability of $W$.

Suppose, then, that $W_\rho$ is measurable. Note that $S_\rho=S_{\alpha+1}\cup T^\alpha$ for any $\alpha<\rho$ and that, by Fubini’s theorem, for almost all $x\in S_\rho$, $T^{r^{−1}x}$ is measurable. It follows that $S_\rho$ itself is measurable.

Then $$0 = \int_{S_\rho}\mu_1(S_{r^{−1}y}) dy$$ and we are done if we can show the outer measure $\mu^*_2$ of $W$ is strictly positive. If it is not, then by the equation above and Fubini’s theorem, $\mu_2(W_\rho) = 0$ and, by applying Fubini’s theorem again, $$\mu_2(W_\rho) =\int_{S_\rho}\mu_1(T^{r^{−1}x}) dx.$$ But for each $\alpha<\rho$, $\mu_1(S_{\alpha+1}) = 0$ and $T^\alpha=S_\rho\setminus S_{\alpha+1}$, so $\mu_1(T^\alpha) > 0$, and the equation last displayed implies $\mu_2(W_\rho) > 0$.

It follows that $W_\rho$ is non-measurable. If $\rho=\lambda$ we are done, so suppose $\rho<\lambda$. Note that $S$ is measurable (arguing as above with $W_\rho$ and $S_\rho$) and $$0 < μ^*_2(W_\rho)\le \mu_2(W) =\int_S \mu_1(S_{r^{−1}y}) dy$$ and by Fubini’s theorem, there must be a $\gamma<\lambda$ such that $S_\gamma$ is non-null and measurable. But then $W_\gamma = W \cap (S_\gamma \times S_\gamma)$ well-orders $S_\gamma$ in order type $\gamma$ and is measurable.

But this contradicts the minimality of $\lambda$, and we are done.

The above is more or less verbatim from my thesis, where I included it as I couldn't find a detailed argument anywhere I looked, but something very close to this ought to be Sierpiński's.

You then go on to ask about compatibility of large cardinals (or their determinacy consequences) with projective well-orderings. This is not possible as determinacy implies Lebesgue measurability (and this goes level by level; in particular, PD implies all projective sets are measurable), but the argument above shows no well-ordering of ${\mathbb R}$ is measurable. (The optimal result in terms of how much determinacy is needed to rule out well-orderings of a given complexity is due to Kechris and is a bit technical to state here.)

It follows, for example, that no well-ordering of ${\mathbb R}$ belongs to $L({\mathbb R})$ under mild large cardinal assumptions, as large cardinals give us determinacy in $L({\mathbb R})$. However, determinacy and large cardinals do not have unlimited influence at higher pointclasses, and it is reasonable to search for (consistent) well-orderings of the reals of nice complexity (necesarily beyond projective) that are compatible with any large cardinals. There is a nice result of Abraham and Shelah accomplishing this: In "A $\Delta^2_2$ well-order of the reals and incompactness of $L(Q^{MM})$", Ann. Pure Appl. Logic 59 (1993), no. 1, 1–32, they prove that one can always force (by small forcing) that CH holds and there is a $\Delta^2_2$ well-ordering of the reals. Actually, $\Sigma^2_1$ is not possible under large cardinals if CH holds, by a nice result of Woodin, so in a sense this is optimal. In their model, $\diamondsuit$ fails, and much works has gone into trying to extend Woodin's result to show that, in particular $\diamondsuit$ should be incompatible with $\Sigma^2_2$ well-orderings.

-
It's great to see your user active here again! :-) – Asaf Karagila Dec 6 '11 at 11:27
Very nice! Thanks for the excellent answer. – user13568 Dec 7 '11 at 19:05