Showing a function $f: \mathbb{N} \times\mathbb{N} \to \mathbb{N}$ is injective

Question

Let $f: \mathbb{N} \times\mathbb{N} \to \mathbb{N}$ with

$$ f(i,j) = \frac{(i+j-2)(i+j-1)}{2}+j. $$

I want to show $f$ is an injection. This is how I approached the problem:

I tried to show $f(i,j)=f(u,v)\Rightarrow (i,j)=(u,v)$. So, $$ \frac{(i+j-2)(i+j-1)}{2}+j = \frac{(u+v-2)(u+v-1)}{2}+v $$ implies

$$ [(i-u)+(j-v)](i+j+u+v-3)+2(j-v)=0. $$ So I looked at the two cases:

If $(i-u)+(j-v)=0$, then $$ 0+2(j-v)=0 \Rightarrow j=v. $$ So $i=u$ as well.

Now, for the case $(i-u)+(j-v)\neq0$ I have tried different things but none of them have worked so far.

I would like to get some ideas.

Answer 1

Consider two cases:

First, if $i+j = u+v$. Then $f(i, j) = f(u, v) \Rightarrow j=v \Rightarrow i=u$.

Second, if $i+j \neq u+v$. Without loss of generality we assume the inequality $<$. Observe that

$$\frac{(i+j-2)(i+j-1)}{2} = 1 + 2 + \cdots +(i + j -2).$$

Thus

$$f(i, j) = \frac{(i+j-2)(i+j-1)}{2} + j \le \frac{(u+v-2)(u+v-1)}{2}-(i+j-1) + j <f(u, v)$$

Thus $f(i, j) \neq f(u, v)$ is impossible.

Answer 2

Your method is a good general method, but I think it is not terribly likely to yield results in this case. The trouble is that we need to respect the fact that this works over $\mathbb N$ - that is, we don't care if there are pairs of pairs of real numbers such that $f(i,j)=f(u,v)$, so long as they aren't a distinct pair of natural numbers - but there are distinct pairs of pairs of reals satisfying that, and the algebraic solution will yield them, which is not good if you're trying to prove injectivity.

I think you'll have more luck in studying the form of the function. In particular, here's a few suggestively arranged values: $$f(1,1)=1$$ $$$$ $$f(2,1)=2$$ $$f(1,2)=3$$ $$$$ $$f(3,1)=4$$ $$f(2,2)=5$$ $$f(1,3)=6$$ $$$$ $$f(4,1)=7$$ $$f(3,2)=8$$ $$f(2,3)=9$$ $$f(1,4)=10$$ Notice how, in each grouping, I am keeping $i+j$ constant (as the first summand in your function is a function of $i+j$) and then increasing $j$ (while necessarily decreasing $i$). I would suggest that you split into two cases: Firstly, suppose that $f(i,j)=f(u,v)$ and $i+j=u+v$ - this is the case you've already handled and is easy since one may note that $f$ is linear when $i+j$ is constant. Then, all you need to do is find a bound on $f(i,j)$ in terms of $i+j$ - which you may be able to surmise from the above table.

(Hint: The $n^{th}$ group above has $i+j=n+1$ and is (strictly) bounded below by $1+2+\ldots+(n-1)$ and (non-strictly) bounded above by $1+2+\ldots+(n-1)+n$. Given that the non-strict upper bound of one is a strict lower bound for the next, there can be no overlap between the groups. If you carry everything out carefully, you can find that this is not only injective, but surjective too)

Answer 3

I would take a different approach altogether and show that for each $n\in\Bbb N$ there is a unique $\langle i,j\rangle\in\Bbb N\times\Bbb N$ such that $f(i,j)=n$ by actually calculating $i$ and $j$ from $n$. Here’s a suggestion for how this can be done.

First note that for each $k\ge 2$ there are $k-1$ pairs $\langle i,j\rangle$ of positive integers such that $i+j=k$. Then observe that

$$\frac{(i+j-2)(i+j-1)}2=\sum_{k=1}^{i+j-2}k=\sum_{k=2}^{i+j-1}(k-1)$$

is the number of pairs $\langle u,v\rangle$ of positive integers such that $u+v<i+j$. Now we consider the $i+j-1$ pairs $\langle u,v\rangle$ such that $u+v=i+j$: they are

$$\langle i+j-1,1\rangle,\langle i+j-2,2\rangle,\ldots,\langle 1,i+j-1\rangle\;.$$

The pair $\langle i,j\rangle$ is the $j$-th pair in that list. In other words, $f(i,j)$ is the number of pairs $\langle u,v\rangle$ of positive integers such that $u+v<i+j$, or $u+v=i+j$ and $v\le j$. (It’s the position of $\langle i,j\rangle$ in a diagonal enumeration of $\Bbb N\times\Bbb N$.)

Now work backwards. Given a positive integer $n$, show that there is a unique $m$ such that

$$\frac{m(m+1)}2=\sum_{k=1}^mk<n\le\sum_{k=1}^{m+1}k=\frac{(m+1)(m+2)}2\;.$$

Then show that if $f(i,j)=n$, then necessarily $i+j=m+2$ and $j=n-\frac{m(m+1)}2$.

If you get stuck, take a look at Wikipedia’s discussion of the pairing function; its version differs slightly from yours, because its version is a pairing function for the non-negative integers rather than for the positive integers – the $\Bbb N$ there includes $0$, while yours does not – but the principle is exactly the same, and the sketch should be helpful.

Answer 4

Mathematical Induction

(if anyone is up to it, replace this picture with genuine MathJax)