The Cartesian Product of Two Countable Sets is Countable

Theorem 1: Let $A$ and $B$ be countable sets. Then the cartesian product $A \times B$ is countable.

• Proof: There are three cases to consider.

• Case 1: If both $A$ and $B$ are finite with $|A| = m$ and $|B| = n$ then it is easy to show that $|A \times B| = mn$ and hence $A \times B$ is finite and so it is countable.

• Case 2: If $A$ is finite with $|A| = n$ and $B$ is countably infinite then there exists bijective functions $f : A \to \{ 1, 2, ..., n \}$ and $g : B \to \mathbb{N}$. Define $h : A \times B \to \mathbb{N}$ for all $(a, b) \in A \times B$ by:

(1)

\begin{align} \quad h(a, b) = 2^{f(a)} \cdot 3^{g(b)} \end{align}

• Then clearly $h$ is injective by the unique factorization of the each natural number. So $A \times B$ is countable.

• Case 3: If $A$ and $B$ are both countable then there exists bijective functions $f : A \to \mathbb{N}$ and $g : B \to \mathbb{N}$ and defining $h : A \times B \to \mathbb{N}$ as above still gives us an injective function, and so $A \times B$ is countable. $\blacksquare$