# Prove countable set function: natural numbers and pairs of natural numbers

Can someone please explain me the proof, where there is a
1-1 Correspondence between the set of natural numbers and the set of all pairs of natural numbers How can the below data be one-to-one function that is total over the natural numbers and onto the pairs of natural numbers?

The following printed list defines a relation between the natural numbers and the natural number pairs.

0:(0,0)
1:(0,1)
2:(1,0)
3:(0,2)
4:(1,1)
5:(2,0)
6:(0,3)
7:(1,2)
8:(2,1)
9:(3,0)
10:(0,4)
11:(1,3)
12:(2,2)
13:(3,1)
14:(4,0)
15:(0,5)
16:(1,4)
17:(2,3)
18:(3,2)
19:(4,1)
20:(5,0)
21:(0,6)
22:(1,5)
23:(2,4)
24:(3,3)
25:(4,2)
26:(5,1)
27:(6,0)
28:(0,7)
29:(1,6)
30:(2,5)
... and so on ...

• Welcome to Math.SE! Can you explain a little more explicitly why you don't understand that this defines a one-to-one function? – Hrodelbert Oct 2 '15 at 9:18
• Thank you. How two different types (one is a natural number and the other is a pair of natural numbers) are related and how do they have one-to-one function. How are they connected? – user3337714 Oct 2 '15 at 9:20
• math.stackexchange.com/questions/444447/… – Stravog Oct 2 '15 at 9:52
• Can you see the pattern? Can you see that "... and so on ..." continues to assign each number a pair? Can you figure out a way to from a given pair deduce which number it corresponds to? – skyking Oct 2 '15 at 9:52
• See the info about the Cantor pairing function, you may have to switch the coordinates (I didn't check). en.wikipedia.org/wiki/Pairing_function – coffeemath Oct 2 '15 at 9:56

Using $(m,n)\mapsto\dfrac{(m+n)(m+n+1)}2+m$, we can go the other way round by considering $k=T(n)+m$, where $T(n)=\dfrac{n(n+1)}{2}$, $n$ is maximal and $m\ge0$ to give $(m,n-m)$ as the pairing.