Let's start with a quick review of "countable". A set is countable if we can set up a 1-1 correspondence between the set and the natural numbers. As an example, let's take $\mathbb{Z}$, which consists of all the integers. Is $\mathbb Z$ countable?
It may seem uncountable if you pick a naive correspondence, say $1 \mapsto 1$, $2 \mapsto 2 ...$, which leaves all of the negative numbers unmapped. But if we organize the integers like this:
$$0$$
$$1, -1$$
$$2, -2$$
$$3, -3$$
$$...$$
We quickly see that there is a map that works. Map 1 to 0, 2 to 1, 3 to -1, 4 to 2, 5 to -2, etc. So given an element $x$ in $\mathbb Z$, we either have that $1 \mapsto x$ if $x=0$, $2x \mapsto x$ if $x > 0$, or $2|x|+1 \mapsto x$ if $x < 0$. So the integers are countable.
We proved this by finding a map between the integers and the natural numbers. So to show that the union of countably many sets is countable, we need to find a similar mapping. First, let's unpack "the union of countably many countable sets is countable":
"countable sets" pretty simple. If $S$ is in our set of sets, there's a 1-1 correspondence between elements of $S$ and $\mathbb N$.
"countably many countable sets" we have a 1-1 correspondence between $\mathbb N$ and the sets themselves. In other words, we can write the sets as $S_1$, $S_2$, $S_3$... Let's call the set of sets $\{S_n\}, n \in \mathbb N$.
"union of countably many countable sets is countable". There is a 1-1 mapping between the elements in $\mathbb N$ and the elements in $S_1 \cup S_2 \cup S_3 ...$
So how do we prove this? We need to find a correspondence, of course. Fortunately, there's a simple way to do this. Let $s_{nm}$ be the $mth$ element of $S_n$. We can do this because $S_n$ is by definition of the problem countable. We can write the elements of ALL the sets like this:
$$s_{11}, s_{12}, s_{13} ...$$
$$s_{21}, s_{22}, s_{23} ...$$
$$s_{31}, s_{32}, s_{33} ...$$
$$...$$
Now let $1 \mapsto s_{11}$, $2 \mapsto s_{12}$, $3 \mapsto s_{21}$, $4 \mapsto s_{13}$, etc. You might notice that if we cross out every element that we've mapped, we're crossing them out in diagonal lines. With $1$ we cross out the first diagonal, $2-3$ we cross out the second diagonal, $4-6$ the third diagonal, $7-10$ the fourth diagonal, etc. The $nth$ diagonal requires us to map $n$ elements to cross it out. Since we never "run out" of elements in $\mathbb N$, eventually given any diagonal we'll create a map to every element in it. Since obviously every element in $S_1 \cup S_2 \cup S_3 ...$ is in one of the diagonals, we've created a 1-1 map between $\mathbb N$ and the set of sets.
Let's extend this one step further. What if we made $s_{11} = 1/1$, $s_{12} = 1/2$, $s_{21} = 2/1$, etc? Then $S_1 \cup S_2 \cup S_3 ... = \mathbb Q^+$! This is how you prove that the rationals are countable. Well, the positive rationals anyway. Can you extend these proofs to show that the rationals are countable?
Best Answer
Since $X$ and $Y$ are countably infinite sets, their elements can be listed such that $$X=\{x_1,x_2,x_3,x_4, \cdots\}$$ and $$Y=\{y_1,y_2,y_3,y_4, \cdots\}$$
We can then display the elements of $X \times Y$ as a two dimensional array: $$ \begin{array}{c|lcr} &\quad\text{$y_1$}&\text{$y_2$}&\text{$y_3$}&\text{$y_4$}&\text{$y_n$}\\ \hline x_1 & (x_1,y_1) \color{red}\to & (x_1,y_2) & (x_1,y_3) & (x_1,y_4) & \cdots\quad(x_1,y_n) & \cdots & \cdots & \cdots & \cdots & \cdots & \\ x_2 & (x_2,y_1) & (x_2,y_2) & (x_2,y_3) & (x_2,y_4) & \cdots\quad(x_2,y_n) &\cdots & \cdots & \cdots & \cdots & \cdots & \\ x_3 & (x_3,y_1) & (x_3,y_2) & (x_3,y_3) & (x_3,y_4) & \cdots\quad(x_3,y_n) &\cdots & \cdots & \cdots & \cdots & \cdots & \\ x_4 & (x_4,y_1) & (x_4,y_2) & (x_4,y_3) & (x_4,y_4) & \cdots\quad(x_4,y_n)&\cdots & \cdots & \cdots & \cdots & \cdots &\\ \\ x_n & (x_n,y_1) & (x_n,y_2) & (x_n,y_3) & (x_n,y_4) & \cdots\quad(x_n,y_n)&\cdots & \cdots & \cdots & \cdots & \cdots &\\ \\ \end{array} $$
This is known as proof by list and after the first right $\color{red}{\mathrm{red}}$ arrow to $(x_1,y_2)$ you go diagonally to $(x_2,y_1)$ then down to $(x_3,y_1)$ then diagonally to $(x_2,y_2)$ and diagonally to $(x_1,y_3)$ then down to $(x_2,y_3)$ and repeat the pattern in this manner. By continuing this pattern you have shown that $X \times Y$ is countable.
Apologies, for not being able to draw the arrows in here, as there is no way I can format the diagonal ones in, and annoyingly when we prove this on paper the arrows are crucial for a proof by list using a $2D$ array.