Is there a bijection between $\mathbb N$ and $\mathbb N^2$? 
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,
 A: Yes. Imagine starting at $(1,1)$ and then zig-zagging diagonally across the quadrant. I'll leave you to formulate it.
Hint: for every natural number $>1$ there's a set of elements of $\mathbb{N}^2$ that add up to that number. For $2$, there's $(1,1)$. For $3$, there's $(2,1)$ and $(1,2)$...
A: Yes there exists a quadratic bijection. 
See this
A: You're trying to find a way to "count" the things in $\mathbb N^2$ in a manner that gets you to any pair $(a,b)$ in some finite time. Notice that "counting" something is essentially finding this bijection - there is a "first" pair, and a "second pair" and so on.
There are many ways to do this, but most of them come down to ordering the set $\mathbb N^2$ in some meaningful way. 
Hint: There are countably many diagonals, i.e. there is a "first diagonal" a "second diagonal" and so on. Does this work? 
A: 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.
A: 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.
