Proposition 1   $\mathbb{N}^2$ is countable.

Proof. There are many ways to prove this. One way is to place the integer pairs in a two-dimensional array indicated by the table on the left below: Let $C(i,j)$ be the content of cell $(i,j)$ , located in the $i$ -th row and $j$ -th column. For example, $C(1,1)=(0,0)$ , and $C(3,2)=(2,1)$ .

Now, let us construct a list of the pairs, which essentially amounts to constructing a bijection $h: \mathbb{N}^2 \to \mathbb{N}$ (the table on the right above). We start at cell $(1,1)$ . If cell $(i,j)$ has been counted, the next cell to be counted is $(i+1,j-1)$ if $j>1$ , or $(1,i+1)$ if $j=1$ . Thus, the first several pairs on the list are $$(0,0),\; (0,1),\; (1,0),\; (0,2),\; (1,1),\; (2,0),\; (0,3),\; \ldots$$ We leave it to the reader to find the bijection $h$ (hint: see the entry on pairing function). Therefore, $\mathbb{N}^2$ is countable.

Proposition 2   If $A$ and $B$ are countable, so is $A\times B$ .

Proof. Suppose $f:A\to \mathbb{N}$ and $g:B\to \mathbb{N}$ are injections. Then $h:=(f,g):A\times B\to \mathbb{N}^2$ is an injection. Since $\mathbb{N}^2$ is countable, so is $A\times B$ .

Proposition 3   Let $n$ be a positive integer, and $A_1,\ldots, A_n$ sets. Then $A_1 \times \cdots \times A_n$ is countable iff each $A_i$ is.

Proof. Again, if one of $A_i$ is empty, so is the product, and vice versa. The countability follows immediately. So we assume that none of $A_i$ is empty. Set $A:=A_1\times \cdots A_n$ .

Suppose first that $A_1,\ldots, A_n$ are countable. We do induction on $n$ . The case where $n=1$ is clear. Suppose now that $n=k$ is true. Then $A_1\times \cdots \times A_k \times A_{k+1}$ is just the product of two countable sets $A_1 \times \cdots \times A_k$ and $A_{k+1}$ , which we know is countable by the proposition above.

Conversely, suppose $A$ is countable. Let $g: A \to \mathbb{N}$ be an injection. Since $A_i \ne \varnothing$ , fix $a_i\in A_i$ for each $i = 1,\ldots, n$ . Now, for any $A_i$ , define a map $e_i: A_i\to A$ so that the $i$ -th component of $e_i(a)$ is $a$ , and the $j$ -th component is the fixed element $a_j \in A_j$ , if $j\ne i$ . Clearly, $e_i: A_i\to A$ is an injection, so its composition with $g$ is also an injection from $A$ to $\mathbb{N}$ , showing that $A_i$ is countable.

Corollary 1   For any positive integer $n$ , $A$ is countable iff $A^n$ is.