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 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 \mathrm{\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
Canonical name	TheCartesianProductOfAFiniteNumberOfCountableSetsIsCountable
Date of creation	2013-03-22 15:19:45
Last modified on	2013-03-22 15:19:45
Owner	BenB (9643)
Last modified by	BenB (9643)
Numerical id	13
Author	BenB (9643)
Entry type	Theorem
Classification	msc 03E10
Synonym	The product of a finite number of countable sets is countable
Related topic	CardinalityOfACountableUnion
Related topic	AlgebraicNumbersAreCountable
Related topic	CardinalityOfTheRationals