3
$\begingroup$

How can we show that $ \aleph_0 \leq 2^{2^\kappa}$ for any infinite cardinal $\kappa$ without using the Axiom of Choice?

By Cantor's Theorem we can easily show that if $ \aleph_0 > 2^{2^\kappa}$, then $\aleph_0 > \kappa$. Is there a way to conclude from this that $\kappa$ is finite without appealing to Choice? Thanks

$\endgroup$
  • $\begingroup$ Notice that, without choice, $\le$ is not necessarily total. We either have $\aleph_{0} \le 2^{2^\kappa}$ or ($\aleph_{0} \not \le 2^{2^{\kappa}} \not \le \aleph_{0}$). $\endgroup$ – Stefan Mesken May 23 '16 at 8:27
  • $\begingroup$ Is it somehow, bizarrely, possible that choice fails but still $2^{2^\kappa}$ is the cardinality of an ordinal for every $\kappa$? $\endgroup$ – Patrick Stevens May 23 '16 at 8:33
  • $\begingroup$ @Patrick No. If $2^{\kappa}$ is bijective to an ordinal, for every ordinal $\kappa$, then choice holds. (I believe its proof is due to Tarski.) If $2^{2^{\kappa}}$ bijective to an ordinal, for each ordinal $\kappa$, this implies that $2^{\kappa}$ is and hence it implies choice. $\endgroup$ – Stefan Mesken May 23 '16 at 8:56
2
$\begingroup$

You can define an injection $f:\mathbb N\to\mathcal P(\mathcal P(X))$ directly: $$ f(n) = \{ A\subseteq X \mid \#A=n \} $$ since, by induction, an infinite set has subsets of every finite cardinality.

$\endgroup$
0
$\begingroup$

The cardinal $m=2^{2^k} $ is infinite otherwise $k$ must be finite. Therefore $\aleph_0$ must be not greater than $m.$

$\endgroup$
  • 2
    $\begingroup$ This shows that $\aleph_0 \not> 2^{2^\kappa}$, but in the absence of Choice that does not imply $\aleph_0 \le 2^{2^\kappa}$. $\endgroup$ – Henning Makholm May 23 '16 at 8:53
  • $\begingroup$ @HenningMakholm it is necesarry to assume a axiom of choice to tell that if a set $A$ is infinite then $A$ contains a subset $B=\{a_n : n\in \mathbb{N}\}$? $\endgroup$ – MotylaNogaTomkaMazura May 23 '16 at 12:00
  • 1
    $\begingroup$ x @Motyla: Yes -- it is consistent with ZF that there may exist a set that is not equinumerous with any natural, yet does not have any countably infinite subset. $\endgroup$ – Henning Makholm May 23 '16 at 12:22
  • $\begingroup$ Thank you for the answer. Thats really interesting $\endgroup$ – MotylaNogaTomkaMazura May 23 '16 at 12:43

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.