# Power of sets - $\{0,1\}^\mathbb{N} \simeq \mathbb{N}^\mathbb{N}$ [duplicate]

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

## marked as duplicate by Najib Idrissi, Asaf Karagila♦ cardinals StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 25 '15 at 14:21

• 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? – MJD Jan 6 '15 at 17:36

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|.$$
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$
$2^\omega\leq \omega^\omega \leq (2^\omega)^\omega = 2^{\omega\cdot\omega}=2^\omega$