Bijection from $\mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$

Question

My goal here is to find a bijection from $\mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$ (this is letting $0 \in \mathbb{Z}$

Here's what I have so far:

Let $$A = \{ x^2 - x \mid x \in \mathbb{Z} \} $$ and let $g: \mathbb{Z} \to \mathbb{Z}$, $g(x) = a \in A$, $a$ is the greatest element of $A$ for which $a \leq x$ i.e.

$$ x \geq a $$ $$ \forall_{b \in A} \left( b > a \to b > x \right)$$

The function $g$ maps an integer to the greatest triangle number that is smaller than itself. For example, $$g(0) = 0$$ $$g(1) = g(2) = 1$$ $$g(3) = g(4) = g(5) = 3$$ $$g(6) = g(7) = g(8) = g(9) = 6$$

Let $h: \mathbb{Z} \to \mathbb{Z}$, $h(x) = g(x) - g(g(x) - 1)$

$$h(0) = 0$$ $$h(1) = h(2) = 1$$ $$h(3) = h(4) = h(5) = 2$$ $$h(6) = h(7) = h(8) = h(9) = 3$$

Let $f: \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}$ such that $$f(x) = (x - g(x), h(x) - (x - g(x)))$$

$$f(0) = (0 - 0, 0 - 0) = (0,0) $$ $$f(1) = (1 - 1, 1 - (1 - 1)) = (0, 1) $$ $$f(2) = (2 - 1, 1 - (2 - 1)) = (1, 0) $$ $$f(3) = (3 - 3, 2 - (3 - 3)) = (0, 2) $$ $$f(4) = (4 - 3, 2 - (4 - 3)) = (1, 1) $$ $$f(5) = (5 - 3, 2 - (5 - 3)) = (2, 0) $$ $$ . $$ $$ . $$ $$ . $$

How could I go about finding an inverse for this function? Aside from showing that it is an isomorphism. The goal is not to simply prove that a bijection exists but to actually find a bijection.

Answer 1

Writing a formula for that diagonalization is tedious. (Someone please prove me wrong in another answer!) Instead, I'd place an order on $\mathbb N^2$ as follows:

$(a,b)\leq(c,d)$ in the case that either $a+b<c+d$ or ($a+b=c+d$ and $a\leq c$)

Then you can define $f(0)=(0,0)$ and $f(n+1)=\min(\{(x,y)\in\mathbb Z^2:(x,y)>f(n)\})$. This is well defined if you can show that for each $(a,b)$ there is a larger point in the order (say, $(a+1,b)$), and this is obviously an injective map since $f(n+1)>f(n)$. Finally, to show that it is onto, you can show that for each point $(a,b)$, only finitely many points are less than it with this order (since only finitely many points have sum less than or equal to $a+b$).

This gives a bijection $\mathbb N \to \mathbb N\times\mathbb N$; a little more work gives $\mathbb Z \to \mathbb Z\times\mathbb Z$.

Answer 2

First choose a bijection $\mathbb Z \to \mathbb N$, for instance the one whose inverse is $0,1,-1,2,-2,3,-3,\dots$.

Now, use a spiral to get a bijection $\mathbb N \to \mathbb Z \times \mathbb Z$. Assume $\mathbb N$ does not contain $0$.

You can have some fun writing an formula for the composite bijection $\mathbb Z \to \mathbb Z \times \mathbb Z$ if you really want a formula.

See this question and this other one.