Countability of $\mathbb{Z} \times \mathbb{Z}$ using isomorphism with $\Bbb Z[i]$ - how to make this rigorous?

Question

Visualise the set $\mathbb{Z}\times \mathbb{Z}$ as points on the complex plane, and take origin as the center of a circle of radius $r$. With $r$ going from $0$ to $\infty$ - as you encounter points on the circle, write them down in counterclockwise order. This way you have a bijective mapping, thus $\mathbb{Z}\times \mathbb{Z}$ is countable.

This proof about the countability of $\mathbb{Z}\times \mathbb{Z}$ doesn't look rigorous enough to me. It was proposed by one of my colleagues. The proposal is to write down elements of $Z[i]$ as we encounter them in some sort of a spiral order.

I need help making this more rigorous.

Is there an explicit bijection for this? It'd be great if someone could help me construct the same.

Perhaps we must show that every such circle has only a countable number of such points and that only countably many such circles, i.e. values of $r$ matter. Thanks!

Answer 1

I came up with this - does it look fine enough?

Consider $z = x+iy \in \mathbb{Z}[i]$, with $x^2 + y^2 = r^2$.  As $r^2$ goes from zero to $\infty$, we cover the entire complex plane. If $x,y\in\mathbb{Z}$ then $r^2 \in \mathbb{Z}$. Define $P = \{ r^2: r\in \mathbb{R}^{\geq 0}, r^2 \in\mathbb{Z}\}$. Since $\mathbb{Z}$ is countable,  so is $P$. Now, for some fixed $r_1$such that $r_1^2\in P$, think about $x^2 + y^2 = r_1^2$. This gives $|x| \le r_1, |y| \le r_1$. Since $r_1$ is finite, the set of values $(x,y) $ such that  $x^2 + y^2 = r_1^2$ holds, is finite. Knowing that a countable union of countable sets is countable, we see that the set $\mathbb{Z}[i]$ is countable. As a result, $\mathbb{Z} \times \mathbb{Z}$ is also countable. 

Answer 2

As the the radius of the circle goes to infinity, each $a+bi$ lies on some circle in the same place as the point $(a,b)$ on the Cartesian graph in $\mathbb{Z}$. I guess there might be a way to explicitly find the radii (which are the going to be same for each point $(a,b)$ in the cartesian plane to the $a+bi$ in the complex plane) and do something with that, but that just seems to make the argument longer. Maybe the point is that this same circle process can be repeated on the Cartesian graph to get that the exact same thing happens.

However, this argument seems to overcomplicate the whole thing by turning this discrete problem into one involving a continuous process of taking $r \to \infty$. It really seems to be saying the same thing as the explicit bijection, but with more words and unnecessary ideas. Perhaps I am missing something.

Answer 3

Adding to strawberry-sunshine's answer: An explicit bijection is hard because it is hard (a) to give an explicit enumeration of all radii that contain a number from $\mathbb Z [i]$ and (b) given one such radius to enumerate all numbers in $\mathbb Z [i]$ with that radius with an explicit function.

As the other answer pointed out, for any radius $r$ there is a finite number of associated numbers in $\mathbb Z [i]$, say S. We can order these formally counterclockwise by first ordering all the numbers $S_+$ from the upper half plane (plus the nonnegative real number halfline) by setting $S_0 = \emptyset$, $S_n=\{a_1+ib_1,\ldots,a_n+ib_n\}$ and

$$a_{n+1} = \max \{a\in \mathbb R: \exists b\in \mathbb R: a+bi\in S_+\setminus S_n\}, \quad b_{n+1} = \sqrt{r^2-a_{n+1}^2} $$

and after that, if $r\neq 0$, set $a_{|S_+|+n} = a_{|S_+|-n+1}$ and $b_{|S_+|+n} = -b_{|S_+|-n+1}$. So by induction, you can order all those numbers counterclockwise, but a convenient definition without using recursion escapes me.

---

However, this is all unneededly complicated. Also the line

Visualise the set $\mathbb Z \times \mathbb Z$ as points on the complex plane

basically already is a bijection, namely $f:\mathbb Z \times \mathbb Z\rightarrow \mathbb Z[i], (a,b)\mapsto a+bi$. If you are looking for formal proofs always be suspicious when someone uses terms like "visualize", as that is not a valid concept in formal proofs. The given bijection can easily be seen as bijective by confirming the function $g:\mathbb Z[i]\rightarrow \mathbb Z \times \mathbb Z, z\mapsto (\Re(z),\Im(z))$ is the inverse (which we can check by checking that $g\circ f$ and $f \circ g$ are the identities on $\mathbb Z \times \mathbb Z$ and $\mathbb Z[i]$ respectively). Therefore, the enumerating as done above with the counterclockwise ordering is unneededly contrived, albeit a good thought exercise nonetheless.

---

Finally a way I would prefer is simply using that if $|A|=|C|$ and $|B|=|D|$ (i.e. bijections between these sets $A, B, C, D$ exist), then $|A\times B|=|C\times D|$ (if the given bijections are $f$ and $g$ respectively, then the new bijection is given by $(a,c)\mapsto (f(a),g(c))$). Then set $A=B=\mathbb N$ and $C=D=\mathbb Z$ and the countability of $\mathbb Z \times \mathbb Z$ follows from the countability of $\mathbb N \times \mathbb N$.