1
$\begingroup$

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 infinite.") 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?

$\endgroup$
5
  • $\begingroup$ You first can show that $\mathbb Z \cong \mathbb N$ and $\mathbb N \cong \mathbb N^2$. $\endgroup$
    – user42761
    Commented Nov 6, 2013 at 15:21
  • 1
    $\begingroup$ Consider the counting argument for rational numbers $\endgroup$ Commented Nov 6, 2013 at 15:22
  • $\begingroup$ Have you considered attempting to show that $\Bbb Z^2$ can be mapped onto $\Bbb Q$ with a bijection? $\endgroup$
    – abiessu
    Commented Nov 6, 2013 at 15:23
  • $\begingroup$ @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... $\endgroup$
    – Dimitri
    Commented Nov 6, 2013 at 15:34
  • $\begingroup$ @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? $\endgroup$
    – Mikasa
    Commented Nov 6, 2013 at 15:37

5 Answers 5

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Writing a formula might be tedious, but a "clear description" may assume many different forms ;-) $\endgroup$
    – dtldarek
    Commented Nov 6, 2013 at 18:47
2
$\begingroup$

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}$simple example of ZxZ to Z function using a double spiral

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$

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

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.

$\endgroup$
1
  • $\begingroup$ If you want additional steps of using this way, sign me. $\endgroup$
    – Mikasa
    Commented Nov 6, 2013 at 15:56
1
$\begingroup$

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?)

$\endgroup$
1
  • 1
    $\begingroup$ I see how this applies. I had to do a bit of research, but I understand. Thank you. $\endgroup$
    – Dimitri
    Commented Nov 6, 2013 at 16:54
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .