Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Thanks in advance!

share|cite|improve this question
up vote 11 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.