Is there an injection from \mathbb{N}^{\mathbb{N}} to 2^{\mathbb{N}}?

[jostpuur]

How do you prove that $$\mathbb{N}^{\mathbb{N}}$$ does not have a cardinality greater than that of $$2^{\mathbb{N}}$$? Is it possible to construct an injection

$$\phi:\mathbb{N}^{\mathbb{N}}\to 2^{\mathbb{N}}$$
?

 

[micromass]

You basically use that $$\mathbb{N}\times\mathbb{N}$$ has the same cardinality than $$\mathbb{N}$$:

$$|\mathbb{N}^\mathbb{N}|\leq |(2^{\mathbb{N})^\mathbb{N}}|=|2^{\mathbb{N}\times\mathbb{N}}|=|2^\mathbb{N}|$$.

The other inequality is trivial to prove, so we have $$|\mathbb{N}^\mathbb{N}|=|2^\mathbb{N}|$$.

 

[jostpuur]

I see.

Actually I also figured out a way to write down an injection explicitly. It's not impossible. Like this:

$$\phi(0,0,0,\ldots)=(0,0,0,\ldots)$$

$$\phi(1,0,0,\ldots) = (1,0,0,0,0,\ldots)$$
$$\phi(2,0,0,\ldots) = (0,0,1,0,0,\ldots)$$
$$\phi(3,0,0,\ldots) = (0,0,0,0,1,\ldots)$$

$$\phi(0,1,0,\ldots) = (0,1,0,0,0,0,0,0,0,0,\ldots)$$
$$\phi(0,2,0,\ldots) = (0,0,0,0,0,1,0,0,0,0,\ldots)$$
$$\phi(0,3,0,\ldots) = (0,0,0,0,0,0,0,0,0,1,\ldots)$$

and so on. Then

$$\phi\Big(\sum_{n=0}^{\infty} f(n) e_n\Big) = \sum_{n=0}^{\infty} \phi\big(f(n) e_n\big)$$

Here $$e_n\in\mathbb{N}^{\mathbb{N}}$$ means the member that maps index $i$ to zero if $i\neq n$, and to one if $i = n$. Any function $$f\in\mathbb{N}^{\mathbb{N}}$$ can be written as above.