# Proving that $\{0,1\}^\mathbb N$ and $\mathbb{N^N}$ have the same cardinality [duplicate]

Problem

Let $D$ be the set of all the functions $f\colon\mathbb N\to \mathbb N$ , where $\mathbb N$ is the set of natural numbers.

Let $E$ be the set of all functions $f\colon \mathbb N\to\{\,0,1\,\}$.

Prove both the sets have equal cardinality.

Attempt (failed)

$E$ is the set of all infinite binary sequences. By Cantor's second diagonal argument $E$ is uncountable. Since $E\subset D$, $D$ is also uncountable. If i prove there exists injections from $D$ to $E$ and also from $E$ to $D$, then Schroeder-Bernstein theorem can be used.

Attempt 2

Consider two functions $\alpha\colon D \to E$ and $\beta\colon E \to D$

Consider a function $f \in E$ is a function from $\mathbb N$ to $\{\,0,1\,\}$. $\beta(f)$ is a function that assigns to $n$ the $f(n)+1$ . This is a injective function .

I have difficulty finding $\alpha$.

Any hint or help will be appreciated.

## marked as duplicate by Asaf Karagila♦ elementary-set-theory 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(); } ); }); }); Aug 17 '18 at 11:27

As you remark, we just need an injection of $D$ into $E$.
Consider $F\in D$, and let $p_i$ denote the $i^{th}$ prime. Define a function $\mathscr F\in E$ by letting $F(p_i^n)$ denote the $n^{th}$ digit in the binary expansion of $F(i)$. If $m$ is not a prime power just let $\mathscr F(m)=0$. Now just verify that the map $\Phi: D\to E$, $F\mapsto \mathscr F$ is injective.
In general, the set of all functions from a set $A$ to a set $B$ has cardinality $card(B)^{card(A)}$. So basically you nee to show that $\aleph_0^{\aleph_0}=2^{\aleph_0}$.