Let $a,b$ be sets, we write $a\leq^\ast b$ if either $a=\varnothing$ or there exists a surjection $f\colon b\to a$. With the axiom of choice this is a linear ordering equivalent to the usual ordering of cardinals $a\leq b$ if there is an injection from $a$ into $b$).

Without the axiom of choice this order need not be linear, or even a partial order. Indeed there are models where $a < b$ (so trivially $a\leq^\ast b$) but also $b\leq^\ast a$.

Let $\Theta(a)$ denote the least ordinal $\alpha$ such that $\alpha\nleq^\ast a$. This is a dual notion to $\aleph(a)$ which is the least ordinal $\alpha$ such that $\alpha\nleq a$. It is not very hard to see that both these ordinals are in fact cardinals, and that they exist for every set in $\mathrm{ZF}$. In the case where $a=\mathbb R$ we simply write $\Theta$ for $\Theta(\mathbb R)$.

It is consistent that for some set $a$ it holds $\aleph(a)<\Theta(a)$. For example if $V$ is a Solovay model then $\aleph(\mathbb R)=\aleph_1\leq^\ast\mathbb R$.

We also know that if $a\leq^\ast b$ then $a\leq 2^b$, where the injection is simply the sending a point in $a$ to its fiber under a fixed surjection from $b$. It follows, if so, that $\Theta(a)\leq\aleph(2^a)$. Even in $\mathrm{ZFC}$ one can see that it is consistent that there is an equality, and it is consistent that there is no equality (e.g. $a=\omega$ and take a model in which $\frak c=\aleph_1$ and another where it is is $\aleph_2$).

Question: Suppose that $V$ is a model of $\mathrm{ZF+AD}$, we know that if $\alpha\leq^\ast\mathbb R$ then $2^\alpha\leq^\ast\mathbb R$, and therefore $\alpha^+\leq^\ast\mathbb R$. Is it consistent that $\Theta<\aleph(2^\mathbb R)$?

Equivalently, suppose $\alpha<2^\mathbb R$, can we find a surjection from $\mathbb R$ onto $\alpha$?


1 Answer 1


Yes, it is consistent with AD. In $L(\mathbb{R})$, if AD holds then $\Theta$ injects into $\mathcal{P}(\mathbb{R})$, or equivalently, into $2^{\mathbb{R}}$. The OD sets of reals are Wadge-cofinal and $\Theta$ is regular, so we can define an injection $F : \Theta \to \mathcal{P}(\mathbb{R})$ by induction. Let $F(\alpha)$ be the $<_{OD}$-least OD set of reals with Wadge rank greater than the Wadge ranks of all the sets of reals $F(\gamma)$, $\gamma < \alpha$.

Going further, we can determine the Hartogs number $\aleph(2^{\mathbb{R}})$ in all models of $AD + V=L(\mathcal{P}(\mathbb{R}))$. The proof splits into two cases corresponding to the length of the Solovay sequence being a successor ordinal or a limit ordinal.

If the length of the Solovay sequence is a successor ordinal, this means that there is a set of reals $A$ such that every set of reals is OD from $A$ and a real. In this case $\aleph(2^{\mathbb{R}})$ has the largest possible value, namely $\Theta(2^{\mathbb{R}})$. Given a surjection $F : \mathcal{P}(\mathbb{R}) \to Z$ for any set $Z$ we can construct an injection $Z \to \mathcal{P}(\mathbb{R})$. Let $G(z)$ be the set of pairs $(x,y)$ of reals such that $y$ is in the least $OD_{A,x}$ set of reals $B$ with $F(B) = z$ (if it exists.)

On the other hand, if the length of the Solovay sequence is a limit ordinal then $\aleph(2^{\mathbb{R}})$ is equal to $\Theta$; that is, to $\Theta(\mathbb{R})$. We have $\aleph(2^{\mathbb{R}}) \ge \Theta$ on general grounds like you said in the question. But any function $F : \Theta \to \mathcal{P}(\mathbb{R})$ is OD from a set $A$ of reals because $V=L(\mathcal{P}(\mathbb{R}))$, so the range of $F$ consists of $OD_A$ sets of reals. The Solovay sequence has limit length, so the range of $F$ cannot be all of $\mathcal{P}(\mathbb{R})$.

  • 1
    $\begingroup$ Hmm. Thanks. I was hoping for such answer. Is there a known bound on $\aleph(2^\mathbb R)$? Also, this answer is for models of regular $\Theta$, what happens when we have a singular $\Theta$? $\endgroup$
    – Asaf Karagila
    Jul 25, 2012 at 20:15
  • $\begingroup$ I don't know about bounds on $\aleph(2^{\mathbb{R}})$, but the updated answer now shows that if $\Theta$ injects into $\mathcal{P}(\mathbb{R})$ and $V = L(\mathcal{P}(\mathbb{R}))$ then $\Theta$ is regular. $\endgroup$ Jul 25, 2012 at 20:27
  • $\begingroup$ So the atypical case is actually $\Theta=\aleph(2^\mathbb R)$? I have to admit that I am somewhat surprised... $\endgroup$
    – Asaf Karagila
    Jul 25, 2012 at 20:48
  • $\begingroup$ I wouldn't necessarily say the case where the Solovay sequence has limit length is atypical. By the way, I've updated the answer to include a calcuation of the Hartogs number for all cases except when the Solovay sequence has limit length and $V \ne L(\mathcal{P}(\mathbb{R}))$. $\endgroup$ Jul 25, 2012 at 21:24

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.