X and Y are infinite countable sets, prove that X × Y is infinite and countable This is a problem on my maths homework where I don't really know where to start, any help would be appreciated :)
For any sets X and Y let
$X\times Y := \left\{(x, y) : x \in X\text{ and} \ y ∈ Y \right\}$ 
denote the set of all ordered pairs (x, y) with x ∈ X and y ∈ Y . (For example, R × R = R^2)
Show that, if X and Y are countable infinite sets, then also X × Y is countable. (Hint. N →
N × N → X × Y )
 A: Separate the proof in three steps: 
1) Let $f:X \rightarrow Y$ be injective. If $Y$ is countable, then $X$ is countable. 
2) Let $f: X \rightarrow Y$ be surjective. If $X$ is countable, then $Y$ is countable. 
3) With 1) and 2), using the fact that $X$ and $Y$ are countable, you can define a surjective map : $${\varphi : \mathbb{N}\times\mathbb{N} \rightarrow X \times Y }$$ as $\varphi(n,m) = (f(n),g(m))$ where $f$ and $g$ are the respective bijections of $\mathbb{N}$ in $X$ and $Y$. Then you have constructed a surjective map of $ \mathbb{N}\times\mathbb{N}$ onto $X\times Y$. Then you need to show that $\mathbb{N}\times\mathbb{N} $ is countable. By 1), it suffices to construct a injective map of $ \mathbb{N}\times\mathbb{N} $ to $\mathbb{N}$. 
Hint: the decomposition of a number in prime factors. 
A: 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.
A: I completely agree with Mr. Almeida's proof, and simply wish to add this:
Let g: N X N to N. g(m,n) = (2^m)(3^n), which is apparently an injective map, since if g(m,n) = g(p,q), then (2^(m-p))(3^(n-q)) = 1, which implies that m = p, and that, n=q, since g.c.d(2,3)=1. 
Now, by Result (1) in Mr. Almeida's proof, since we have managed to find an injection, we know that N X N is countable. Now, since you have a surjection from N X N to X x Y, we are through, by Result (2) of Mr. Almeida's proof. 
A: Well, there's nothing wrong with the cliched classics.  It's going to be assumed later that you know them and find them obvious and they are your first thought.
Map: N $\rightarrow$ N x N as:
1->(0,0 ) pairs that add up to zero
2->(0,1) 3->(1,0) pairs that add up to one
4->(0,2) 5->(1, 1) 6->(2,0) pairs that add up to two.
and so on.
Usually at this point the presenter just says "so it's obvious" and walks away.  So each pair (n,m) $\rightarrow  (\sum_{i= 1}^{n+m}) + n + 1=M $ which is unique to n and m.  And each natural number M has a unique $p_M$ and $S_M$ such that $S_M=\sum_{i= 1}^{p_M} < M  $ but   $\sum_{i= 1}^{p_M+ 1} \ge M$.  So M $\rightarrow (M - S_M - 1, (p_M + 1) -  (M - S_M - 1))$ which is unique to M.  Which is a lot more tedious than anyone needs.
A: I will apply Bruno Almeida' tip 1) in the following way: construct an injection from $f\colon \mathbf{N}\times  \mathbf{N}\to \mathbf{N}$. This will show the set is countable.
Write the numbers in base  7 number system: use the digits $0,1,2,3,4,5$ and $6$. So a  typical element of the  cartesian product looks like
$(312,5104)$. In this replace open parenthesis by the (unused) symbol  $7$,  comma by the symbol $8$, close parenthesis by the symbol $9$, getting in this case $\mathbf{7}312\mathbf{8}5104\mathbf{9}$. That is
$f(312,5104)=\mathbf{7}312\mathbf{8}5104\mathbf{9}$. It is fun to check that  this $f$ is an injective function.
