11
$\begingroup$

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?

Thanks.

$\endgroup$
2
  • $\begingroup$ Two days ago it was here $\endgroup$
    – Henry
    Feb 17, 2012 at 1:38
  • 1
    $\begingroup$ See here. $\endgroup$ Feb 17, 2012 at 4:21

3 Answers 3

37
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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$

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

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.

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Feb 17, 2012 at 5:50

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