# Size of cardinal without choice

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

• 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}$). – Stefan Mesken May 23 '16 at 8:27
• Is it somehow, bizarrely, possible that choice fails but still $2^{2^\kappa}$ is the cardinality of an ordinal for every $\kappa$? – Patrick Stevens May 23 '16 at 8:33
• @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. – Stefan Mesken May 23 '16 at 8:56

## 2 Answers

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.

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

• 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}$. – Henning Makholm May 23 '16 at 8:53
• @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}\}$? – MotylaNogaTomkaMazura May 23 '16 at 12:00
• 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. – Henning Makholm May 23 '16 at 12:22
• Thank you for the answer. Thats really interesting – MotylaNogaTomkaMazura May 23 '16 at 12:43