6
$\begingroup$

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?

$\endgroup$
4

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
9
  • $\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
    Commented Jun 10, 2016 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$ Commented Jun 10, 2016 at 4:35
  • $\begingroup$ Very clear, thanks much. $\endgroup$
    – user4894
    Commented Jun 10, 2016 at 17:54
  • $\begingroup$ I still think this leaves part of the original question unanswered: Can we prove in ZF that $\mathfrak c=2^{\aleph_0}$? If so, doesn't that imply that $\mathbb R$ must be well ordered in ZF, since it can be put into bijection with an ordinal? $\endgroup$
    – WillG
    Commented Apr 10, 2020 at 21:10
  • $\begingroup$ @WillG Yes, $\mathfrak{c}=2^{\aleph_0}$ is provable in ZF - in fact, that's almost the definition of $\mathfrak{c}$. However, $2^{\aleph_0}$ need not be an ordinal in ZF alone! It may help at this point to look back at the definition of $2^{\aleph_0}$. It's defined as "the cardinality of $\mathcal{P}(\omega)$." But when we're working in ZF, cardinalities need not cardinals, that's the whole point of my answer. So in fact there's no tension here (or incompleteness in the answer). $\endgroup$ Commented Apr 10, 2020 at 21:11
-1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .