# Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? [duplicate]

Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$?

I thought I saw this kind of statement somewhere, but I do not remember it.

Can anyone show me the proof of it?

Thanks.

## marked as duplicate by Arturo Magidin, Zhen Lin, Asaf Karagila♦, Nate Eldredge, t.b.Feb 17 '12 at 16:56

• Two days ago it was here – Henry Feb 17 '12 at 1:38
• See here. – Arturo Magidin Feb 17 '12 at 4:21

They are actually equal, $2^{\aleph_0}\leq \aleph_0^{\aleph_0}\leq (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}$

Depending on your precise definition of "cardinal", the theorem below may require the Axiom of Choice (in fact, to make it really useful it does require it).

Theorem. For all cardinals $\lambda$ and $\kappa$, with $\kappa$ infinite, if $2\leq \lambda\leq\kappa^+$, then $\lambda^{\kappa}=2^{\kappa}$.

Proof. $2^{\kappa}\leq \lambda^{\kappa}\leq (\kappa^+)^{\kappa}\leq (2^{\kappa})^{\kappa} = 2^{\kappa\kappa} = 2^{\kappa}$. $\Box$

(AC is used to get $\kappa\kappa=\kappa$; the assertion that every infinite set $X$ is bijectable with $X\times X$ is equivalent to the Axiom of Choice).

Corollary. $\aleph_0^{\aleph_0} = 2^{\aleph_0}$.

Proof. Take $\lambda=\aleph_0$, which satisfies $2\leq \lambda \leq \aleph_0^+=\aleph_1$. $\Box$

• Don't need choice for the special case of $\kappa = \aleph_0$, though.... – Hurkyl Feb 18 '12 at 3:27
• @Hurkyl: Correct, you don't. – Arturo Magidin Feb 18 '12 at 3:53

We need to find an injection from $\mathbb N^\mathbb N$ to $2^\mathbb N$. We need to encipher a sequence of natural numbers as a binary sequence. The first thought might be to concatenate the binary expansions of the elements from a sequence in $\mathbb N^\mathbb N$. This doesn't work because it's not not an injection: from the resulting binary sequence, we can't tell where one natural numbers ends and another starts. We can easily fix it by taking $3^\mathbb N$ instead of $2 ^\mathbb N$, which is fine because, as I'm sure you know, the sets are equinumerous. We obtain an additional, third, symbol to use in our cipher. We can now use it as a separator in our, previously binary, sequence.

• Or you can just code $(a_0,a_1,a_2,\dots)$ by $a_0$ 1's followed by a 0 followed by $a_1$ 1's followed by a 0 etc. – Alex Kruckman Feb 17 '12 at 5:50