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?

  • 1
    $\begingroup$ 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? $\endgroup$ – CameronJWhitehead May 24 '15 at 14:31
  • $\begingroup$ 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? $\endgroup$ – Nate Eldredge May 24 '15 at 15:23
  • 1
    $\begingroup$ @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.) $\endgroup$ – Asaf Karagila May 24 '15 at 15:28
  • 1
    $\begingroup$ @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? $\endgroup$ – Nate Eldredge May 24 '15 at 15:33
  • 2
    $\begingroup$ @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.) $\endgroup$ – 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.

You can also show that equality is never possible. But that is besides the point. You are asked to find an injection, not to prove there are no bijections.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much, the last answer probably confused me more than anything else. I have to admit, I was hoping you would answer. $\endgroup$ – CameronJWhitehead May 24 '15 at 16:19
  • $\begingroup$ You're welcome! $\endgroup$ – Asaf Karagila May 24 '15 at 16:21
  • $\begingroup$ 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? $\endgroup$ – CameronJWhitehead May 24 '15 at 16:32
  • 3
    $\begingroup$ @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}$. $\endgroup$ – Andrés E. Caicedo May 24 '15 at 18:47
  • 2
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila May 24 '15 at 18:48

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.