4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Too tired to read the details of this proof, but are you familiar with Cantor's diagonalization argument? You can easily adapt that to this case $\endgroup$ – Alan Mar 19 '15 at 3:08
  • $\begingroup$ @Alan so doing so would prove that there is a bijection? I need to prove that this function itself is a bijection $\endgroup$ – Larry Un Mar 19 '15 at 3:10
  • $\begingroup$ @Alan, or are you saying if I show that $\mathbb{Z} \times \mathbb{Z}$ can be written (using Cantor diag.) as the image of the function then the function is surjective? and clearly injective? $\endgroup$ – Larry Un Mar 19 '15 at 3:12
  • $\begingroup$ Oh, if you need to prove this functon is a bijection, that wouldn't help you, thought you were just trying to come up with a bijection. $\endgroup$ – Alan Mar 19 '15 at 3:12
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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$.

enter image description here

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.