Cardinality of Power set of naturals equal to $\Bbb{N}^\Bbb{N}$

Question

The question: Decide with proof which has greater Cardinality $\Bbb{N}^\Bbb{N}$ or $2^\Bbb{N}$.

My intuition: They will be the same. By Cantors argument and the continuum hypothesis, both will have cardinality $\aleph_1$.

My attempt at a proof: I know that $|A|\le|B|$ if there is an injection $f:A \rightarrow B$ and by the Schroder Bernstein theorem I know that you can always compare cardinalities. Thus, I want to show that there is an injection from $\Bbb{N}^\Bbb{N} \rightarrow 2^\Bbb{N}$ and one from $2^\Bbb{N} \rightarrow \Bbb{N}^\Bbb{N}$.

I thought an injection from $2^\Bbb{N} \rightarrow \Bbb{N}^\Bbb{N}$ might be: for each element of the power set of Naturals, arrange its elements from smallest to largest and map the set to the element of $\Bbb{N}^\Bbb{N}$ that has all of the same elements with an infinite string of zeros if needed. For example: ${(a_1,a_2,...,a_k)} \in 2^\Bbb{N} \rightarrow {(a_1, a_2, a_3,...,a_k,0,0,0,0...)}\in \Bbb{N}^\Bbb{N}$ where $a_1<a_2<a_3<...$

Is this a valid injection? Can you please help me find an injection the other way or am I not on the right track? Thanks.

Answer 1

The injection you gave seems to be right. Let me give you one in the other direction. $\mathbb{N}$ is clearly in bijection with the set of odd numbers $N_0$. So $\mathbb{N}^\mathbb{N}$ is in bijection with $N_0^{\mathbb{N}}$ and it is enough to prove that $N_0^{\mathbb{N}}$ injects into $2^{\mathbb{N}}$.

We consider the following map. For every sequence of odd numbers $s=(a_0,a_1, a_2,\ldots)$ we map it to set $\{a_0, 2 a_1, 2^2 a_2, \ldots\}$. You must now show that this is an injection.