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

Solution 1:

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} $

Solution 2:

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$

Solution 3:

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.