1
$\begingroup$

This question already has an answer here:

I've got a problem with prove about cardinality of sets.
How can I prove that $\lbrace 0,1 \rbrace^\mathbb{N} \simeq \mathbb{N}^\mathbb{N}$?

$\endgroup$

marked as duplicate by Najib Idrissi, Asaf Karagila cardinals Mar 25 '15 at 14:21

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.

  • 1
    $\begingroup$ One way to think of an element of $\{0, 1\}^{\Bbb N}$ is as a sequence of $0$s and $1$s. You can similarly think of an element of $\Bbb N^{\Bbb N}$ as a sequence of positive integers. Can you think of a bijection between the set of sequences of the first type and the set of sequences of the second type? $\endgroup$ – MJD Jan 6 '15 at 17:36
2
$\begingroup$

Hint. Note that $$ \big\lvert \{0,1\}^{\mathbb N}\big\rvert\le \lvert {\mathbb N}^{\mathbb N}\rvert $$ and $$ \lvert {\mathbb N}^{\mathbb N}\rvert\le \big\lvert \big(\{0,1\}^{\mathbb N}\big)^{\mathbb N}\big\rvert=\big|\{0,1\}^{\mathbb N\times\mathbb N}\big|=\big|\{0,1\}^{\mathbb N}\big|. $$

$\endgroup$
2
$\begingroup$

Hint:

An injection from $\mathbb{N}^\mathbb{N}$ to $\{0,1\}^\mathbb{N}$ could be given by $(a_1,a_2,a_3,...)\mapsto \underbrace{1,1,...,1}_{a_1 \mbox{ times }},0,\underbrace{1,1,...,1}_{a_2 \mbox{ times }},0,\dots$

$\endgroup$
0
$\begingroup$

It's enough consider the following inequalities

$2^\omega\leq \omega^\omega \leq (2^\omega)^\omega = 2^{\omega\cdot\omega}=2^\omega$

Also, you can easily generalize this argument for infinite cardinal numbers.

$\endgroup$

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