# For an infinite cardinal $\kappa$, $\aleph_0 \leq 2^{2^\kappa}$

I'm trying to do a past paper question which states: $$\text{For all infinite cardinals \kappa, we have } \aleph_0 \leq 2^{2^\kappa}.$$ I'm supposed to be able to do this without the axiom of choice, but I can't see how. I know that there can be no bijection (or surjection) from any natural number with $X$, where $|X| = \kappa$, but I can't get any further.

A solution or hint would be great, thanks!

EDIT: Something that bugs me about this question is that they've written $\aleph_0 \leq 2^{2^\kappa}$, whereas the solution below using Cantor's theorem shows that $\aleph_0 < 2^{2^\kappa}$, that is strict inequality holds. Is this just a mistake, or to throw people off?

• According to the definition I have, $\kappa$ is finite if there is a bijection $f:n \to X$ for $|X| = \kappa$, and some $n \in \omega$, otherwise $\kappa$ is infinite? – CameronJWhitehead May 24 '15 at 14:31
• If you are not assuming the axiom of choice then there are a few different possible inequivalent definitions of "cardinal". Can you be precise about how it is defined here? – Nate Eldredge May 24 '15 at 15:23
• @Nate: Only one definition of cardinal makes sense when exponentiation is involved, if the axiom of choice is not assumed. (HINT: The axiom of choice is equivalent to saying that for every ordinal $\alpha$, $2^\alpha$ can be well-ordered.) – Asaf Karagila May 24 '15 at 15:28
• @AsafKaragila: So, should one read the claim as "for every infinite set $A$, there is an injection from $\aleph_0$ to $\mathcal{P}(\mathcal{P}(A))$"? Or am I still missing something? – Nate Eldredge May 24 '15 at 15:33
• @Nate: Yes, that is correct. (For bonus points, you can actually find an injection from $\Bbb R$ into $\mathcal{P(P(}A))$. And you can still show that the inequality is strict.) – Asaf Karagila May 24 '15 at 15:33

HINT: It suffices to find a surjection from $2^\kappa$ onto the natural numbers, now look at cardinalities of finite sets.
• it seems like if I showed $f:2^\kappa \to \omega$ was a surjection, then this doesn't imply $\aleph_0 \leq 2^\kappa$ unless I use the axiom of choice? Am I missing something? – CameronJWhitehead May 24 '15 at 16:32
• @CameronJWhitehead In fact, if there is a surjection from $A$ to $B$, then there is an injection from $\mathcal P(B)$ into $\mathcal P(A)$, so you get that $\mathbb R$ injects into $2^{2^\kappa}$. – Andrés E. Caicedo May 24 '15 at 18:47
• @Andres: That is correct. And if we brought this up, we can even show that there is no bijection from $\Bbb R$ to $2^{2^\kappa}$, but that's a more difficult theorem. – Asaf Karagila May 24 '15 at 18:48