# 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 |