0

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

enter image description here

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

Barak Ohana
  • 67
  • 2
    https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function – Noah Schweber Dec 23 '18 at 00:51
  • 1
    "Proof by pictures" can be some of the simplest kinds of proof. As the picture suggests, if we were to go through the entries of the diagonals going from up-left to down-right, starting from the smallest such diagonal and progressively getting larger, this corresponds to going through the outputs as $0,1,2,3,4,\dots$ going through each of the natural numbers in sequence. Showing that the function acts as described takes a bit of knowledge about triangular numbers and can be proven by induction over the sum of $n+k$ as well as $n$. – JMoravitz Dec 23 '18 at 00:56
  • Related: https://math.stackexchange.com/questions/3010935/is-there-an-intuitive-way-to-understand-pairx-y-fracxyxy12-x#comment6209760_3010935 – Mason Dec 23 '18 at 01:22
  • What is $\omega$? – Michael Dec 23 '18 at 01:24
  • 1
    @Michael. $\omega =\mathbb{N}$. This is a convention from cardinal arithmetic. – Mason Dec 23 '18 at 01:29

2 Answers2

1

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

Henry
  • 157,058
  • great way to show that $f$ is surjective! I don't see how $g$ make sense as an inverse. – Barak Ohana Dec 23 '18 at 02:00
  • @user3195363 for example $g(6)=3$ and $g(10)=4$ which is what you want when inverting triangle numbers. But it is only an inverse "in a sense" and one-way since you also have $g(7)=3$ – Henry Dec 23 '18 at 02:05
0

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.

fleablood
  • 124,253
  • I didn't quite understand why, in the ono-to-one proof we got $ m−(1+2+......+a+b)\geq(a+b)+1 $. – Barak Ohana Dec 23 '18 at 10:52
  • $w_m = n+k$ was the smallest such number where the sum is $\ge m$. If $a+b > n+k$ then $1 + ..... + (a+b) > 1 + ..... + (n+k) \ge m$. If $a+b < n+k$ then $1 + .... + (a+b) \not \ge m$ – fleablood Dec 23 '18 at 17:27