Well-ordering the reals: a response

This is a reply to Jay’s comment.

First, I should mention that in the absence of AC, the real numbers may not be well-orderable at all. In the Solovay model of ZF in which every set of reals is Lebesgue-measurable, for instance, the reals cannot be well-ordered, since one can construct from a well-ordering of the reals a non-measurable set of reals (by choosing a transversal of \mathbb{R}/\mathbb{Q}. Exercise!).

There are at least two interpretations of ‘explicit’ in this context. I’ll address the two that seem most natural to me: Borel/projective and definable (by a first-order formula).

The Axiom of Constructibility says that V=L, or that every set is constructible. (The class V is the class of all sets, and L is the class of all constructible sets.) The axiom might seem appealing to the non-set-theorist, since it implies the Axiom of Choice and the (Generalized even, I think) Continuum Hypothesis. In fact, this is how Gödel originally proved the relative consistency of AC: by showing that AC holds in L, which is a model of ZF. It’s also important to realize that L is the smallest inner model of ZF (that is, in a model V of ZF, V‘s L is the smallest model of ZF inside V): it contains only those sets which must exist because they’re forced to by the axioms (maybe something like the trivial group for the axioms of group theory). But assuming V = L makes for a pretty uninteresting (limited, at least) set theory, and it’s therefore generally unappealing to set theorists. I would compare the restriction of set theory to ZF + (V=L) to the restriction of group theory to abelian group theory: the latter would make group theory (mostly) uninteresting and eliminate many tools useful to the non-group-theorist. It’s still useful to consider, though, especially for consistency business.

Aside: So, some Grothendieckian algebraic geometry depends on one or more large cardinal axioms, which are almost certainly inconsistent with V = L. (Edit: I think algebraic geometers need only assume something like There is a proper class of inaccessibles, which is considerably milder than what V=L forbids.)

So the point of telling you about L was to tell you this: if V=L, then the whole set-theoretic universe is well-ordered, so \mathbb{R} (and every other set) inherits a well-ordering from the universe. One might hope for a Borel well-ordering of \mathbb{R} (Borel as a subset of \mathbb{R}^2, of course). I’m fairly certain that this is impossible (and that shouldn’t be hard to see, but I don’t see it right now). There are broader families of ‘explicit’ sets of \mathbb{R}, though; what we’re interested in is the projective hierarchy, described here. The punchline is that under the assumption V=L, there is a well-ordering of the reals of complexity \mathbf{\Delta}^1_2; essentially, this means that, for some analytic set X in \mathbb{R}^3, the well-ordering is the complement of X projected down to \mathbb{R}^2. (Analytic means the continuous image of a Borel set.) So that’s fairly explicit, right? There have been other attempts at finding projectively uncomplicated well-orderings of the reals; see this answer to an MO question. But that’s under the assumption V=L. Under certain large cardinal assumptions, the lower bound for the complexity of a well-ordering of \mathbb{R} is higher than \mathbf{\Delta}^1_2.

The other natural interpretation of ‘explicit’ is ‘definable’. Your question then becomes something like, Is there some formula \phi such that the set \{ x : \phi(x) \} is a well-ordering of the reals? And the answer is that this is independent of ZFC+GCH. (And your question in this form is similar to this MO question. You’ll notice that I provide a link in my comment on that page to a paper by Feferman, in which he proves this independence.)

I think all this is accurate; I hope it’s helpful.

Aside | This entry was posted in Logic. Bookmark the permalink.

2 Responses to Well-ordering the reals: a response

  1. JCummings says:

    Interesting stuff. Confusing to me, but interesting. I do like the constructibility question and hope that all sets are constructible (sorry). I’d have to think about the projective business for awhile longer to understand it. One question that I do have: What do you mean by the existence of a formula \phi which is a well-ordering of the reals? Do you mean formula in a way that differs from function? If a well-ordering exists, isn’t there implicitly a function which does it? With choice, probably. I thought that any sort of process can be described with a function that maps where it starts out to where everything ends up.

  2. Z Norwood says:

    What do you mean, you “hope that all sets are constructible”?

    A formula like \phi(x,y) iff x=y. This defines the diagonal line that is the graph of the function f\colon x \mapsto x. Not every set is necessarily definable, though. Definability depends on the (formal) language you’re using, too; for instance, you won’t get very far trying to define subsets of \mathbb{R} using only (regular logical connectives and) the symbol 1. If you add the symbols +, \cdot, <, though, you can define quite a lot.

    So when I said 'definable' up there, I meant 'definable in the language of set theory', which includes the symbol \in.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s