# proving there is an injection from natural numbers to a set without the axiom of choice

Let $\kappa$ be an infinite cardinal number. Prove, without appealing to the Axiom of Choice, that $$\aleph_0 \leq 2^{2^\kappa}$$

I am struggling to answer this question. If I had the axiom of choice available, I would have that there is an injection from natural numbers to k, by cardinal comparability. I'm not sure how to approach this question without axiom of choice being available.

• Does the theorem that states that $|/mathcal P(X)|>|X|$ use axiom of choice? – André Porto May 20 '17 at 23:09
• @AndréPorto Cantor's theorem shows (without choice) that $$2^{2^\kappa}\gt2^\kappa\gt\kappa.$$ That does not in itself establish $$2^{2^\kappa}\ge\aleph_0$$ because, in the absence of the axiom of choice, we do not know that $\kappa\ge\aleph_0;$ as far as we know, $\kappa$ could be incomparable with $\aleph_0.$ – bof May 21 '17 at 1:27
• Oh man! It's everything so confusing without choice! – André Porto May 21 '17 at 5:09
• @AndréPorto No, that's not true. By definition, a set is infinite if it has more than $n$ elements for every natural number $n.$ In the real world, where the axiom of choice is true, every infinite set has cardinality $\ge\aleph_0.$ However, in some weird fantasy worlds where the axiom of choice fails, there are sets which can't be well-ordered; the cardinality of such a set is not equal to any aleph, and is not necessarily comparable with $\aleph_0.$ – bof May 21 '17 at 6:56
• Yeah, but I was thinking. Let X be an infinite set. Define $f:\aleph_0\to X$ as follows: $f(0)=x_0$ for some fixed $x_0$; For each $n$, $X$ must contain more than $n$ elements, so there exists $x_{n+1}$ in $X$ which is not in $\{f(x_0),...,f(x_n)\}$ and we define $f(n+1)=x_{n+1}$. This way we constructed an injective function from $\aleph_0$ to $X$. Then $aleph_0\leq |X|$ for every infinite set $X$. What am I missing? – André Porto May 21 '17 at 10:29

If $S$ is an infinite set, we can define an injection $f:\mathbb N\to\mathcal P(\mathcal P(S))$ by setting $$f(n)=\{X\subset S:X\text{ is an }n\text{-element set}\}.$$ This shows that $\aleph_0\le2^{2^\kappa},$ a result which I believe is due to Bertrand Russell. Of course it's actually a strict inequality; there is no bijection between $\mathbb N$ and $\mathcal P(\mathcal P(S)).$

By assumption, there exists a non-surjective injective map $f\colon\kappa\to\kappa$. Define $g_0=f$ and recursively $g_{n+1}=f\circ g_n$. Finally, define $\Bbb \omega\to 2^{2^\kappa}$, $n\mapsto g_n(\kappa)$.

• No, the assumption is that $\kappa$ is infinite, i.e., $\kappa\gt n$ for every natural number $n.$ Some kind of choice is needed to conclude that $\kappa$ is Dedekind infinite, i.e., that there is a non-surjective injection $f:\kappa\to\kappa.$ – bof May 21 '17 at 0:57