1
$\begingroup$

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 ...
$\endgroup$
  • $\begingroup$ Welcome to Math.SE! Can you explain a little more explicitly why you don't understand that this defines a one-to-one function? $\endgroup$ – Hrodelbert Oct 2 '15 at 9:18
  • $\begingroup$ 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? $\endgroup$ – user3337714 Oct 2 '15 at 9:20
  • $\begingroup$ math.stackexchange.com/questions/444447/… $\endgroup$ – Stravog Oct 2 '15 at 9:52
  • $\begingroup$ 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? $\endgroup$ – skyking Oct 2 '15 at 9:52
  • $\begingroup$ 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 $\endgroup$ – coffeemath Oct 2 '15 at 9:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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