the Cartesian product of a finite number of countable sets is countable

Theorem 1

The Cartesian product of a finite number of countable sets is countable.

Proof:Let $A_1,A_2,\mathrm{\dots },A_n$ be countable sets and let$S=A_1\times A_2\times \mathrm{\cdots }\times A_n$.Since each $A_i$ is countable, there exists an injective function$f_i:A_i\to \mathbb{N}$.The function $h:S\to \mathbb{N}$ defined by

$$h(a_1,a_2,\mathrm{\dots }{a}_n)=\prod _{i=1}^n{p}_i^{f_i(a_i)}$$

where $p_i$ is the $i$th primeis, by the fundamental theorem of arithmetic, a bijection between$S$ and a subset of $\mathbb{N}$ and therefore $S$ is also countable.

Note that this result does not (in general) extend to theCartesian product of a countably infinite collection of countablesets. If such a collection contains more than a finite number of setswith at least two elements, then Cantor’s diagonal argument can beused to show that the product is not countable.

For example, given $B=\{0,1\}$, the set $F=B\times B\times \mathrm{\cdots }$ consists of all countably infinite sequences of zeros and ones.Each element of $F$ can be viewed as a binary fraction and cantherefore be mapped to a uniquereal number in $[0,1)$ and $[0,1)$ is, of course, not countable.