# Bijecting a countably infinite set $S$ and its cartesian product $S \times S$

From Herstein's Topics in Algebra (exercise 14, section 1.2):

If $S$ is infinite and can be brought into one-to-one correspondence with the set of integers, prove that there is one-to-one correspondence between $S$ and $S \times S$.

So far I know there exists some bijection $\sigma : S \rightarrow \mathbb{Z}$. If I can define a bijection $\tau : \mathbb{Z} \rightarrow \mathbb{Z} \times \mathbb{Z}$, then a one-to-one correspondence between $S$ and $S \times S$ is given by $\mu$ such that $s_\mu = (a_{\sigma^{-1}},b_{\sigma^{-1}})$, with $a,b\in \mathbb{Z}$ given by $s_{\sigma \circ \tau} = (a,b)$.

I'm having trouble defining $\tau$. I think a possible way to do so would be to create some kind of spiral (like the Ulam spiral), and assign each point to a different integer. I suppose this would be a one-to-one correspondence but I'm at a loss on how to prove it. Thanks a lot!

-
I'm not sure if set-theory is the appropriate tag here by the way. – F M Jan 6 '11 at 20:48
[set-theory] is probably okay; if not, then [elementary-set-theory] would certainly be. – Arturo Magidin Jan 6 '11 at 20:50

It's a little simpler to find a bijection $\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ (e.g., think of the usual proof that $\mathbb{Q}$ is countable). There is also an easy bijection $\mathbb{Z}\to\mathbb{N}$, so you can use that to get a bijection $\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}$.

A couple of comments, though: Herstein is only asking you to show that such a bijection exists, not to explicitly construct one. You could do so using any number of tools, including some that are in principle constructive but which you may not want to actually carry out. For example, there are obvious and easy embeddings $\mathbb{Z}\hookrightarrow \mathbb{Z}\times\mathbb{Z}$. If you also have an embedding $\mathbb{Z}\times\mathbb{Z}\hookrightarrow \mathbb{Z}$ you get the existence of a bijection between the two by using Cantor-Bernstein. For instance, you could take: $$(a,b)\longmapsto \left\{\begin{array}{ll} 2^a\times 3^b &\text{if a,b\geq 0;}\\ 3^b\times 5^{|a|} &\text{if a\lt 0, b\geq 0;}\\ 2^a\times 7^{|b|} &\text{if a\geq 0, b\lt 0;}\\ 5^{|a|}\times 7^{|b|} &\text{if a,b\lt 0.} \end{array}\right.$$ So with this you know there is a bijection $S\to S\times S$, even if you don't go through the rather annoying work of trying to write it out explicitly.

Also, it might be worth noting that if you drop the clause "and can be brought into one-to-one correspondence with the set of integers", then the resulting statement is equivalent to the Axiom of Choice (this is a result of Tarski's).

-
Arturo, actually Tarski's result is that if every infinite set $A$ is equinumerous to $A\times A$ then AC holds. However the bijection from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$ is explicitly defined (as in my answer) – Asaf Karagila Jan 6 '11 at 21:16
@Asaf: Notice that I said "if you drop the clause". Take the quoted statement by the OP, and delete the words "and can be brought into one-to-one correspondence with the set of integers"; you get "If $S$ is infinite, prove that there is a one-to-one correspondence between $S$ and $S\times S$"; this implication is equivalent to AC, and the fact that this is equivalent to AC is Tarski's theorem; I thought that the syntax of my sentence made it clear this is what I meant to say. – Arturo Magidin Jan 6 '11 at 21:22
Arturo, you are absolutely right! Sorry :-) – Asaf Karagila Jan 6 '11 at 21:24
For my intro analysis course, I remember we were asked to prove Cantor-Bernstein. Now that was fun. – TNi Jan 6 '11 at 22:21
@TNi: Analysis? Interesting. We prove the theorem in introduction to logic and set theory. – Asaf Karagila Jan 6 '11 at 23:31

You can do it the following way:

1. Define $f\colon\mathbb{Z}\to\mathbb{N}$ to be any bijection (for example, $f(x) = 2x$ if $x\ge 0$ and $f(x) = -2x+1$ otherwise)
2. Define $g\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ your favourite bijection (e.g. $f(a,b) = \frac{(a+b+1)(a+b)}{2}+a$)
3. Assume $\sigma$ is a bijection of $S$ with $\mathbb{Z}$ then define: $\tau(s_1,s_2) = \sigma^{-1}(f^{-1}(g(f(\sigma(s_1)),f(\sigma(s_2)))))$

The proof that $\tau$ is a bijection is pretty straightforward, I think.

Of course you can skip many a step in this crazy composition by using Cantor-Schroeder-Bernstein theorem.

Edit:
I think I should expand a bit on the second part, as Arturo said in the comments to the original question. Assume $f\colon\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ a bijection, and $\sigma\colon S\to\mathbb{Z}$ then you have $\tau(s_1,s_2) = f(\sigma(s_1),\sigma(s_2))$ a bijection from $S\times S$ to $\mathbb{Z}$ and therefore you have both $S$ and $S\times S$ equinumerous with the integers, and therefore with each other.

-

In addition to Arturo's answer, recall that if you have a bijection between A and B, and one between B and C, you have a bijection between A and C by composition.

-