How to prove properly that $\mathbb{N \times N}$ $\rightarrow$ $\mathbb{N}$ : $(p,q) \rightarrow \frac{(p+q)(p+q+1)}{2} +q$ is a bijection?

Question

I tried to show that for : $\frac{(p_1+q_1)(p_1+q_1+1)}{2} +q_1$=$\frac{(p_2+q_2)(p_2+q_2+1)}{2} +q_2$

we have $(p_1,q_1)=(p_2,q_2)$ to prove that it's an injection.

But I obtain : $p_{1}^{2}+2p_{1}q_{1}+q_{1}^{2}+p_1+3q_1$ = $p_{2}^{2}+2p_{2}q_{2}+q_{2}^{2}+p_2+3q_2$ and I don't know what to do next.

And for surjectivity I have no idea.

Thanks in advance.

@AsafKaragila for instance if $k=1$ that means $(m,n)=(1,0)$ ? — Maman, Oct 28 '14 at 13:49
@AsafKaragila We have to prove that it's bijective that means injectivity and surjectivity — Maman, Oct 28 '14 at 13:55
@AsafKaragila yes but with your method we prove surjectivity — Maman, Oct 28 '14 at 14:01

score 0 · Answer 1 · answered Oct 28 '14 at 13:50

0

Hint: The bijection works as follows

$$(0,0), (0,1), (1,0), (0,2), (1,1),(2,0)...$$ So you first look at the pairs $(x,y)$ so that $x+y=0$ and you order them lexicographically then all pairs so that $x+y=1$ and you order them lexicographically and so on....

answered Oct 28 '14 at 13:50

azarel

13,120

why do we have to look at $x+y$ ? – Maman Oct 28 '14 at 13:53
@Maman That's the way Cantor constructed the bijection. $f$ is just the formula for it. – azarel Oct 28 '14 at 13:57
If $x+y=1$ there are two solutions for $(x,y)$ – Maman Oct 28 '14 at 14:02
@Maman yes, $(0,1)$ and $(1,0)$ so you need to decide which one goes first. – azarel Oct 28 '14 at 14:04

score 0 · Answer 2 · answered Oct 28 '14 at 14:13

I suggest plotting the function: draw a $5 \times 5$ grid and place the values of the function into the grid. A distinctive pattern will emerge, and you'll get better results proving that the pattern really is there, and using the pattern to prove bijectivity.

Barış Akalın · Accepted Answer · 2014-10-30T23:20:59.827

I think this link contains a good proof http://www.math.drexel.edu/~tolya/cantorpairing.pdf

I think the best and elegant way is to show its bijection by algebraic methods.

We need a lemma:

if $ p_{1}+p_{2} < q_{1}+q_{2} $ then $ f(p_{1},p_{2}) < f(q_{1},q_{2}) $

Proof. Let $ k \in N $ be a fixed natural number and let $ p_{1}+p_{2} = k$. Then it's clear that maximum value of $ f(p_{1},p_{2}) $ is $ f(k, 0) $ and minimum value of $ f(p_{1},p_{2}) $ is $ f(0, k) $ . Given that $ p_{1}+p_{2} < q_{1}+q_{2} $, minimum value of $ f(q_{1},q_{2}), \ where \ q_{1}+q_{2} = k+n, for \ n\geq 1, n \in N $ is $f(0,k+1)$. But this value is still greater than $ f(k,0) $ which is maximum value of $ f(p_{1},p_{2})$. Then we're done. By symmetry $ p_{1}+p_{2} > q_{1}+q_{2} $ then $ f(p_{1},p_{2}) > f(q_{1},q_{2}) $ is also true.

So, $ f(p_{1},p_{2}) = f(q_{1},q_{2}) $ implies $ p_{1}+p_{2} = q_{1}+q_{2} $. If we keep in mind for example $ p_{1}+p_{2} = q_{1}+q_{2} = k $ then, we easily see, $p_{1}=q_{1}$ and $p_{2}=q_{2}$ which proves that our function is injective.

With respect to surjectivity, assume $ z \in N$. Think about largest triangular number not greater than z, that is $t_{k} = k*(k+1)/2 $ (you may want to draw the diagonals to get some intuition). Then, $ p_{1} = z - t_{k}$ and $p_{2} = k - p_{1}$ will do, that is, $f(p_{1},p_{2}) = z$. Its absent in the link but, you need to prove that $p_{2} \in N$.

Sincerely

Ok nice, I've found that $p_2=k\frac{(k+3)}{2}-z$. Then I say that for $k$ odd, we have $k+3$ even, so by multiplying the number becomes even, that means divided by $2$. It's the same thing if we consider $k$ even at the beginning.So $k\frac{(k+3)}{2}\in \mathbb{N}$ and the difference with $z$ is also $\in \mathbb{N}$ because necessarly $z<k+t_z$. So $p_2 \in \mathbb{N}$. That's it ? — Maman, Oct 29 '14 at 13:18
$t_{k}\leq z < t_{k}+k+1 \ (t_{k+1}=t_{k}+k+1) \ -t_{k}-k-1< -z \leq -t_{k} \ -1 < p_{2} \ p_{2} \in N $ — Barış Akalın, Oct 30 '14 at 23:14

How to prove properly that $\mathbb{N \times N}$ $\rightarrow$ $\mathbb{N}$ : $(p,q) \rightarrow \frac{(p+q)(p+q+1)}{2} +q$ is a bijection?

3 Answers3