10
$\begingroup$

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,

$\endgroup$
14
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Yes there exists a quadratic bijection.

See this

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$

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