Krdytkyu

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

$$
f(n,k)=frac{left(n+k+1right)left(n+kright)}{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.

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+1right)left(n+kright)}{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= {kin 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+1right)left(n+kright)}{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{kin 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+bnot 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+1right)left(n+kright)}{2}$ and so $b = m - frac {(a+b)(a+b+1)}2 = m - frac{left(n+k+1right)left(n+kright)}{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.

The intuitive argument is that $left(n+k+1right)left(n+kright)$ is even and non-negative so clearly this is a function $omega^2 to omega$, while $f(0,k)=frac{kleft(k+1right)}{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{kleft(k+1right)}{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