Show that $2^\mathbb{N} $ is equinumerous with $2^\mathbb{N\times N} $.

Question

I need to show that $2^\mathbb{N} $ is equinumerous with $2^\mathbb{N\times N} $.

I already found a function from $2^\mathbb{N} $ to $2^\mathbb{N \times N} $, wich just returns a pair containing the same element repeated, but I can't find a function wich goes from $2^\mathbb{N\times N} $ to $2^\mathbb{N} $, any ideas?

Thanks in advance.

Answer 1

HINT: Start with a bijection $p:\Bbb N\times\Bbb N\to\Bbb N$; if you want a specific one, the pairing function works fine. Use $p$ to construct a map $A\mapsto p[A]$ from $2^{\Bbb N\times\Bbb N}$ to $2^{\Bbb N}$, and show that this map is a bijection.

Answer 2

Since $\mathbb{N}$ is equinumerous with $\mathbb{N}\times \mathbb{N}$ -- to get the bijection, think of $\mathbb{N}\times \mathbb{N}$ as the upper quadrant of the integer lattice in the plane. Then start at the origin, go up one, right one, down one, right one, up two, left two, up one, right three, etc.

Answer 3

Well, if you know that $\mathbb N$, $\mathbb Z$, and $\mathbb Q$ are all equinumerous, then all you need is an injection $\mathbb Q\to \mathbb Z\times\mathbb Z$.