Cardinality Problem (2)

**Markeur** · September 8th 2011, 09:30 PM

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.

Thanks in advance.

**Drexel28** · September 8th 2011, 10:55 PM

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.

Thanks in advance.

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|$ .

**MoeBlee** · September 9th 2011, 08:11 AM

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.

Thread: Cardinality Problem (2)

LinkBack

Thread Tools

Display

Cardinality Problem (2)

Re: Cardinality Problem (2)

Re: Cardinality Problem (2)

Similar Math Help Forum Discussions

[SOLVED] Cardinality Problem

Cardinality

Cardinality

cardinality

Cardinality Problem

Search Tags