[SOLVED] bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$

By Ataraxia

I understand that both $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are of the same cardinality by the Shroeder-Bernstein theorem, meaning there exists at least one bijection between them. But I can't figure out what such a bijection would be. The paper that I'm reading gives an example of an injective function $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$, $f(n)=(0,n)$, and an injective function $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, $g(a,b)=2^a3^b$. I was thinking perhaps if there were some way to combine these two, I could find a bijection, but I have no idea how to go about that or if it's even possible.

What is an example of a bijection between these two sets, and please explain the process by which you found it? @dtldarek 2013-07-15 19:50:41

The easiest bijection $\mathbb{N}\times\mathbb{N} \to \mathbb{N}$ I know is like this:

$$\color{red}{42},\color{blue}{2013} \to \color{blue}{2}\, \color{red}{0}\, \color{blue}{0}\, \color{red}{0}\, \color{blue}{1}\, \color{red}{4}\, \color{blue}{3}\, \color{red}{2}\,.$$

The above is for base 10, but it works for any base $b \geq 2$.

Edit: As there was some confusion, some alternative explanations:

1. To obtain the result, one starts writing digits from the right side in alternating fashion, and if one of the numbers has no more digits, we put zeros.
2. Let $\varepsilon$ be the empty string, then \begin{align} f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= f(\color{red}{a_ma_{m-1}\ldots a_2}, \color{blue}{b_nb_{n-1}\ldots b_2}) \color{blue}{b_1}\color{red}{a_1} \\ f(\color{red}{\varepsilon}, \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= f(\color{red}{\varepsilon}, \color{blue}{b_nb_{n-1}\ldots b_2}) \color{blue}{b_1}\color{red}{0} \\ f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{\varepsilon}) &= f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{\varepsilon}) \color{blue}{0}\color{red}{a_1} \\ f(\color{red}{a_1}, \color{blue}{\varepsilon}) &= \color{blue}{\varepsilon}\color{red}{a_1} \\ f(\color{red}{\varepsilon}, \color{blue}{\varepsilon}) &= \varepsilon \end{align}
3. Let numbers be treated as polynomials in their base, i.e. $\mathbf{123}(z) = 1z^2+2z^1+3z^0$, then $$f(\color{red}{\mathbf{a}}, \color{blue}{\mathbf{b}})(z) = \color{red}{\mathbf{a}}(z^2) + z\color{blue}{\mathbf{b}}(z^2).$$

Some more examples for the first method: \begin{align} \color{red}{0},\color{blue}{50} &\to \color{blue}{5}\, \color{red}{0}\, \color{blue}{0}\, \color{red}{0}\,,\\ \color{red}{50},\color{blue}{0} &\to \color{red}{5}\, \color{blue}{0}\, \color{red}{0}. \end{align}

An example for the second method:

\begin{align} f(\color{red}{42},\color{blue}{2013}) &= f(\color{red}{4},\color{blue}{201}) \,\color{blue}{3}\,\color{red}{2}\, \\ &= f(\color{red}{\varepsilon},\color{blue}{20}) \,\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\ &= f(\color{red}{\varepsilon},\color{blue}{2}) \, \color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\,\\ &= f(\color{red}{\varepsilon},\color{blue}{\varepsilon}) \, \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\ &= \varepsilon\, \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\ &= \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, . \end{align}

Finally, an example for the third method:

\begin{align} \color{red}{\mathbf{a}}(x) &= \color{red}{4}x+\color{red}{2} \\ \color{blue}{\mathbf{b}}(y) &= \color{blue}{2}y^3+\color{blue}{0}y^2+\color{blue}{1}y^1+\color{blue}{3}y^0 \\ \color{red}{\mathbf{a}}(z^2) &= 4z^2+2 \\ \color{blue}{\mathbf{b}}(z^2) &= 2z^6+z^2+3 \\ f(\color{red}{\mathbf{a}}, \color{blue}{\mathbf{b}})(z) &= \color{red}{\mathbf{a}}(z^2)+z\color{blue}{\mathbf{b}}(z^2) \\ &= 2z^7+z^3+4z^2+3z+2 \\ &= \color{blue}{2}z^7+\color{red}{0}z^6+\color{blue}{0}z^5+\color{red}{0}z^4+\color{blue}{1}z^3+\color{red}{4}z^2+\color{blue}{3}z^1+\color{red}{2}z^0 \end{align}

I hope this helps ;-) @Asaf Karagila 2013-07-15 19:54:05

Is $0,50$ sent to $500$ or $50,0$ sent to $500$? @celtschk 2013-07-15 19:56:31

@AsafKaragila: $(\color{red}{0},\color{blue}{50})=(\color{red}{00},\color{blue}{50})$ is sent to $\color{blue}5\color{red}0\color{blue}0\color{red}0$. I would have defined the bijection the other way, though. @dtldarek 2013-07-15 19:58:58

Thank you celtschk. You are right, maybe the other way would be more intuitive, but as long as we are consistent it does not matter. @DonAntonio 2013-07-15 20:03:06

I'm still not sure I got this: so one has to complete by means of zeros on the left the ammount of digits every coordinate has? Say, $\;(234,1)=(234,001)\;$? And then you write the digits odds-even, like $\,(234,\color{blue}{001})\mapsto \color{blue} 02\color{blue}03\color{blue}14=20314\;$ ? @Asaf Karagila 2013-07-15 20:06:20

@dtldarek: So how many $00000$'s do you want $0$ to actually be? What about $1,11$ and $11,1$? What about $111,1111$ and $1111,111$? @Brian M. Scott 2013-07-15 20:13:46

