# 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},\ldots,A_{n}$ be countable sets and let $S=A_{1}\times A_{2}\times\cdots\times A_{n}$. Since each $A_{i}$ is countable, there exists an injective function $f_{i}\colon A_{i}\to\mathbb{N}$. The function $h\colon S\to\mathbb{N}$ defined by

 $h(a_{1},a_{2},\ldots a_{n})=\prod_{i=1}^{n}p_{i}^{f_{i}(a_{i})}$

where $p_{i}$ is the $i$th prime is, 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 the Cartesian product of a countably infinite collection of countable sets. If such a collection contains more than a finite number of sets with at least two elements, then Cantor’s diagonal argument can be used to show that the product is not countable.

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

Title the Cartesian product of a finite number of countable sets is countable TheCartesianProductOfAFiniteNumberOfCountableSetsIsCountable 2013-03-22 15:19:45 2013-03-22 15:19:45 BenB (9643) BenB (9643) 13 BenB (9643) Theorem msc 03E10 The product of a finite number of countable sets is countable CardinalityOfACountableUnion AlgebraicNumbersAreCountable CardinalityOfTheRationals