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?


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.

  • $\begingroup$ And if we throw out Choice and Foundation, then we just can't have cardinals as sets? How much should we care? If cardinal numbers are proper classes, does that cause any problems for "working" mathematicians and "naive" set theoreticians, or is it only a concern for advanced work in set theory? $\endgroup$ – bof Jun 10 '16 at 4:33
  • $\begingroup$ @bof If we throw out Choice and Foundation, then it is possible that we won't have cardinals as sets in any nice way; if I recall correctly, this was addressed in a Mathoverflow question a long time ago (EDIT: it was math.stackexchange.com/questions/305859/…, which also kills extensionality a teensy bit via atoms but that's a small price to pay; see also ams.org/mathscinet-getitem?mr=366666). However, we can still express e.g. equinumerosity, so almost nothing changes. $\endgroup$ – Noah Schweber Jun 10 '16 at 4:35
  • $\begingroup$ Very clear, thanks much. $\endgroup$ – user4894 Jun 10 '16 at 17:54

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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