Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Why are we interested in definable wellordering of the reals? For instance, we have

  1. Con(ZFC) $\Rightarrow$ Con(ZFC + there is a $\Delta^1_2$-wellordering of $\mathbb{R}$),
  2. Con(ZFC + there is a measurable cardinal) $\Rightarrow$ Con(ZFC + there is a measurable cardinal+there is a $\Delta^1_3$-wellordering of $\mathbb{R}$).
share|improve this question
add comment

2 Answers

Several objects can be defined from a wellordering of the reals. Nonprincipal ultrafilters on the natural numbers, non-measurable sets of reals, sets of reals without the property of Baire, and so on.

Knowing how complicated wellorderings of the reals are tells us how complicated these objects are.

On the other hand, knowing the minimal complexity of a wellordering of the reals tells us something about the universe of set theory we are living in. In $L$, Goedel's constructible universe, there is a wellordering of the reals of minimal complexity, namely $\Delta^1_2$.
Assuming more and more large cardinals, we have more and regularity properties for projective sets of reals, and since a wellordering of the reals can be used to construct pathological sets of reals (as above), large cardinals imply that there is no easily definable wellordering of the reals. For example, a measurable cardinal implies that there is no $\Delta^1_2$ wellordering, but is consistent with a $\Delta^1_3$ wellordering of the reals.

So in some sense, the minimal complexity of a wellordering of the reals in a given universe of set theory is a test question to gauge the pathologies that definable sets of reals can exhibit in this universe.

share|improve this answer
add comment

This is a very interesting topic! There are two ways to address the question. They are different, so I treat them separately.


As mentioned by Stefan, knowing that we have a well-ordering of certain complexity gives us a bound on the extent of regularity properties.

For example, the complexity of well-orderings gives us an upper bound on the complexity of pointclasses for which determinacy holds. Abstractly, determinacy of nice pointclasses implies that their members are Lebesgue measurable, etc, so it provides us with a precise framework to talk about "regularity" of sets of reals.

Moreover, in the context of fine structural inner models, the complexity of a well-ordering is really a reflection of the complexity of the underlying "comparison process" used to build the model. We are interested in this complexity as it gives us an upper bound on the kind of reals we can expect to see in these models.

To be more concrete, think of $L$ and its well-ordering: We say that $x\lt y$ (for $x,y$ reals), iff either $x$ appears first (i.e., there is an $\alpha$ such that $x\in L_\alpha$ but $y\notin L_\alpha$), or they appear at the same time, but $x$ is "simpler" (measured by, say, an ordering of formulas and parameters). This ordering is $\Sigma^1_2$ because the models $L_\alpha$ are simple to code by reals, essentially all we say is that $r$ codes a model $(A,E)$ and $E$ is well-founded.

When we go from $L$ to, say $L[\mu]$, it is more complicated to compare the levels where $x$ and $y$ appear. Now we have two set models $L_\alpha[U_1]$ and $L_\beta[U_2]$ and we iterate their respective measures until we reach a model and one of its initial segments. The complexity of describing this is greater than in the case of $L$, as now we need to talk about well-foundedness of the iteration as well as of the relevant models. This complexity increases with the models under consideration, as the iterations become more and more complex (iteration trees).

A good discussion of these ideas can be seen in the paper by Martin and Steel, "Iteration trees." J. Amer. Math. Soc. 7 (1994), no. 1, 1–73. It is also treated at a higher level in Steel's Handbook article.

The reason why the complexity of iterations bounds the complexity of the reals we can obtain is a folklore result in inner model theory. Rather than stating the technical fact, let me illustrate with an example: We can identify the real $0^\sharp$ with a model $(L_\alpha,U)$. This model is countable, and pointwise definable. This translates without much effort in the fact that if $y$ is a real in $L$, then $y\le_T 0^\sharp$, where $\le_T$ is the Turing-reducibility order (essentially, because in fact $y\in L_\alpha$). Hence, if a real is more complex (in the Turing sense) than $0^\sharp$, it cannot be in $L$. It also shows that (if $0^\sharp$ exists) then ${\mathbb R}\cap L$ is countable.

$0^\sharp$ is an example of what we call mice. In a sense, the more complex the mouse, the more reals it contains. If a mouse $m$ is so complex that it contains all reals of certain complexity $\Gamma$, and if the comparison process for a fine-structural model $M$ can be coded in $\Gamma$, then we have a concrete example (namely, $m$) for a real not in $M$ and, in fact, we get that all reals in $M$ are Turing reducible to $m$.

(The ultimate expression of these ideas is the so-called mouse set conjecture, but it would take us far off topic to discuss it here properly.)


There is another reason for being interested in simple well-orderings. This reason appears in practice, and is not guided by fine-structural considerations or by trying to limit the extent of regularity properties.

Typically we are interested in strengthenings of the axioms of set theory by axioms that provide us with "combinatorial tools." Examples of the principles I have in mind include forcing axioms (Martin's Axiom, BPFA, MM, ...), the covering property axiom, real-valued measurability of some cardinal $\kappa\le{\mathfrak c}$, etc.

The combinatorial niceness that these axioms provide usually is a hindrance when it comes to defining well-orderings in simple ways. The reason is that typical coding tools we would use in such a definition are ruled out by the combinatorial principles. I present several examples of this in my paper "Real-valued measurable cardinals and well-orderings of the reals," available at this link, in a section titled "Anticoding results".

It is therefore an interesting technical problem to see whether we can circumvent these obstacles and still obtain (consistent) simple well-orderings. Usually we are not so interested in well-orderings per se, but rather in the possibility of developing coding tools. Typically, we can code arbitrary sets of reals just as well as we can code well-orderings (this, in turn, can be seen as an anti-compactness result).

This line of work, in the context of Martin's axiom, was started by Solovay, and developed by Abraham and Shelah in a nice series of papers:

  • "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.
  • "Martin's axiom and $\Delta^2_1$ well-ordering of the reals." Arch. Math. Logic 35 (1996), no. 5-6, 287–298.
  • "Coding with ladders a well ordering of the reals." J. Symbolic Logic 67 (2002), no. 2, 579–597.

(I particularly recommend the introduction to the first paper in the series.)

I have worked on this problem of coding in the context of forcing axioms, and the surprise here is that strong forcing axioms actually provide us with simple definitions of well-orderings (not just consistently). For example:

  • Sy Friedman and I showed that if BPFA holds and, say, $\omega_1=\omega_1^L$, then there is a $\Sigma^1_3$ well-ordering.
  • Velickovic and I showed that if BPFA holds and $C$ is a ladder sequence on $\omega_1$, then there is a $\Delta_1$ well-ordering of the reals in parameter $C$.

The context here differs from that of the first part of the answer in several ways. For example, we tend not to be interested in projective well-orderings any longer, as decent forcing axioms imply AD${}^{L({\mathbb R})}$ and therefore prevent the existence of such orderings. Also, although we may (and do) ask about third-order definable well-orderings, we are actually more interested in definability over $H(\omega_2)$, as we expect to define not just a well-ordering of the reals but of all of ${\mathcal P}(\omega_1)$.

share|improve this answer
add comment

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.