Well-orderings of $\mathbb R$ without Choice

701 Views Asked by At

The question is about well-ordering $\mathbb R$ in ZF. Without the Axiom of Choice (AC) there exists a set that is not well-ordered. This could occur two ways: a) there are models of ZF in which $\mathbb R$ is well ordered and some other set isn't; or b) there are models in which $\mathbb R$ itself can not be well-ordered. Both possibilities are consistent with ZF.

Do I have this right?

If so then I am confused about the following argument that $\mathbb R$ must be well-ordered even in the absence of choice.

Let $\mathfrak c$ be the cardinality of $\mathbb R$. It's easy to show that $\mathfrak c = 2^{\aleph_0}$.

Now (this is the part that's got me confused) in set theory cardinals are defined as certain ordinals. Therefore $\mathfrak c$ is some ordinal; which immediately induces a well-order on $\mathbb R$.

What is wrong with this argument? I can imagine a couple of scenarios but without much confidence.

  • $\mathfrak c$ is a cardinal but it is possible that it's not well-ordered. But if it's a cardinal that's not an ordinal, then what is it? This scenario seems unlikely.

  • Or perhaps $\mathfrak c$ is not always well-defined. When people say, "Let $\mathfrak c$ be the cardinality of $\mathbb R$," they typically neglect to prove that such a thing exists. Perhaps there are models of ZF in which $\mathbb R$ has no well-defined cardinality at all. This seems like the only sensible way out, in which case there are a lot of misleading expositions out there.

I found several Stackexchange questions about properties of well-orderings of $\mathbb R$ under AC; but nothing about this particular question. According to this article the reals might not be well-ordered in Solovay's model in which all sets of reals are Lebesgue-measurable; but this requires an inaccessible cardinal. What happens if we take the inaccessible away?

In general what is the correct way to understand well-ordering the reals in ZF?

2

There are 2 best solutions below

9
On BEST ANSWER

Tl;dr: the cardinality of a set need not be a cardinal. Yes, this is terrible terminology.

The former possibility is what happens if $\mathbb{R}$ is not well-orderable. $\mathfrak{c}$ is always well-defined; it's just that, in the absence of choice, it need not be an ordinal.


Note that this means that we need to be careful with our terminology when working in just $ZF$: we need to distinguish between cardinals in the sense of initial ordinals (equivalently, cardinalities of well-orderable sets) and cardinalities in general.

For that matter, we need to be a little careful how we define a possibly-non-well-orderable cardinality! We use the notion of rank. The rank of a set is defined in terms of the cumulative hierarchy. We define $V_\theta$, for every ordinal $\theta$, inductively as follows:

  • $V_0=\emptyset$,

  • $V_\lambda=\bigcup_{\beta<\lambda} V_\beta$ for $\lambda$ limit, and

  • $V_{\alpha+1}=\mathcal{P}(V_\alpha)$.

Then by the Axiom of Foundation, we can show that for all $A$ there is some $\theta$ such that $A\in V_\theta$. The least such $\theta$ is the rank of $A$. Moreover, each $V_\theta$ is a set.

If $X$ is a non-well-orderable set, then we let $\vert X\vert$ be the set of all sets $Y$ such that $(i)$ $Y$ is in bijection with $X$, and $(ii)$ the rank of $Y$ is as small as possible (no set of strictly smaller rank is in bijection with $X$).

That is, we take a Fregean approach - a cardinality is a set of all sets of a given size - but use the notion of rank to make the result a set, instead of a proper class (this is called Scott's trick).

Note that, however, this clashes slightly with the definition of the cardinality of a well-orderable set; but this doesn't really cause any problems.


By the way, I think Solovay's model is a bit of a red herring, here. The most straightforward way to break the well-orderability of $\mathbb{R}$ is Cohen's original model; Jech's big book has a good exposition of it. This does require forcing, though, so is a serious chunk of work to get through.

0
On

According to the Wikipedia article Cardinal number, in ZFC, the cardinality of any set is defined to be the smallest ordinal number that is equivalent to that set, that is, there is a bijection from that ordinal number to that set. That's probably because in ZFC, it can be proven that for all sets, there is a smallest ordinal number that is equivalent to that set. The problem with your proof that the set of all real numbers can be well ordered is that you need the axiom of choice to prove that the cardinality of all sets can be defined in that way and therefore that $\mathfrak c$ is an ordinal number according to that definition.