elementary set theory - 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!

Answer

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