1. ## Cardinality Problem (2)

Prove that $\displaystyle |\mathbb{N}^{\mathbb{N}}| = |\mathbb{N}^{\mathbb{N} \times \mathbb{N}}|$.

I know of a fact that $\displaystyle |\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|$. The problem here is how I can go about establishing the bijective function non-trivially.

2. ## Re: Cardinality Problem (2)

Originally Posted by Markeur
Prove that $\displaystyle |\mathbb{N}^{\mathbb{N}}| = |\mathbb{N}^{\mathbb{N} \times \mathbb{N}}|$.

I know of a fact that $\displaystyle |\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|$. The problem here is how I can go about establishing the bijective function non-trivially.

If you know basic cardinal arithmetic you can say that $\displaystyle |\mathbb{N}^\mathbb{N}|=\aleph_0^\aleph_0=\aleph_0 ^{\aleph_0\aleph_0}=|\mathbb{N}^{\mathbb{N} \times\mathbb{N}}|$, but this is really just what you're asking, isn't it? If you know there exists a bijection $\displaystyle f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ define $\displaystyle F:\mathbb{N}^\mathbb{N}\to\mathbb{N}^{\mathbb{N} \times\mathbb{N}}$ by taking $\displaystyle k\in \mathbb{N}^\mathbb{N}$ to the function $\displaystyle F(k)\in\mathbb{N}^{\mathbb{N}\times\mathbb{N}}$ given by $\displaystyle F(k)(n,m)=k(f(n,m))$. To see this is a bijection you must merely note that if $\displaystyle k\ne h$ then there exists some $\displaystyle n\in\mathbb{N}$ for which $\displaystyle k(n)\ne h(n)$ check then that $\displaystyle F(k)(f^{-1}(n))\ne F(h)(f^{-1}(m,n))$. I leave it to you to show that this is a surjection.

Note, this extends to show that $\displaystyle |X|=|Y|\implies |Z^X|=|Z^Y|$.

3. ## Re: Cardinality Problem (2)

Originally Posted by Markeur
The problem here is how I can go about establishing the bijective function non-trivially.
This is just an instance of the more general theorem:

If S and T are 1-1, then B^S and B^T are 1-1.

I would just prove that more general result.

Or are you asking how to prove that N and NxN are 1-1?

Do you have the fundamental theorem of arithmetic at your disposal? If so, it's easy to get an injection form NxN into N. If not, then there are other ways too.