# Cardinality Problem (2)

• September 8th 2011, 10:30 PM
Markeur
Cardinality Problem (2)
Prove that $|\mathbb{N}^{\mathbb{N}}| = |\mathbb{N}^{\mathbb{N} \times \mathbb{N}}|$.

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

• September 8th 2011, 11:55 PM
Drexel28
Re: Cardinality Problem (2)
Quote:

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

I know of a fact that $|\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 $|\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 $f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ define $F:\mathbb{N}^\mathbb{N}\to\mathbb{N}^{\mathbb{N} \times\mathbb{N}}$ by taking $k\in \mathbb{N}^\mathbb{N}$ to the function $F(k)\in\mathbb{N}^{\mathbb{N}\times\mathbb{N}}$ given by $F(k)(n,m)=k(f(n,m))$. To see this is a bijection you must merely note that if $k\ne h$ then there exists some $n\in\mathbb{N}$ for which $k(n)\ne h(n)$ check then that $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 $|X|=|Y|\implies |Z^X|=|Z^Y|$.
• September 9th 2011, 09:11 AM
MoeBlee
Re: Cardinality Problem (2)
Quote:

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.