Is there a bijection between $\mathbb N$ and $\mathbb N^2$? [duplicate]

Is there a bijection between $\mathbb N$ and $\mathbb N^2$?

If I can show $\mathbb N^2$ is equipotent to $\mathbb N$, I can show that $\mathbb Q$ is countable. Please help. Thanks,

Solution 1:

It is easier to write an answer than to find one of its several occurrences on this site.

Let $n$ be a positive integer. Then there exist uniquely determined positive integers $u$ and $v$ such that $n=2^{u-1}(2v-1)$. This is because every positive integer $n$ can be written in one and only one way as a power of $2$ (possibly $2^0$) and an odd number.

Define $g$ by $g(n)=(u,v)$. Then $g$ is a bijection from $\mathbb{N}$ to $\mathbb{N}^2$.

For a different bijection, search for the Cantor Pairing Function.

Solution 2:

Here is a non constructive proof.

Of course, there is an injection of $\mathbb{N}$ into $\mathbb{N}\times\mathbb{N}$.

Now consider the map $$ (x,y)\longmapsto 2^x\cdot 3^y $$ By the fundamental theorem of arithmetic, this is an injection of $\mathbb{N}\times\mathbb{N}$ into $\mathbb{N}$.

By Cantor-Bernstein-Schroeder, there exists a bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$.

Edit: I added this answer because the only constructive proof I knew was the zigzag along the diagonals, which I find slightly tedious to write down. But thanks to Andre Nicolas, now I know a straightforward and easy-to-write-down bijection. Which is actually a little step away from the injection I use above.