Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
What's the cardinality of all sequences with coefficients in an infinite set?

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?


share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

3 Answers 3

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

share|improve this answer

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$

share|improve this answer
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.

share|improve this answer
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.