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$
  • $\begingroup$ You first can show that $\mathbb Z \cong \mathbb N$ and $\mathbb N \cong \mathbb N^2$. $\endgroup$ – user42761 Nov 6 '13 at 15:21
  • 1
    $\begingroup$ Consider the counting argument for rational numbers $\endgroup$ – Tim Ratigan Nov 6 '13 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 Nov 6 '13 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 Nov 6 '13 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$ – mrs Nov 6 '13 at 15:37
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$
  • $\begingroup$ That's even nicer than my answer, all in one step :) What did you use to make the plot? $\endgroup$ – finitud Nov 6 '13 at 20:44
  • $\begingroup$ @finitud Inkscape, I strongly recommend it! $\endgroup$ – dtldarek Nov 6 '13 at 20:49
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$
  • $\begingroup$ Writing a formula might be tedious, but a "clear description" may assume many different forms ;-) $\endgroup$ – dtldarek Nov 6 '13 at 18:47
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$
  • $\begingroup$ If you want additional steps of using this way, sign me. $\endgroup$ – mrs Nov 6 '13 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
    $\begingroup$ I see how this applies. I had to do a bit of research, but I understand. Thank you. $\endgroup$ – Dimitri Nov 6 '13 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$

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.