3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ yes that is the injection that you are looking for in that direction. $2^\mathbb N$ is the set of functions $f:\mathbb N\to 2$ and $\mathbb N^\mathbb N$ is the set of $g:\mathbb N\to\mathbb N$. The map you thouht is the canonucal inclusion of the first set to second. $\endgroup$ – ugur efem May 5 '16 at 10:17
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good. Or you can do the injection from $\mathbb N^\mathbb N$ to $2^\mathbb N$ in one fell swoop: map any sequence $a_0,a_1,\dots$ of natural numbers to the set $\{2a_0+1,2(2a+1+1),4(2a_2+1),\dots\}.$ $\endgroup$ – bof May 5 '16 at 10:50
  • 1
    $\begingroup$ I think we should be careful with OP's injection. If I am understanding correctly, $\{0\}\mapsto(0,0,\ldots)$ and also $\emptyset\mapsto(0,0,\ldots)$. This would be fixed by mapping to $$(a_1+1,a_2+1,\ldots,a_k+1,0,0,\ldots).$$ $\endgroup$ – Szmagpie May 5 '16 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.