Proving that $\mathrm{card}(2^{\mathbb{N}})=\mathrm{card}(\mathbb{N}^\mathbb{N})$

449 Views Asked by At

I'd like to prove that $\mathrm{card}(2^{\mathbb{N}})=\mathrm{card}(\mathbb{N}^\mathbb{N})$, I have the following 'sketch' but I'm not sure if this works.

$|2^{\mathbb{N}}|\leq|\mathbb{N}^{\mathbb{N}}|\leq|2^\mathbb{N^{\mathbb{N}}}|=|2^{\mathbb{N}\times\mathbb{N}}|=|2^\mathbb{N}|$, then $|2^{\mathbb{N}}|=|\mathbb{N}^\mathbb{N}|$

I'm taking for granted the first inequality, (i.e: $|2^{\mathbb N}|\leq|\mathbb{N}^{\mathbb{N}}|$), could be done a further proof about this. Would it be enough to point out that the functions in $2^{\mathbb{N}}$ are in $\mathbb{N}^{\mathbb{N}}$ but there are functions in the last one that are not in the first one? Should I try to give a more formal proof?

2

There are 2 best solutions below

0
On BEST ANSWER

I'll just point out that when you write $2^{\mathbb N^{\mathbb{N}}}$ , there is a certain ambiguity to it.

To make sure that it is clear what you have in mind, you should write $(2^{\mathbb N})^{\mathbb{N}}$. (This is what you have used here.)

The other possible meaning is $2^{(\mathbb N^{\mathbb{N}})}$.

In fact, when someone writes $a^{b^c}$, they usually mean $a^{(b^c)}$. (If someone wants to write $(a^b)^c$, they can write $a^{bc}$ instead. See How to evaluate powers of powers (i.e. $2^3^4$) in absence of parentheses? or $x^{y^z}$: is it $x^{(y^z)}$ or $(x^y)^z$?

0
On

Your proof of inclusion is fine. You have shown that each element of $2^{\Bbb N}$ is also an element of $\Bbb N^{\Bbb N}$.