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.
• 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:
• 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$