Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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,

share|improve this question
add comment

marked as duplicate by hardmath, Arthur Fischer, Micah, Stefan Hansen, Aang Mar 9 '13 at 8:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5 Answers

up vote 2 down vote accepted

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.

share|improve this answer
Indeed the first duplicate I found has essentially the same answer by you! –  hardmath Mar 9 '13 at 4:29
It might be nice to learn some searching secrets. I did remember answering the question, but finding is another matter. –  André Nicolas Mar 9 '13 at 4:35
@AndréNicolas You can search for user:me is:answer cantor pairing to boil it down to (currently) seven candidates –  Tobias Kienzler Mar 15 '13 at 14:00
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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?

share|improve this answer
add comment

Yes there exists a quadratic bijection.

See this

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.