@Asaf: I take it that $\langle1,11\rangle\mapsto1011$ and $\langle11,1\rangle\mapsto0111$. @dtldarek 2013-07-15 20:15:47

@AsafKaragila Let's treat a number as a polynomial in $b$, its base, that is, $123 = 1b^2+2b^1+3b^0$. Then $f(n,m) = n(b^2)+bm(b^2)$. @dtldarek 2013-07-15 20:20:58

@DonAntonio Yes. Alternative formulation would be: you write the digits odd-even, and when you run out, you put zeros. @dtldarek 2013-07-15 20:23:02

@AsafKaragila As there was some confusion, I would appreciate any suggestions on how I could make the construction more easily digestible. @DonAntonio 2013-07-15 20:24:13

@dtldarek, I don't get that: how many zeros do I have to put when "I run out" (what does this mean, anyway?)? One, two, thirty five...? @dtldarek 2013-07-15 20:32:52

@DonAntonio When you represent a polynomial $P(x) = 2x^3+0x^2+1x^1+3x^0$ as a sequence $a_0=3, a_1=1, a_2=0, a_3=2$, how many zeros do you put? For example, $a_4 = ?$, $a_5 = ?$ It does not matter, because $P(x) + 0\cdot x^{35}$ is still $P(x)$. In fact $(a_n)$ might be infinite sequence, but with finite support. The zeros are only so that number does make sense (a blank is not a number). @DonAntonio 2013-07-15 23:12:31

With a polynomial is very simple: you have one zero for every power of $\,x\,$ with zero coefficient. Period. Of course, you can also add zeros to the left with no consequence (but getting bored, perhaps). In this case, you said you begin writing digits odd-even until you run out...run out of what? And where do you add the zeros? I still think that the soudner thing to do here is to add as many zeros on the left of the shorter number as to have the same number of digints in both coordinates, and then odd-even... @dtldarek 2013-07-16 05:36:24

@DonAntonio You start from the right side and go until you run out of digits, or in terms of polynomials, until you run out of non-zero coefficients. I add zeros to the left whenever the second number is still going, because otherwise it would create blanks (e.g. 2_0_1432 for 42, 2013). When both numbers are finished, of course, as in polynomials, you can add more zeros to the left, that is, $00345=345$, but there is no reason to do so. @DonAntonio 2013-07-16 06:47:15

Now I think I got it, @dtldarek . Thanks. @dtldarek 2013-07-16 06:48:41

@DonAntonio Great, now if you could tell me, how can I make my post more accessible? @DonAntonio 2013-07-16 06:53:11

Well, just writing down explicitly how to form the map, exactly how you explained to me. For one, beginning with the "writing the digits from the right " would be great, as this is what made things clear. But I think it'd be clearer to tell what we talked about above" complete with zeros on the left one of the numbers so that both have the same No. of digits and etc. @dtldarek 2013-07-19 10:22:42

@DonAntonio Thanks, I fixed what I could. @Asaf Karagila 2013-07-19 10:26:56

Yeah, it's a nice map. Far from "easiest", as the many comments indicate, though. :-) @dtldarek 2013-07-19 10:49:08

@AsafKaragila I guess it depends on who's looking ;-) For me it is instantaneous that it is a bijection, and what the inverse is (both easy to code, as in some programming language). While it is intuitive that Cantor's example is a bijection, its inverse is more hairy and (correct me if I am wrong) you need to rely on existential results if you want to do this "elegantly". @Asaf Karagila 2013-07-19 22:07:36

Which is why I usually prefer $2^m(2n+1)-1$. Although in the context of recursive functions and whatnot, it's far more striking that the Cantor pairing function is $\Sigma^0_0$ as are its inverses. That's an important feature. @dtldarek 2013-07-19 22:44:33

@AsafKaragila Neat, I haven't noticed that. This is why I like math.SE so much, even if you answer a way more than ask, there is still a lot one can learn ;-) Thanks! @N. S. 2013-07-15 19:54:47

Assuming than $\mathbb N$ contains $0$, then

$$f(m,n)=2^m(2n+1)-1$$

is a bijection from $\mathbb N \times \mathbb N$ to $\mathbb N$.

The inverse $g: \mathbb N \to \mathbb N \times \mathbb N$ is simple: $g(n)=(a,b)$ where $a$ is the largest power of $2$ dividing $n+1$ and $2b+1$ is the largest odd number dividing $n+1$.

If you don't include $0$ in $\mathbb N$, all you need is replace $m,n$ by $m-1, n-1$. @Asaf Karagila 2013-07-15 19:45:47

I found such bijection when I was a freshman. Cantor found it, but I don't know how he came to notice it.

$$(m,n)\mapsto\frac{(m+n)(m+n+1)}2+m$$

Another function, which is simpler to prove is a bijection is the following, I don't know who came up with that one.

$$(m,n)\mapsto 2^m(2n+1)-1$$

The idea is that every pair encodes a unique number by writing it as an even number times an odd number, and reducing $1$ so we can get $0$ as well. @egreg 2013-07-15 20:00:09

Let's call $f$ the first function. If $m+n=k$, then $f(m,n)=k(k+1)/2 + m$. So $f(0,0)=0$, $f(0,1)=1$, $f(1,0)=2$; $f(0,2)=3$, $f(1,1)=4$, $f(2,0)=5$; and so on. So we're counting the points on the lattice going through the diagonals. And we're lucky, because the $k$-th diagonal contains exactly $k+1$ points.

[SOLVED] Explicit bijection between $[0,1)$ and $(0,1)$

• 2015-09-07 15:38:15
• Gabriel Romon
• 2465 View
• 3 Score