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

<br /> \phi:\mathbb{N}^{\mathbb{N}}\to 2^{\mathbb{N}}<br />
?

 

[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:

<br /> \phi(0,0,0,\ldots)=(0,0,0,\ldots)<br />

<br /> \phi(1,0,0,\ldots) = (1,0,0,0,0,\ldots)<br />
<br /> \phi(2,0,0,\ldots) = (0,0,1,0,0,\ldots)<br />
<br /> \phi(3,0,0,\ldots) = (0,0,0,0,1,\ldots)<br />

<br /> \phi(0,1,0,\ldots) = (0,1,0,0,0,0,0,0,0,0,\ldots)<br />
<br /> \phi(0,2,0,\ldots) = (0,0,0,0,0,1,0,0,0,0,\ldots)<br />
<br /> \phi(0,3,0,\ldots) = (0,0,0,0,0,0,0,0,0,1,\ldots)<br />

and so on. Then

<br /> \phi\Big(\sum_{n=0}^{\infty} f(n) e_n\Big)<br /> = \sum_{n=0}^{\infty} \phi\big(f(n) e_n\big)<br />

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.