# Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?

-
Can you prove that $\mathbb N\simeq\mathbb N\times\mathbb N$? Compose that proof with the (product of the) bijections you get from knowing that $A$ and $B$ are countable. –  Henning Makholm Oct 12 '11 at 1:20
Do you know how to prove that $\mathbb{N}\times\mathbb{N}$ is countable? Because if you do, you can use essentially the same argument for $A\times B$. –  Brian M. Scott Oct 12 '11 at 1:21

In your answer you use Cantor's pairing function. It is an important function indeed. However using Cantor-Bernstein's theorem we only need to find an injection from $\mathbb N\times\mathbb N$ into $\mathbb N$.

A useful example is: $$f(m,n) = 2^m\cdot 3^n$$

If $f(m,n)=f(l,k)$ then by the fundamental theorem of arithmetics we have that $m=l, n=k$.

We now can find an injection $g\colon\mathbb N\to\mathbb N\times\mathbb N$, for example $g(n)=(0,n)$.

Now Cantor-Bernstein's theorem tells us that if $f\colon A\to B$ and $g\colon B\to A$ are two injective functions, then there is a bijection from $A$ into $B$.

From this to $\mathbb N^k$ being countable, you can either go with induction, as you suggested, or map $(m_1,\ldots,m_k)$ to $p_1^{m_1}\cdot\ldots p_k^{m_k}$, where $p_i$ is the $i$-th prime number.

-

So I know $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ via (provided from class proof): $$f(x,y) = \frac{(x + y - 2)(x + y - 1)}{2}$$ Then it would mean that two countable sets, $A$ and $B$, can be set up as $f:\mathbb{N} \to A$ and $g: \mathbb{N} \to B$. This points to: $$f \times g : \mathbb{N} \times \mathbb{N} \to A \times B$$ There is now a surjection $\mathbb{N} \times \mathbb{N}$ to $A \times B$ $\implies$ $A \times B$ is also countable. So then induction can be used in the number of sets in the collection.

-
Yes, this is why the product of finitely many countable sets is still countable. –  Asaf Karagila Oct 12 '11 at 15:16
Another map in like yours is this: $f(x)=\frac{(x+y)^2+3x+y}{2}$ –  leo Oct 13 '11 at 0:10