# Existence of a function from $f : \mathbb Z^2 \rightarrow \mathbb Z$

I have a problem with the following question:

Does there exist a function $f : \mathbb Z^2 \rightarrow \mathbb Z$ that is one-to-one and onto, and hence invertible? (If yes, then $\mathbb Z^2$ can be called "countably inﬁnite.") If such a function exists then give a clear description of it. If such a function does not exist then explain why not.

Now, I cannot think of any function that satisfies this. How can there be an inverse function from $\mathbb Z \rightarrow \mathbb Z^2$? If a function of this type doesn't exist, how I can I explain so?

• You first can show that $\mathbb Z \cong \mathbb N$ and $\mathbb N \cong \mathbb N^2$. – user42761 Nov 6 '13 at 15:21
• Consider the counting argument for rational numbers – Tim Ratigan Nov 6 '13 at 15:22
• Have you considered attempting to show that $\Bbb Z^2$ can be mapped onto $\Bbb Q$ with a bijection? – abiessu Nov 6 '13 at 15:23
• @abiessu What comes to mind is something like this: $f(a,b) = a + b$. However, this function is not 1-1 but it is onto... – Dimitri Nov 6 '13 at 15:34
• @Dimitri: Why don't u use Andre's comment and then show that $\mathbb N\times\mathbb N$ is infinitely countable via another way? Not by an isomorphism function? – mrs Nov 6 '13 at 15:37

Simple explicit example of $\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ bijection is pictured below. This isn't a very formal definition, but I would say that it should pass as a "clear description" (in particular there are no ambiguities or doubts about whether the function is really 1-to-1 and onto).

$\hspace{70pt}$

If you are looking for formulas, then the simplest way would be to go through $\mathbb{N}\times\mathbb{N} \to \mathbb{N}$ bijections. My favorite can be found here along with some other (even simpler) examples.

I hope this helps $\ddot\smile$

• That's even nicer than my answer, all in one step :) What did you use to make the plot? – finitud Nov 6 '13 at 20:44
• @finitud Inkscape, I strongly recommend it! – dtldarek Nov 6 '13 at 20:49

It may be hard to find an explicit function with these properties, so instead try "proving that it exists". For example, think of elements of $Z\times Z$ as points in the Euclidean plane, and show that there are only finitely many of then inside any circle, so that "there exists" a finite list giving all of them, etc.

• Writing a formula might be tedious, but a "clear description" may assume many different forms ;-) – dtldarek Nov 6 '13 at 18:47

Regarding to @Andre's comment, why don't you employ the function $(n,m)\to 2^i3^j$ for showing that $$\mathbb N\times\mathbb N$$ is infinitely countable.

• If you want additional steps of using this way, sign me. – mrs Nov 6 '13 at 15:56

There is a way to do this that seems to me more appropriate than relying on "explicit" functions.

First, you use the function:

$\phi: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$

given by $\phi(n,m)=2^n.3^m$

This function is injective.(#1 why?) Here, we could invoke the Cantor-Bernstein-Schroeder theorem (with the way back being obvious), but we can use the fact that any infinite subset of a countable set is countable (#2 why?) (meaning we can make a bijection $\nu$ from it to $\mathbb{N}$)

So, call "$A$" the image of $\phi$. Then we have:

$\displaystyle \mathbb{N}\times \mathbb{N} \xrightarrow{\phi} A \xrightarrow{\nu} \mathbb{N}$

And the composition is a bijection from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$.

Now, a bijection from $\mathbb{Z}$ to $\mathbb{N}$ is easy (#3 why?) (Hint: just "count" the integers going forwards and backwards - formalize this as an exercise, if you don't know.)

It rests to show that there is a bijection from $\mathbb{Z}\times \mathbb{Z}$ to $\mathbb{N}\times \mathbb{N}$. But this follows from the bijection from $\mathbb{Z}$ to $\mathbb{N}$ (#4 why?)

• I see how this applies. I had to do a bit of research, but I understand. Thank you. – Dimitri Nov 6 '13 at 16:54

You can first map $\mathbb Z^2 \rightarrow \mathbb N$ by using a $g$ that maps: $$(0,0) \rightarrow 0$$ $$(1,0) \rightarrow 1$$ $$(1,1) \rightarrow 2$$ $$(0,1) \rightarrow 3$$ etcetera, in an outward spiral shape. Then you can map $\mathbb N \rightarrow \mathbb Z$ by using the function $h(x)$ that maps $h(2n) = n+1$ and $h(2n+1) = -n$. The mapping $f=g\circ h$ has the properties you are looking for.