proving that f:N^2->N is bijective

Question

I'v got a function $f:\omega^2\to\omega$ defined

$$ f(n,k)=\frac{\left(n+k+1\right)\left(n+k\right)}{2}+n $$

This function suppose to be a bijection between $\omega$ and $\omega^2$, but I can't find a simple proof that it's bijective. $f$ noppose to order $\omega^2$ like this

Every proof I saw (in my undergrad degree, for example) was just this picture, with no further proof.

Answer 1

Well, you want a proof.

Let $m \in \mathbb N$

We want to prove that there exist a unique pair of $n,k$ so that

$f(n,k)=\frac{\left(n+k+1\right)\left(n+k\right)}{2}+n =m$

Let $w_m$ be the smallest natural number where $1 + 2 + ..... + w_m = \sum_{j=1}^{w_m} \frac {w_m(w_m + 1)}2 \ge m$.

We know such a number exists as: $S= \{k\in \mathbb N| 1+2+3+....k \ge m\}$ is not empty because $m \in S$ as $1 + .... + m > m$. And by well-ordering principal $S$ has a least element.

So $\frac {w_m(w_m+1)}2 \ge m$ so $\frac {w_m(w_m+1)}2- m \ge 0$ so let $n = \frac {w_m(w_m+1)}2-m \in \mathbb N$.

Now $n < w_m$ because otherwise if $n \ge w_m$

$1 + 2 + ..... + (w_m - 1) = \frac {w_m(w_m+1)}2 -w_m \ge \frac {w_m(w_m+1)}2 - n = m$

But $w_m$ was the smallest such number.

Let $k = w_m -n$.

So $f(n,k)=\frac{\left(n+k+1\right)\left(n+k\right)}{2}+n=$

$\frac {w_m(w_m + 1)}2 + (m -\frac {w_m(w_m + 1)}2) = m$.

So $f$ is onto.

Now if for any $a+b$ if $a + b > n+k$

then $\frac {(a+b)(a+b+1)}2 + b \ge \frac {(a+b)(a+b+1)}2 > m$ (because we proved $n+k = \min S=\min\{k\in \mathbb N| 1+2+3+....k \ge m\}$

And if $a+b < n+k$ then $m - (1 + 2 + ...... + a+b) \ge (a+b) +1$ (because $a+b\not \in S$.)

So if $f(a,b) = f(n,k)=m$ then $a+b = n+k$.

So $\frac {(a+b)(a+b+1)}2 = \frac{\left(n+k+1\right)\left(n+k\right)}{2}$ and so $b = m - \frac {(a+b)(a+b+1)}2 = m - \frac{\left(n+k+1\right)\left(n+k\right)}{2}$ so $b = n$.

So $a = (a+b)-b = (n+k)-n = k$.

So $(n,k)$ is a unique value.

So $f$ is one-to-one.

Answer 2

The intuitive argument is that $\left(n+k+1\right)\left(n+k\right)$ is even and non-negative so clearly this is a function $\omega^2 \to \omega$, while $f(0,k)=\frac{k\left(k+1\right)}{2}$ giving the triangle numbers $0,1,3,6,10, \ldots$ for $k=0,1,2,3,4,\ldots$, and so $f(m,k-m)=\frac{k\left(k+1\right)}{2} +m$ for $0 \le m \le k$ fills the gaps between the triangle numbers

More explicitly, if we had a function which was in a sense the inverse of the triangle numbers, say $g(x)=\bigl{\lfloor} \frac{\sqrt{8x+1}-1}{2}\bigr{\rfloor}$ and another giving a sort of remainder, say $h(x)=x-\frac{g(x)(g(x)+1)}2$, then we could construct an actual inverse of $f$ as $i:\omega \to \omega^2$ with $i(x) = \Big(h(x), g(x)-h(x)\Big)$ in the sense that $i(f(n,k))=(n,k)$ and $f(i(x))=x$. If you have a two-way inverse then you have a bijection