Prove a function is one-to-one and onto

Question

I need some help proving the following function is one-to-one and onto for $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$.

$F(i, j) = {i + j - 1 \choose 2} + j$

I know you guys like to see some attempt at a problem but I honestly have no idea where to start. A naive attempt simply making $F(i, j) = F(n, m)$ seems like it will have way too many cases to prove and I'm not even sure if that will prove 1-1. Is the best approach to define some sort of function and show it is invertible?

By the way, this is Cantor's pairing function. Logicians use it to code finite sequences of numbers by single numbers. — Andrés E. Caicedo, Feb 06 '14 at 03:04
proving surjectivity is actually quite fun, maybe you could read at [ http://juanmarqz.wordpress.com/2011/02/17/algunos-trucos-matematicos-en-spanish/ ] — janmarqz, Feb 06 '14 at 03:19
what's up @John? could you tell now what are $(i,j)$, positive integers, such that $F(i,j)=100,000$ for example? Kudos for your problem that made me sweat :D — janmarqz, Feb 06 '14 at 15:39
@john do you appreciate the effort we put into answering your question? could you upovote or accept an answer if you do? Thank you very much for your contribution to MSE. — Asinomás, Feb 08 '14 at 03:42

score 5 · Answer 1 · answered Feb 06 '14 at 02:19

You could start by listing the function values out in a grid. You might see something like the following:

$$ \begin{array}{cccccccccc} 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\ 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & 54 & 65 \\ 4 & 8 & 13 & 19 & 26 & 34 & 43 & 53 & 64 & 76 \\ 7 & 12 & 18 & 25 & 33 & 42 & 52 & 63 & 75 & 88 \\ 11 & 17 & 24 & 32 & 41 & 51 & 62 & 74 & 87 & 101 \\ 16 & 23 & 31 & 40 & 50 & 61 & 73 & 86 & 100 & 115 \\ 22 & 30 & 39 & 49 & 60 & 72 & 85 & 99 & 114 & 130 \\ 29 & 38 & 48 & 59 & 71 & 84 & 98 & 113 & 129 & 146 \\ 37 & 47 & 58 & 70 & 83 & 97 & 112 & 128 & 145 & 163 \\ 46 & 57 & 69 & 82 & 96 & 111 & 127 & 144 & 162 & 181 \\ \end{array} $$

Now, can you explain that? One hint might be to look up triangular numbers.

I guess I'm tired or something but I still don't quite get where this is going. — John, Feb 06 '14 at 02:26
Can you see the pattern in @Mark's table? If so then you could try two steps: (1) assuming the pattern continues, explain why $F$ is one-to-one and onto; (2) explain why the pattern does in fact continue. — David, Feb 06 '14 at 02:31

score 0 · Answer 2 · edited Feb 06 '14 at 03:05

0

I would like to point out I love Mark's answer. Triangular numbers are these ones. and they are of the form $\binom{n+1}{2}$

enter image description here

edited Feb 06 '14 at 03:05

Andrés E. Caicedo

79,201

answered Feb 06 '14 at 02:31

Asinomás

105,651

Does this help you? – Asinomás Feb 06 '14 at 02:33
Would it be helpful to express the binomial coefficient in summation notation and then handle the cases where i + j - 1 < 2 separately? – John Feb 06 '14 at 02:37
yes, I believe that is another approach. – Asinomás Feb 06 '14 at 02:38
Is it different than what you are trying to show me here? I see that the triangular numbers correspond to the expression I have but I'm unsure how it helps. – John Feb 06 '14 at 02:39
This is a visual proof – Asinomás Feb 06 '14 at 02:41

janmarqz · Answer 3 · 2014-02-06T20:01:00.627

Surjectivity of $F(i, j) = {i + j - 1 \choose 2} + j$.

Here it goes an algorithm to find for a given natural $\lambda$, a pair $(i,j)$ of natural numbers such that $F(i, j) = \lambda$:

For,

1) Find a couple $(1,m)$ such that $F(1,m)\approx\lambda$

2) Then you are lead to consider ${m\choose 2}+m\approx\lambda$ which is a quadratic $m^2+m-2\lambda\approx0$

3) Seek $m_+=\frac{-1+\sqrt{1+8\lambda}}{2}$

4) Verify that $F(1,\lfloor m_+\rfloor)\le\lambda$, where $\lfloor m_+\rfloor$ is the positive integer $\le$ than $m_+$.

5) Take $r=\lambda-F(1,\lfloor m_+\rfloor)$

6) Then $F(\lfloor m_+\rfloor+2-r,r)=\lambda$

Check the next exemplification:

Do you need $i,j\in{\Bbb{N}}$ such that $F(i,j)=308$?

-- Find the greatest solution for $m^2+m-616=0$:

-- this is $m_+=\frac{-1+\sqrt{1+2464}}{2}=24.3243...$

-- so $\lfloor m_+\rfloor=24$

-- then $F(1,24)={24\choose 2}+24=300$

-- so $r=8$

-- Then $F(18,8)={25\choose 2}+8=308$.

Injectivity of $F(i, j) = {i + j - 1 \choose 2} + j$.

(Pending)

this little algorithm is adapted from the one in [ http://juanmarqz.wordpress.com/2011/02/17/algunos-trucos-matematicos-en-spanish/ ] — janmarqz, Feb 06 '14 at 05:33

Prove a function is one-to-one and onto

3 Answers3

Linked