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$
2
  • $\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
    Commented May 5, 2016 at 10:17
  • $\begingroup$ I’ve taken a discrete math course, but I’m wondering what level of discrete math I would need to know to have any intuition on this problem. Any textbook recommendations? $\endgroup$ Commented Jan 21 at 19:24

1 Answer 1

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$
2
  • $\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
    Commented May 5, 2016 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
    Commented May 5, 2016 at 20:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .